AVL Tree

An AVL Tree is a Binary Search Tree with additional height-balance property at every node: The heights of the left and right subtree differ at most 1.

Convention: height(empty tree) = -1 $T$ AVL if at any node, (height of right subtree) - (height of left subtree )$\in -1,0,1$

• balance(v) = -1 means v is left-heavy
• balance(v) = +1 means right-heavy

We can either store the balance at each node or the height of its subtree.

Theorem

The height of an AVL Tree is always $\Theta (\log n)$ Theorem: An AVL tree on $n$ n nodes has $\Theta (\log n)$ height. $\to$ search, insert, delete all cost $\Theta (\log n)$

Formula

Minimum # nodes in a tree is given by $N(h)=1+N(h-1)+N(h-2)$. Where 1 is the root, $N(h-1)$ is left and $N(h-2)$ is right. So we start with N(0) which is 0, and N(1) is 2, then to find the next one that is N(3) we apply N(0) + N(1) + 1. Always the two previous +1.

Insertion in AVL Tree

Inserting into an AVL Tree is the same as inserting into a Binary Search Tree but it can potentially disrupt the balance so we need to restore the AVL properties by doing [Rotations].

Note

z: unbalanced y: depper child x: deeper child

AVL::insert(k, v):
    z ← BST::insert(k, v) // Insert (k, v) into the AVL tree as a leaf node, returns the node z where k is now stored
    while (z is not NIL):
        if (|z.left.height - z.right.height| > 1):
            // z is imbalanced, we need to perform rotations to restore balance
            y ← taller child of z
            x ← taller child of y
            z ← restructure(x, y, z) // Restructure the tree to restore balance
            // We can argue that we are done here since the tree is balanced now
            break
        setHeightFromSubtrees(z)
        z ← z.parent
 

setHeightFromSubtrees(u)
	u.heigth ← 1 + max{u.left.height, u.right.height}

Restoring the AVL Property: Rotations

There are 4 cases:

AVL Deletion

We do a Binary Search Tree delete.

Pseudocode:

When choosing $x$, we need to choose the one that does the lest amount of rotations. The easier one.

Time complexity of AVL Tree

• search: $O(height)$ total cost
• delete: $O(height)$ total cost
• worst-case for all operations: $\Theta (heigth)=\Theta (\log n)$ $\to$ good for searching unlike Heap (Memory) which is better for inserting and deleting.

Questions

• What is the minimum number of nodes in an AVL tree of height?

• When inserting into an AVL tree, what is the most number of rotations that you will have to perform?

  • 2

• What is the most number of rotations that we will have to perform if we delete from an AVL tree?

  • height of the tree? $\Theta (\log n)$

• What is the rotation needed to correct a right-right imbalance in an AVL tree?

• What is the minimum number of nodes in an AVL tree of height 8?

  • 88

• If you are given all $n$ numbers ahead of time, it is possible to create an AVL tree containing all $n$ numbers in $O(n)$ time.

  • False, why???

• Inserting the same set of $n$ items into an AVL tree will always result in the same AVL tree, regardless of the order they are inserted.

  • False

• An AVL Tree with $n$ nodes always has the minimum height over all BSTs with $n$ nodes.

  • False

• When inserting a key into an AVL Tree, the newly inserted node will always be a leaf after the insertion is complete.

  • False, might be rebalanced through Tree Rotation

• Suppose AVL-Insert calls restructure on a node with balance factor +2, while its right child has balance factor 0. In this case, the imbalance will be fixed by:

  • Invalid. This situation cannot occur.

• Every heap satisfies the AVL height-balance property but not every AVL tree satisfies the heap structure property.

  • True, heap property makes it that it won’t violate height-balance property of AVL trees, but AVL tree does not have the property of ordering elements as heaps. Where the node is bigger than its children for a max-heap for instance.
  • In summary, AVL trees ensure height balance for efficient searching, while heaps maintain a specific structure for efficient extraction of extreme elements.