(data structure)
Definition:Abinary tree in which everylevel (depth), except possibly the deepest, is completely filled. At depth n, theheight of the tree, allnodes must be as far left as possible.
Generalization (I am a kind of ...)
complete tree,binary tree.
Specialization (... is a kind of me.)
binary heap,perfect binary tree.
See alsofull binary tree,extendible hashing,heap.
Note:A complete binary tree has 2k nodes at everydepth k < n and between 2n and 2n+1-1 nodes altogether. It can be efficiently implemented as anarray, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with1-based indexing. If child index is greater than the number of nodes, the child does not exist.
After LK.
Thanks to Adrienne G. Bloss ([email protected]) 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 callperfect binary trees "complete".
Author:PEB
If you have suggestions, corrections, or comments, please get in touchwithPaul Black.
Entry modified 16 November 2016.
HTML page formatted Wed Oct 30 12:15:30 2024.
Cite this as:
Paul E. Black, "complete binary tree", inDictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 16 November 2016. (accessed TODAY)Available from:https://www.nist.gov/dads/HTML/completeBinaryTree.html