我正在尝试实现我自己的 Patricia Trie 库以用于学习目的，所以在添加一些节点时我被卡住了，因为我得到的每个示例都有这些奇怪的反向链接，这对我来说毫无意义。这些链接有什么意义？其背后的逻辑是什么？
我看过几十个视频、论文（包括 Edward Fredkin 的原始论文）、书籍（Drozdek、Chapman、Cormen 等）和演示文稿，但我无法找到线索。
这是我制作的插入例程，忽略最后的评论，我试图自学并惨遭失败。
public void insert(int value) {
int numOfBits = (int) (Math.log(value) / Math.log(2)) + 1;
if (numOfBits > MaxBits) {
System.out.println("Error : Number too large");
return;
}
root = insert(this.root, value);
}
private PatriciaNode insert(PatriciaNode node, int value) {
int differingBitNumber;
String binaryValue, binaryLastNodeValue;
PatriciaNode newNodeGrandma, newNodeParent, lastNode, newNode;
// Tree is empty create the first item
if (node == null) {
node = new PatriciaNode();
node.bitNumber = 0;
node.data = value;
node.leftChild = node;
node.rightChild = null;
return node;
}
// Checks if there is already a node with this value
lastNode = search(node, value);
if (value == lastNode.data) {
System.out.println("Error : key is already present\n");
return node;
}
// There is no value like this stored!!!
// translate values in to the binary
// representations for comparisons
binaryValue = toBinary(value);
binaryLastNodeValue = toBinary(lastNode.data);
// find the first differing bit beetween the binary representations
differingBitNumber = 1;
while (isBit1At(binaryValue, differingBitNumber) == isBit1At(binaryLastNodeValue, differingBitNumber)) {
differingBitNumber++;
}
// going down in the tree in order to find a spot to insert the new node
newNodeParent = node;
newNodeGrandma = node.leftChild; // I known it makes no sense, but after the loop will
while (newNodeGrandma.bitNumber > newNodeParent.bitNumber && newNodeGrandma.bitNumber < differingBitNumber) {
newNodeParent = newNodeGrandma;
// deciding if we should go to the left or to ther right
// bit 1 to right, bit 0 to left
newNodeGrandma = isBit1At(binaryValue, newNodeGrandma.bitNumber) ? newNodeGrandma.rightChild : newNodeGrandma.leftChild;
}
// spot has been found!!
// creating the node
newNode = new PatriciaNode();
newNode.bitNumber = differingBitNumber;
newNode.data = value;
// Doing some circular references, it will be used when we search at tree
// when bitNumberCurrent < bitnumberParent we known we reach the bottom of
// the tree
// my grandma is less than me? Put it on the left otherwise put it on the right
newNode.leftChild = isBit1At(binaryValue, differingBitNumber) ? newNodeGrandma : newNode;
// my grandma is bigger than me? Put it on right otherwise put it on the left
newNode.rightChild = isBit1At(binaryValue, differingBitNumber) ? newNode : newNodeGrandma;
// when using patricia trees the children points
// backwards to grandmas informing if its grandmas
// has bigger or lowers values, when a node has
// a child it must "forget" about your own grandmas
// and points to your new children
if (newNodeGrandma == newNodeParent.leftChild) {
newNodeParent.leftChild = newNode;
} else {
newNodeParent.rightChild = newNode;
}
return node;
}
所以代码似乎正在工作，但我不明白为什么以及如何。