Definition: A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.
Generalization (I am a kind of ...)
complete tree, binary tree.
Specialization (... is a kind of me.)
See also full binary tree, perfect binary tree, extendible hashing, heap.
Note: A complete binary tree has 2k nodes at every depth k < n and between 2n and 2n+1-1 nodes altogether. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with one-based indexing. If child index is greater than the number of nodes, the child does not exist.
Thanks to Adrienne G. Bloss (firstname.lastname@example.org) September 2003.
This kind of tree is called "complete" by authors that mention it (Budd page 332, Ege, Carrano & Prichard page 427, Goodrich & Tamassia page 302, [HS83, page 226], [Knuth97], [Stand98, page 249]). Some authors call perfect binary trees "complete".
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 26 May 2011.
HTML page formatted Thu May 26 15:59:49 2011.
Cite this as:
Paul E. Black, "complete binary tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/completeBinaryTree.html