File ThreadedTree.h

↰ Parent directory (ADS/tree)

The threaded binary search tree of Perlis and Thornton, beyond the book: a missing left child is replaced by a link (a thread) to the predecessor in symmetric order, and a missing right child by a thread to the successor, a bit of each node telling a child from a thread; the symmetric visit then needs neither a stack nor the recursion, the successor of a node being its right thread or the leftmost node of its right subtree (Algorithm 2.3.1S), in O( 1 ) amortized time each.

Definition (ADS/tree/ThreadedTree.h)

Detailed Description

A head node, whose left child is the root and which is the predecessor of the first node and the successor of the last one, closes the threads, as in the representation of Knuth.

The contracts [see File Contract.h]: insert() ensures that the key is there; the invariant is that the visit by threads gives the keys in increasing order, size() of them, an O( n ) check at the level 3. The operations are defined in ThreadedTree.tpp.

    1. Perlis, C. Thornton, Symbol manipulation by threaded lists, Communications of the ACM 3(4), 195-204, 1960, doi:10.1145/367177.367202

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 2.3.1

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes