right-threaded tree

(data structure)

Definition: A variant of a threaded tree in which only the right thread, i.e. link to the successor, of each node is maintained.

Generalization (I am a kind of ...)
threaded tree.

See also binary search tree.

Note: Keeping only the right thread, rather than both left and right threads, keeps it quick to find the next greater key and faster to insert and delete.

Author: PEB

Implementation

Ben Pfaff's explanations and code (C)

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 23 May 2011.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "right-threaded tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 23 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/rightThreadedTree.html