Radical Trees

Radical trees are a form of binary tree in which all data is held in leaf nodes. They are searchable but unordered. In contrast to a binary search tree, which is searchable using a comparison relation, a radical tree is searchable using a sequence of bits from the key. This is similar to the difference between comparison-based sorting and radix sort. (They're not called radix trees because that name is already used for another type of tree).

Definition

Internal and leaf nodes are assumed to be distinguishable by external means. Keys are encoded in binary and are all the same length (but they need not be finite). An internal node has two children, child0 and child1, and a bit number, B. The child subtree child0 contains only keys which have the value 0 in bit position B in their keys. Similarly, the child subtree child1 contains only keys which have the value 1 in bit position B in their keys.

Searching

Searching consists of searching subtrees starting with the whole tree. In each subtree there are three cases:

• the subtree is empty. In this case the key does not exist.
• the subtree is a leaf. In this case the key is foudn in the leaf or it does not exist.
• the subtree is an internal node. In this case the search result is the result of searching the child corresponding to the value of bit B in the key.

Insertion

Insertion of a new leaf node is very similar to searching. It consists of finding the correct place to insert and making local modifications. Apply the following insertion to the whole tree:

• if the subtree is empty, return the new node. This can only happen if the whole tree is empty.
• if the subtree is a leaf, create an internal node. Find any bit where the leaf and the new key differ. Set the internal node's value B to the position of this bit. Set child0 and child1 of the internal node to the leaf and the new node such that child0 gets whichever has the value 0 for bit B in its key, and child1 gets the one with value 1. Return the new internal node.
• if the subtree is an internal node, it has one child in which the new node belongs. Return the internal node with that child replaced with the subtree resulting from inserting the new node in it.

Timing

The maximum height of the tree is lg(keylen). All operatons examine a path from the root, so they take O(log(keylen)). Where the keys tend towards being dense in a special sense, the tree will tend towards being well balanced. This is where 'dense' means that where keys differ at a bit position, there are about equal numbers of keys which occur with 0 and 1 at that position. In the special case where every key in a range 0..2^N-1 occurs, then the tree will be a complete balanced tree.