patternMinor
Why is Binary Heap never unbalanced?
Viewed 0 times
neverwhyunbalancedheapbinary
Problem
My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?
Solution
You must refer to the definition of a
A
It is by definition that it is never unbalanced. The maximum difference in balance of the two subtrees is
Binary Heap:A
Binary heap is by definition a complete binary tree ,that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.It is by definition that it is never unbalanced. The maximum difference in balance of the two subtrees is
1, when the last level is partially filled with nodes only in the left subtree.Context
StackExchange Computer Science Q#108852, answer score: 5
Revisions (0)
No revisions yet.