These lecture notes are based on chapter 9 in ``Data Structures, Algorithms, & Software Principles in C'' by Thomas Standish.

Overview

previously - binary search tree analysis
today - balanced binary trees

Rebalancing a binary search tree

Assume we have the following tree.

     5
    /  
   3

Then we insert a 2 into the tree.

Now the tree is the worst case for searching (O(n) rather than O(log n) search).

Should "rebalance" the tree to maintain O(log n) search.

     3
    / \
   2   5

Can rebalance by an inorder traversal to get sorted order, then rebuild the tree by choosing the middle value and inserting it. The inorder traversal in O(n).

So this rebalancing has

O(log n) search
O(n) insertion

AVL Trees

O(log n) search
O(log n) insertion/rebalancing

Definition: The height of a tree is the length of the longest path in the tree.

Definition: A node in a binary tree has the AVL property if the height of the left and right subtrees differ by at most one.

Definition: If every node in the tree has the AVL property then the tree is said to be an AVL tree.

An AVL tree is shown below.

     3
    / \
   2   5

The following is not an AVL tree because node 5 does not have the AVL property.

When AVL property is lost can rebalance via one of four rotations.

single right - A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the left (the left subtree is 2 higher than the right subtree) and B is leftheavy (the left subtree of B is 1 higher than the right subtree of B). T1, T2 and T3 represent subtrees (a node was added to T1 which made B leftheavy and unbalanced A).
```
        A                        B
       / \      ---------->     / \
      B  T3                    T1  A
     / \                          / \
    T1 T2                        T2 T3
```
single left - A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree) and B is rightheavy (the right subtree of B is 1 higher than the left subtree of B). T1, T2 and T3 represent subtrees (a node was added to T3 which made B rightheavy and unbalanced A).
```
        A                        B
       / \      ---------->     / \
      T1  B                    A  T3
         / \                  / \
        T2  T3               T1 T2
```
double right - C is the node that the rotation is performed on. This rotation is performed when C is unbalanced to the left (the left subtree is 2 higher than the right subtree), A is rightheavy (the right subtree of A is 1 higher than the left subtree of A) and B is leftheavy. T1, T2, T3, and T4 represent subtrees (a node was added to T2 which made B leftheavy, made A rightheavy and unbalanced C). This consists of a single left rotation at node A, followed by a single right at node C.
```
        C                         B
       / \      ---------->     /   \
      A  T4                    A     C
     / \                      / \   / \
    T1  B                    T1 T2 T3 T4
       / \
      T2 T3
```
double left - A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree), C is leftheavy (the left subtree of A is 1 higher than the right subtree of A) and B is rightheavy. T1, T2, T3, and T4 represent subtrees (a node was added to T3 which made B rightheavy, made C leftheavy and unbalanced A). This consists of a single right at node C, followed by a single left at node A.
```
        A                         B
       / \      ---------->     /   \
      T1  C                    A     C
         / \                  / \   / \
        B  T4                T1 T2 T3 T4
       / \
      T2 T3
```

AVL-tree node structure

typedef enum {LeftHeavy, Balanced, RightHeavy} BalanceFactorType;

typedef struct AVLTreeNodeTag {
   BalanceFactorType balance_factor;
   KeyType       key;
   struct AVLTreeNodeTag *left;
   struct AVLTreeNodeTag *right;
} AVLTreeNode;

local balance factor adjustments only during rebalancing

examine subtree below, height h=1

insert 1, height h=2, but is unbalanced

rebalance via single right rotation

rebalanced, height h=1
rebalancing is a local adjustment O(log n)
no need to adjust balance factors higher in the tree

Analysis

minimum number of comparisons
- h is height of tree
- can be at most 2**h leaves
- internal nodes are then at most 2**h - 1
- h must be at least as much as the ceiling of log(n + 1)
- so comparisons must be more than 2*ceiling of log(n + 1)
maximum number of comparisons
- fibonacci trees
- number of comparisons are less than 2.88*log(n + 2)-1.66
worst case is at most 44 percent worse than best/optimal case