File Trie.h

↰ Parent directory (ADS/dictionary)

Two digital search trees of strings, beyond the book:

Definition (ADS/dictionary/Trie.h)

Detailed Description

  • Trie, the tree of Fredkin whose node at depth d stands for a prefix of d characters, the children of a node being indexed by the next character (here by a sorted map); a string is there if the node of its last character is marked. A search, an insertion and a removal take :math:` O( m log sigma ) ` time for a string of m characters on an alphabet of sigma, independently of the number of strings, and the strings with a given prefix are those below the node of the prefix, visited in their order;

  • RadixTree, the compact trie (the Patricia of Morrison, on characters rather than on bits), where every chain of nodes with a single child and no mark is merged into one edge labelled by a string, so that it has at most 2 n nodes for n strings, however long they are; an insertion splits an edge where the new string departs from it, and a removal merges back a node left with a single child.

Both map each string to a value, i.e., they are a DICTIONARY [see File ADT.h] whose keys are strings, with keysWithPrefix() besides. The contracts [see File Contract.h]: insert() ensures that the key is there and remove() that it is not; the invariant of RadixTree is that no node but the root has a single child and no mark, and that the labels of the edges out of a node begin with distinct characters. The operations are defined in Trie.tpp.

  1. Fredkin, Trie memory, Communications of the ACM 3(9), 490-499, 1960, doi:10.1145/367390.367400

    1. Morrison, PATRICIA: practical algorithm to retrieve information coded in alphanumeric, Journal of the ACM 15(4), 514-534, 1968, doi:10.1145/321479.321481

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.3

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes