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 $\Omicron(\lg n)$ instead of the worst-case $\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 $1$.
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.