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).


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 consists of searching subtrees starting with the whole tree. In each subtree there are three cases:


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:


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.