Problem 13.3

AVL Trees

An AVL tree is a binary search tree that is heigh 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.

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

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 BALANCE(x), which takes a subtree rooted at $x$ whose left and right children are height balanced and have height 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. (Hint: Use rotations).

Using part (b), describe a recursive procedure 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 TREE-INSERT from Section 12.3, assume that $z.key$ has already been filled in and that $z.left = \mathrm{NIL}$ and $z.right = \mathrm{NIL}$; also assume that $z.h = 0$. Thus, to insert the node $z$ into the AVL tree $T$, we call AVL-INSERT(T.root, z).

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

a. number of nodes and height

Let $N_h$ be a lower bound of the number of nodes in an AVL tree with height $h$.

When $h = 1$, we have that $N_1 = 1$ (there is a single root node in the tree). Let's also have $N_0 = 0$.

Let's look at $N_h$ more generally. We know two facts:

The taller subtree will have height $h - 1$ (otherwise we're not calculating heights correctly).
The other subtree will have height at least $h - 2$ (otherwise the AVL invariant will be broken).

This yields the following recurrence:

$$ N_h \ge N_{h-1} + N_{h-2} $$

This is the well-known Fibonnaci sequence. This means, that if a tree has height $h$, then it will have at least $F_h$ nodes.

Now let's use this fact to establish a bound on a tree with $n$ nodes. Let's find an $i$ such that $F_i \le n < F_{i+1}$. We know the height of the tree must be less than $i + 1$, otherwise the tree would have at least $F_{i+1} > n$ nodes. Since $F_i = \Theta(\phi^i)$, we have:

$$ n = \Theta(\phi^h) $$

And taking the logarithm of both sides (and skipping some formal rigour):

$$ h = \Theta(\lg n) $$

b. balance procedure

Refer to the Python code below for some details. Here's a high-level summary.

There are four different cases in which we need to perform rotations when the tree is not balanced:

(A)   3      (B)   3     (C)  1        (D)  1
    /            /              \             \
  2            1                  2             3
 /              \                  \           /
1                2                  3         2

The later two are symmetrical to the former two. In both cases, the bottom node is the inserted one, and the top node is the one with the inbalance (height = 2 in one subtree, and height = 0 in the other). We need to perform one or two rotations in order to get a balanced tree.

(A) Performing a right rotation on the root is enough to balance the tree
(B) We need to perform a left-right rotation, that is, we need to rotate the middle node left, which reduced the tree to the one in (A), and then perform a left rotation
(C) Symmetrically, we just perform a right left rotation
(D) In a similar fashion, we perform a right-left rotation

Note that once we make the rotation, the height of the taller subtree gets reduced by one, and the height of the shorter gets increased by one. This leaves the root of the subtree with an unchanged height. Since the root's height remains unchanged, the rest of the tree won't need any additional rotations.

c. the `AVL-INSERT` procedure

We insert a node in the standard way, and then we traverse the ancestors, updating the heights, until we find a imbalance. Then we perform one or two rebalancing rotations, and the tree is once again balanced.

Refer to the Python code for more detail.

d. Running time

Insertion needs to

descend through the tree, to find where to insert the node, in $\O(\lg n)$ time;
go back the ancestors, and update the heights, in $\O(\lg n)$ time;
perform a one or two balancing rotations if it encounters an imbalance, in $\O(1) time

Python code

from collections import deque


class Node:
    def __init__(self, key, height=-1, left=None, right=None):
        self.key = key
        self.height = height
        self.left = left
        self.right = right

    def __str__(self):
        def dump(node):
            if not node:
                return "NIL"
            else:
                return f"/{node.height}/({node.key}, {dump(node.left)}, {dump(node.right)})"

        return dump(self)

    def left_rotate(self):
        child = self.right
        assert(child)
        self.right = child.left
        child.left = self

        self.height = 1 + max(height(self.left), height(self.right))
        child.height = 1 + max(height(child.left), height(child.right))

        return child

    def right_rotate(self):
        child = self.left
        assert(child)
        self.left = child.right
        child.right = self

        self.height = 1 + max(height(self.left), height(self.right))
        child.height = 1 + max(height(child.left), height(child.right))

        return child

    __repr__ = __str__


def height(node):
    return node.height if node else 0


class AVL:
    def __init__(self):
        self.root = None

    def __str__(self):
        if not self.root:
            return "NIL"
        else:
            return str(self.root)

    __repr__ = __str__

    def nodes(self):
        if not self.root:
            return

        remaining = deque()
        remaining.append(self.root)

        while remaining:
            node = remaining.popleft()
            if node.left:
                remaining.append(node.left)
            if node.right:
                remaining.append(node.right)
            yield node

    def insert(self, key):
        def insert_node(subtree, node):
            if not subtree:
                return node
            elif node.key < subtree.key:
                subtree.left = insert_node(subtree.left, node)
            else:
                subtree.right = insert_node(subtree.right, node)

            subtree.height = 1 + max(height(subtree.left), height(subtree.right))

            balance = height(subtree.left) - height(subtree.right)

            if balance < -1:
                if key < subtree.right.key:
                    subtree.right = subtree.right.right_rotate()
                return subtree.left_rotate()
            elif balance > 1:
                if key > subtree.left.key:
                    subtree.left = subtree.left.left_rotate()
                return subtree.right_rotate()
            else:
                return subtree

        new = Node(key, height=1)
        self.root = insert_node(self.root, new)

    def search(self, key):
        node = self.root

        while node:
            if node.key == key:
                return node
            elif key < node.key:
                node = node.left
            else:
                node = node.right

        return None