我正在尝试在 python 中实现Kademlia（二叉树）DHT。据我了解，路由表需要将根节点 ID 中的各个位与新条目进行比较。如果 ID 的位不匹配，则向左走，如果匹配，则向右走。这可以递归地完成，您的停止条件是您已到达 ID 长度的末尾或您已到达叶节点。然后每个叶节点都包含自己的 kbucket（一个数组）。
目前我尝试过的如下：
#!/usr/bin/python
class Node:
def __init__(self, id, data):
self.id = id
self.data = data
self.left = None
self.right = None
def __str__(self):
return '{id:' + self.id + ',' + self.data + '}'
class Tree:
def __init__(self):
self.root = None
def find_placement(self, node, previous_node, id_index):
if (node == None):
return previous_node, id_index
elif (node.right == None and node.left == None):
return node, id_index
elif (node.id[id_index] == previous_node.id[id_index]):
return self.find_placement(node.right, node, id_index+1)
elif (node.id[id_index] != previous_node.id[id_index]):
return self.find_placement(node.left, node, id_index+1)
def add(self, id, data):
new_node = Node(id, data)
if (self.root == None):
self.root = new_node
return
previous_node = current_node = self.root
id_index = 0
current_node, id_index = self.find_placement(current_node, previous_node, id_index)
if (current_node.id[id_index] == new_node.id[id_index]):
current_node.right = new_node
elif (current_node.id[id_index] != new_node.id[id_index]):
current_node.left = new_node
new_node.parent = current_node
def printtree(self, node=None, level=0, lr = ''):
if (node == None):
node = self.root
print (lr, level, node)
if (node.left != None):
self.printtree(node.left, level+1, 'L')
if (node.right != None):
self.printtree(node.right, level+1, 'R')
if __name__ == "__main__":
t = Tree()
t.add('0000','test')
t.add('0100','test')
t.add('0010','test')
t.add('0001','test')
t.add('0101','test')
t.printtree()
目前我试图做的是找到一个新节点可能是其子节点的叶节点。
谁能帮我弄清楚我到底做错了什么？如果我遗漏了任何需要的东西，我会提前道歉，并欢迎任何关于如何使这篇文章变得更好的建议！
我想我的问题是这样的：
目前我的节点是根据与根节点相同索引的位相矛盾的第一位排序的。相反，我需要做的是对节点进行排序，以便在引导后最右边的节点是您自己的节点。
如果是这种情况，根节点会是什么？有没有办法做到这一点，根节点是您自己的节点，同时仍然保持网络的完整性？
将新节点添加到网络后，我将如何重构树以维护您遍历的分支（每个新分支）代表叶节点 id 中的单个位的规则？最右边的节点是离你最近的节点，最左边的节点是最远的节点。