Next: , Up: Trie String Key Pointer Value Arrays   [Index]


4.1.2.1 Radix Tree Associative Array

The least refined radix tree associative array is constructed over a path compressed trie. The trie is a character (byte) one, i.e. node selection uses 8 bits. Nodes having a common parent are stored as a sorted array - node selection is binary search derived. The trie is prefix compressed, i.e. common prefixes are stripped from keys and stored only once - it is possible for the data structure representation to require less memory than the sum of the stored key lengths.

The trie cannot store binary keys (strings containing null characters).

General library:

See String Key Pointer Value Array Library.


Next: , Up: Trie String Key Pointer Value Arrays   [Index]