Digital search tree & Radix search trie - a brief description

• Searching is based on the binary representation of the search key
• If keys are uniformly distributed, the average time per operation is O(log N)
• Worst case is O(b), where b is the number of bits in the search key
• Some other way is needed to handle duplicates

Digital search tree

Works otherwise like the binary search tree, but branching is based on the bits of the search key.
If we have a key bit(0)bit(1)bit(2)bit(3) (bit(0) is the most significant bit) and we must branch at level k  (root is at level 0) , we
choose left branch if the bit(k) is 0 and the right branch if the bit(k) is 1.

Example: searching the letter E from a digital search tree

Radix Search trie

• All data is stored at leaves.
• Inner nodes of the tree just contain links.
• The form of the trie does not depend on the order of insertions
• Branches of the trie are as long as it takes to make a difference between keys

Searching

1. Start from the root node and from the most significant bit
2. Go forward bit by bit on the trie until you find a leaf node
3. Check if the item is in the leaf node

Insertion

1. Find the place of the item by following bits
2. If there is nothing, just insert the item there as a leaf node
3. If there is something on the leaf node, it becomes a new innernode. Build a new subtree or subtrees to that inner node depending how
   the item to be inserted and the item that was in the leaf node differs.
4. Create new leaf nodes where you store the item that was to be inserted and the item that was originally in the leaf node.

Deletion

1. Remove the item
2. Remove the leaf node where the item was
3. If the nearest sister node is also a leaf node, shorten the tree until the sister node differs only by one bit from some other branch of the tree.

Example: a radix search trie

Example: searching

Example: inserting a key to the trie