I'm trying to implement my own Patricia Trie library for learning purposes, so i got stuck when adding some nodes because every single example i got have these strange backwards links that makes no sense to me. What's the point of these links? What's the logic behind it?
I've seen dozens of videos, papers (including the original paper from Edward Fredkin), books (Drozdek, Chapman, Cormen and others) and presentations and i cant get a clue.
Here is the insertion routines i made, ignore the final comments, i was trying to teach myself and fail miserably.
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;
}
So the code seems to be working but i can't understand why and how.
Patricia tries merge internal (branch) and terminal (leaf) nodes into one node type. Terminal nodes are indicated by having a bit to compare that is not later than their parent i.e. they are upward or self links. The sane way to read a graphic of these tries is to follow links (using only the bit and children fields) until you encounter a node comparing a bit that is not a successor. This is the terminal node where you compare the full key. Figuratively, upward links point to terminal nodes and downward links point to internal nodes, with any one particular node fulfilling both roles.
An empty tree has no nodes. A tree with a single item has one root but no bits to compare since there are no other values. So if you had byte values in a big-endian tree compared on bits {7..0}, then the root node would be initialized to compare bit 8, which due to it being 1 to the left of the max bit 7, is the same for all values, i.e. nothing to compare. So let's take a tree having a single root node of 0x00 with bit 8 assumed equal to a leading zero. Then the left(0) child points back to root and the right can remain undefined or null since it will never be used because bit 8 is just a leading zero representing no bits to compare and can never be 1 because a byte has no bit 8.
Now steal root's left(0) field and point it at a child of value 0x40 (64). This byte differs from 0x00 (root) on bit 6. So it marks bit 6 and has the right(1) child pointing back to itself while the left(0) child points back to root 0x00.
"Patricia is a little tricky, and requires careful scrutiny before all of her beauties are revealed." -Donald Knuth.
The best description of this structure is in Sedgwick's "Algorithms in C" first edition. He implements insert for a big ending int tree. You'll notice he uses values that all begin with zero, i.e. the leading 0 (really meaning no bit to compare) is explicit. Just remember these two rules: Root really does contain a value (it is not a nullary root). Only one path away from root is ever used and this directly represents having nothing to compare until you have at least two nodes in the tree.