Digital and Radix trees improve search efficiency by decreasing the work done for key comparisons.

Digital / Radix search: use the binary representation of the keys and compare the bits one by one until a difference is found. Branch in the tree by comparing the key’s bits, not the keys as a whole.

Digital and Radix trees are used when the keys are long. The longest path is no longer than the length of the binary representation.

Advantages: Reasonable worst-case performance - the longest path is equal the length of the bit representation of the keys

Disadvantages:Dependent on computer’s architecture – difficult to do efficient implementations in some high-level languages

Methods:

1. Digital Search Trees
2. Radix Search Tries
3. Multiway Radix Searching

1. Digital Search Trees

Similar to binary tree search.

Difference: Branch in the tree by comparing the key’s bits, not the keys as a whole.

Example:



A 00001     C 00011    D 00100    E 00101    L 01100   M 01101     
N 01110	   O 01111    P 10000    R 10010    T 10100   U 10101

The above figure represents a tree built by inserting keys into an initially empty tree

Inserting V = 10101 is done in the following way:

• go right (rightmost bit is 1) - node is occupied
• go left (second bis is 0) - node is occupied
• go right (third bit is 1) - node is occupied
• go left (fourth bis is 0) - external node, attach V to the left of T

Search and insertion requires about logN comparisons on the average
and b comparisons in the worst case in a tree built from N random b-bit keys. No path will ever be longer than the number of bits in the keys

Advantages:

1. The depth of the tree is limited by the number of the bits in the representation
2. Only part of the key (the leading bits) is compared.

Disadvantages: If the keys are long, digital search trees have low efficiency,
because the entire key is stored.

Solution: Radix search tries

2. Radix Search Tries

Idea: : do not store keys in the tree at all, the keys are in the external nodes of the tree.
(Note that the term "trie" is used instead of "tree". "trie" comes from "retrieve".)

Two types of nodes:

Internal: contain only links to other nodes
External : contain keys and no links

To insert a key:

• go along the path described by the leading bit pattern of the key
• store the key in the external node at the end of the path.

1. it does not contain a key – store there the new key
2. it contains a key – replace the external node by an internal node
   linked to two new external nodes - one for the new key and one for the old key

NOTE: insertion does not depend on the order of the keys.

To search for a key:

• branch according to key's bits
• don’t compare the key to anything, until an external node is reached
• one full key comparison at the external node completes the search.

If the keys have several bits equal, more internal nodes are necessary

Examples:



A  00001
S  10011
E  00101
R  10010
C  00011

Inserting H 01000, empty external node.



Inserting I 01001, occupied external node.



Complexity: about logN bit comparisons in average case and b bit comparisons
in the worst case in a tree built from N random b-bit keys.

The height of the tree is limited by the number of the bits in the keys.
If we have larger keys – the height increases.

One way to overcome this deficiency is using a multiway radix tree searching.

3. Multiway radix tree

Instead of one bit, several bits are used for branching (most often 2)
If m bits are examined at a time – the search is speeded up by a factor of 2^m .

Problem: if m bits at a time, the nodes will have M = 2^m links.
This may result in considerable amount of wasted space due to unused links.

Example:

If two bits are used, each node will have 4 links.



Search – take left, right or middle links according to the first two bits.
Insert – replace external node by the key (E.G. insert T).

Wasted space – due to the large number of unused links.
Worse if M gets higher.

Running time: log_MN – very efficient.