AVL Search Tree

⚠️ This post was created when I was in high school and is no longer maintained.

(Adel’son-Vel’skii & Landis 1962)

1. Recap tree basics and BST

1. Height of node = length (# edges) of longest downward path to a leaf (see CLRS B.5 for details).

2. BSTs support insert, delete, min, max, next-larger(successor), next-smaller(predecessor), etc. in O(h) time, where h = height of tree (= height of root).

3. Why being balanced matters?

   • Height h is between log~2~n and n

(“The unlucky case”: Build a BST from a sorted array)

- balanced BST maintains `h = O(lg n)` ⇒ all operations run in `O(lg n)` time

---

2. AVL Tree

We want to have as many nodes and smaller height as possible for a tree structure.

2.1 Data structure augmentation

• AVL∈ BST∈ BT
• each node also stores its height (or just difference in heights)
• treat NIL node as height -1

2.2 AVL property

For every node, require the heights of right and left children to differ by at most |1|.

2.3 Worst-case

Worst-case occurs when the height of every node differs by 1. let N_h be the minimum number of nodes in an AVL tree of height h:

Tips:

• 2^{h/2}: the number of times we multiply N_{h-2} by 2 equals the number of times we can subtract 2 from h.
• We can subtract 2 from h exactly h/2 times. ***

3 AVL operations

3.1 Insertion

Loop invariant: (Assume x is the lowest node violating the AVL property and assume x is “too right-heavy”)

• case 1 [same-direction-heavy]: x’s right child is also right-heavy or balanced
  • Rotate x left (LeftRotate(x)): Tips: If X is too right-heavy and X’s right child Y is right-heavy or balanced, then after Left-Rotate(X), X takes Y’s lighter child, so it is no longer too right-heavy. (replace X’s “too heavy” right child Y by Y’s “light child”)
  • Then continue doing so up to x’s grandparent, great grandparent …
• case 2 [Z-shap-heavy]: the heavy child of x (z) leans the opposite way—x’s right child z is left-heavy
  • Rotate z so its heavy child aligns with x’s heavy side (RightRotate(z)).
  • Then rotate x just like in case 1.
  • Then continue doing so up to x’s grandparent, great-grandparent . . .

AVL insertion steps sum up:

1. insert new node using an algorithm for BST
2. identify the lowest unbalanced node on the path from the new node to the root
3. rebalance that node using a single or double rotation then the balance is restored
4. At most one rebalance step is needed; insertion runs in O(log n)

Tips:

• XXRotate(node) adds a layer to the lighter branch. If x is too right-heavy, after LeftRotate(x) its left branch gains a layer from the heavy side, so x is no longer right-heavy.
• To fix the Z-shape-unbalance case, first convert it into a same-direction-unbalance case.
• RightRotate(Z) makes the left-heavy AVL tree rooted at Z become right-heavy (or too right-heavy) at Y. Then LeftRotate(X) lets X take Y’s lighter children.

---

Examples:

3.2 Removal

Steps:

• remove node using the algorithm for BST
• consider the first unbalanced node on the path from the removed node upwards
• rebalance by considering the ‘heaviest child’ of the unbalanced node
• then, if necessary, consider the next unbalanced node and iterate rebalancing
• 6 possible cases of unbalanced nodes after update:

ps. we do not need more rules for rebalancing because removal is in O(log n)

3.3 Final notes concerning the differences between the insertion and removal operations

The removal operation in an AVL is generally much more hassle than insertion for the following reasons:

• removal will change the height of the tree which will possibly break the AVL property.
• consequently, after removal, checking AVL property in a bottom-up manner is needed;
• then, we recursively rebalance the unbalanced parents;
• therefore, the delete operation per se is in O(logn) and the rebalance operation is also in O(logn), so unlike the insertion which is “purely” in O(logn), it will be more precise to say that the removal is in 2 * O(logn). (Well, asymptotically speaking, this does not really matter)

3.4 Time complexty