Balanced BST

  • Describe what balance property is in the context of BST structure.

For efficiency, we shall restrict the height of a BST so that it is O(lg⁡n)\Omicron(\lg n) instead of the worst-case O(n)\Omicron(n).

Balancing to the rescue: The tree structure is adjusted as necessary to maintain a better balance and resulting height.

A BST is balanced when it has the following property:

For any node, the heights of the node's left and right subtrees are either equal or differ by at most 11.

The above is often referred to as the balance property. Thus, a BST that maintains the balance property is a balanced BST or simply a BBST.