AVL Trees

Self-balancing Binary Search Tree

Each node has a balance factor, so that the height of the tree only differs by one height.

O(log(N)) height, lookup, insertion, and deletion.

Compared to Red-Black Trees:
• AVL's 1.44 * log(N) height
• better than RBT's 2 * log(n)
• AVL's O(log N) rotations
• worse than O(1) operations

Click here to learn more.