Menu
A complete tree is a tree in which every level is completely filled and an Almost complete tree is a tree in which if last level is not completely filled then all nodes are as far as left as possible. my confusion is in following example of binary tree:
O
/ \
O O
/ \ / \
O O O O
/ \
O O
According to definition it should be an incomplete binary tree but it is a complete binary tree. if someone could elaborate how is this complete binary tree and why not an incomplete binary tree?
512
Almost complete binary tree is a binary tree which satisfies following conditions: Insertion of nodes must takes place level by level and all the nodes must be left justified(i.e. from left to right). All the levels from 1 to n-1 level(n stands for number of levels) should be completely filled without any gap.
A almost complete binary tree is a binary tree in which every level of the tree is completely filled except the last level. Also, in the last level, nodes should be attached starting from the left-most position.
DEFINITION: A max-heap (or simply a heap) is a nearly complete binary tree in which each node contains an ele- ment from a set S with a strict weak ordering, such that: For each node p except the root, element(parent(p)) > element(p).
A balanced binary tree is the binary tree where the depth of the two subtrees of every node never differ by more than 1. A complete binary tree is a binary tree whose all levels except the last level are completely filled and all the leaves in the last level are all to the left side.
Your example is a complete binary tree: a complete binary tree can have an incomplete last level, as long as all the leaves in it are pushed across to the left.
A perfect binary tree is a complete binary tree in which the last level is full.
An almost complete binary tree is a complete but not perfect binary tree. So your example is also almost complete.
The terminology is confusing, but an almost complete binary tree is also complete.
113
Actually, the confusion arises due to reading from different books. The explanation of complete binary tree (i.e. every level except possibly the last, is completely filled and all nodes are as far left as possible) is in some books referred as almost complete binary tree and explanation of FBT takes as explanation of CBT and explanation of strictly BT takes as FBT. They don't have any explanation of strictly binary tree or if it possible they don't have explanation for FBT.
39
Not sure where some of these terms are coming from... the technical terminology for binary trees that I've learned are strictly binary, complete, and almost complete.
Strictly binary trees are binary trees where every node either has two children or is a leaf (has no children).
Complete binary trees are strictly binary trees where every leaf is on the same "maximum" level.
Almost complete binary trees are not necessarily strictly binary (although they can be), and are not complete. If the tree has a maximum level of d, then the subtree containing all the nodes from the root to level d-1 is a complete tree. Additionally, if a node has a right descendant at level d, then its left subtree is a complete tree whose leaves are all at level d (all the "bottom" nodes of the tree are "as far left as possible").
From what I've been taught, the accepted answer would be incorrect in saying that "an almost complete binary tree is also complete." They're not. An almost complete binary tree would be complete if you removed every leaf at the tree's lowest level.
42
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
