Balanced BST

For efficiency, we shall restrict the height of a BST so that it is $O(\lg n)$ instead of the worst-case $O(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. A BST that maintains the balance property is a balanced BST or simply a BBST.