13-3 AVL trees

An AVL tree is a binary search tree that is height balanced: for each node $x$, the heights of the left and right subtrees of $x$ differ by at most $1$. To implement an AVL tree, we maintain an extra attribute in each node: $x.h$ is the height of node $x$. As for any other binary search tree $T$, we assume that $T.root$ points to the root node.

a. Prove that an AVL tree with $n$ nodes has height $O(\lg n)$. ($\textit{Hint:}$ Prove that an AVL tree of height $h$ has at least $F_h$ nodes, where $F_h$ is the $h$th Fibonacci number.)

b. To insert into an AVL tree, we first place a node into the appropriate place in binary search tree order. Afterward, the tree might no longer be height balanced. Specifically, the heights of the left and right children of some node might differ by $2$. Describe a procedure $\text{BALANCE}(x)$, which takes a subtree rooted at $x$ whose left and right children are height balanced and have heights that differ by at most $2$, i.e., $|x.right.h - x.left.h| \le 2$, and alters the subtree rooted at $x$ to be height balanced. ($\textit{Hint:}$ Use rotations.)

c. Using part (b), describe a recursive procedure $\text{AVL-INSERT}(x, z)$ that takes a node $x$ within an AVL tree and a newly created node $z$ (whose key has already been filled in), and adds $z$ to the subtree rooted at $x$, maintaining the property that $x$ is the root of an AVL tree. As in $\text{TREE-INSERT}$ from Section 12.3, assume that $z.key$ has already been filled in and that $z.left = \text{NIL}$ and $z.right = \text{NIL}$; also assume that $z.h = 0$. Thus, to insert the node $z$ into the AVL tree $T$, we call $\text{AVL-INSERT}(T.root, z)$.

d. Show that $\text{AVL-INSERT}$, run on an $n$-node AVL tree, takes $O(\lg n)$ time and performs $O(1)$ rotations.

a. Let $T(h)$ denote the minimum size of an AVL tree of height $h$. Since it is height $h$, it must have the max of it's children's heights is equal to $h - 1$. Since we are trying to get as few nodes total as possible, suppose that the other child has as small of a height as is allowed. Because of the restriction of AVL trees, we have that the smaller child must be at least one less than the larger one, so, we have that

$$T(h) \ge T(h - 1) + T(h - 2) + 1,$$

where the $+1$ is coming from counting the root node.

We can get inequality in the opposite direction by simply taking a tree that achieves the minimum number of number of nodes on height $h - 1$ and on $h - 2$ and join them together under another node.

So, we have that

$$T(h) = T(h - 1) + T(h - 2) + 1, \text{ where } T(0) = 0, T(1) = 1.$$

This is both the same recurrence and initial conditions as the Fibonacci numbers. So, recalling equation $\text{(3.25)}$, we have that

$$T(h) = \Big\lfloor \frac{\phi^h}{\sqrt 5} + \frac{1}{2} \Big\rfloor \le n.$$

Rearranging for $h$, we have

$$ \begin{aligned} \frac{\phi^h}{\sqrt 5} - \frac{1}{2} & \le n \\ \phi^h & \le \sqrt 5(n + \frac{1}{2}) \\ h & \le \frac{\lg \sqrt 5 + \lg(n + \frac{1}{2})}{\lg\phi} \in O(\lg n). \end{aligned} $$

b. Let $\text{UNBAL}(x)$ denote $x.left.h - x.right.h$. Then, the algorithm $\text{BALANCE}$ does what is desired. Note that because we are only rotating a single element at a time, the value of $\text{UNBAL}(x)$ can only change by at most $2$ in each step.

Also, it must eventually start to change as the tree that was shorter becomes saturated with elements. We also fix any breaking of the AVL property that rotating may of caused by our recursive calls to the children.

BALANCE(x)
    while |UNBAL(x)| > 1
        if UNBAL(x) > 0
            RIGHT-ROTATE(T, x)
        else
            LEFT-ROTATE(T, x)
            BALANCE(x.left)
            BALANCE(x.right)

c. For the given algorithm $\text{AVL-INSERT}(x, z)$, it correctly maintains the fact that it is a BST by the way we search for the correct spot to insert $z$. Also, we can see that it maintains the property of being AVL, because after inserting the element, it checks all of the parents for the AVL property, since those are the only places it could of broken. It then fixes it and also updates the height attribute for any of the nodes for which it may of changed.

d. Both for loops only run for $O(h) = O(\lg(n))$ iterations. Also, only a single rotation will occur in the second while loop because when we do it, we will be decreasing the height of the subtree rooted there, which means that it's back down to what it was before, so all of it's ancestors will have unchanged heights, so, no further balancing will be required.

AVL-INSERT(x, z)
    w = x
    while w != NIL
        y = w
        if z.key > y.key
            w = w.right
        else w = w.left
    if z.key > y.key
        y.right = z
            if y.left = NIL
                y.h = 1
    else
        y.left = z
        if y.right = NIL
            y.h = 1
    while y != x
        y.h = 1 + max(y.left.h, y.right.h)
        if y.left.h > y.right.h + 1
            RIGHT-ROTATE(T, y)
        if y.right.h > y.left.h + 1
            LEFT-ROTATE(T, y)
            y = y.p