HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is Binary Heap never unbalanced?

Submitted by: @import:stackexchange-cs··
0
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 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.