binary tree

(data structure)

Definition: A tree with at most two children for each node.

Formal Definition: A binary tree either

is empty (no nodes), or
has a root node, a left binary tree, and a right binary tree.

Also known as dyadic tree.

Generalization (I am a kind of ...)
tree, k-ary tree with k=2.

Specialization (... is a kind of me.)
complete binary tree, full binary tree, binary search tree, binary heap, balanced binary tree, threaded tree, Fibonacci tree, extended binary tree.

Note: Formal definition after [CLR90, page 94].

Author: PEB

Implementation

examples, analysis, and code (C). Bro. David Carlson's tutorial and code (C++). Worst-case behavior of traversal, annotated for real time (WOOP/ADA).

More information

Historical Note
An early use of the term "dyadic tree" is in Georgii M. Adelson-Velskii and Evgenii M. Landis, An algorithm for the organization of information, Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259-1263, 1962.
(Doklady is Russian for "Report". Sometimes transliterated in English as Doclady or Dokladi.)

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

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

Entry modified 14 May 2007.
HTML page formatted Mon May 14 10:01:55 2007.

Cite this as:
Paul E. Black, "binary tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 May 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/binarytree.html