Patricia Trees Demystified
Patricia Tree Insert Algorithm
Definitions: Record key: the key, in our tree, is a sequence of bits, numbered from right to left (least significant to most significant)
a checkbit is the place value of the bit which should be checked when a node is visited. The least significant bit would be checkbit zero, the next bit up checkbit one, etc.
The current node is the node that you are currently visiting.
Step one: Traverse down the tree until you find a "leaf"
Check for "leaf":
Two possible cases:
You find the "dummy"
The checkbit for the current node is NOT LESS than the checkbit of the last node visited
If not yet a leaf, check the bit value of the new record key at the checkbit location. You do not check the new record's entire key, nor do you worry about the value of the current node's key. You only need to check that one bit from the new record's key.
If that bit is a zero, go down the tree in the zero (usually left) direction
If that bit is a one, go down the tree in the one (usually right) direction
Step two: Find the first different bit
When you reach a leaf, whether the dummy or otherwise, use the whole key of the new record and the whole key of the node you are at (the dummy value is 0) to find the highest order bit that is different. That is, starting at the most significant bit, compare that bit of the two keys. If they are the same, move on to the next most significant bit and compare them, until you find a bit in which the two keys differ. Record this place as the "checkbit" for your new record's node. If there is no difference, the new record is the same as the current node's record, and the new record cannot be inserted (duplicate error)
Step three: Go back up the tree to find correct inset location
When the checkbit for the new record is less than the checkbit for the current node, the new node containing the new record will be inserted below the current node.
If the checkbit for the new record is not less that the checkbit for the current node, continue up the tree to the parent of the current node.
Step four: Reset children
When you find the correct place to insert the new record's node, the new node will be set as the child of the current node, in the direction of the path that you traversed back up (which is the same as the path you traversed down.) For example, if you just came back up from the current node's zero child, the new record's node will be the current node's new zero.
The current node's displaced child (the one the new node is replacing) will become a child of the new node, the direction (zero or one) based on the checkbit of the NEW node.
The new node will always have itself as one of its children, whether the zero or one depending on the value of the key's bit at the checkbit place. The other child will be the former child of the current node (the displaced child of the parent of the new node.) For example, if the new node record's key has a zero at the checkbit place, the nodes zero child will point to itself. The one will then point to the old child of the parent of the new node (the displaced one from the node you just inserted the new node below.) Note that the displaced link could have been a zero or a one, based on values at the old node's checkbit, but it now will reflect values at the new node's checkbit, not the old node's.