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.

  1. 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.)
  2. 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).
  3. 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).
  4. 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:

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.

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

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"
                return f"/{node.height}/({node.key}, {dump(node.left)}, {dump(node.right)})"

        return dump(self)

    def left_rotate(self):
        child = self.right
        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
        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"
            return str(self.root)

    __repr__ = __str__

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

        remaining = deque()

        while remaining:
            node = remaining.popleft()
            if node.left:
            if 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)
                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()
                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
                node = node.right

        return None