Balanced Binary Search trees

As previously discussed, a binary tree which is highly imbalanced may require $O(n)$ time to perform an operation, where $n$ is the number of nodes. This section provides an example of binary search tree with additional constraints that ensure that every node has depth $O(\log n)$.

Height constraints

Rotation

Double Rotation

Worst case depth