AVL Trees

Agenda

1. The problem with BSTrees ...
2. Formalizing the problem and hoped-for solution
3. Strategy for maintaining a balanced tree
4. Building and Balancing simple trees
5. Formalizing tree rotations
6. Rotation prescriptions

1

... is that they can become very "imbalanced". With pathological (i.e., sorted) input. they can essentially degenerate into linked lists!

Search = O(N)
Insert (requires search) = O(N)
Delete (requires search) = O(N)

2

Need to define "imbalance", and decide when it is and isn't permissible.

• Empty tree = balanced
• Tree with no left/right subtrees = balanced
• Tree with either 1 left or 1 right node = imbalance of +/-1 --- is this ok?
• Tree with left and right subtrees with equal #s of values = ???

Observe: disparity in # of values is not necessarily indicative of imbalance between subtrees!

We are interested in a height-balanced tree, where:

def height(t):
    if not t:
        return 0
    else:
        return 1 + max(height(t.left), height(t.right))

In a strictly height-balanced tree, the left and right subtrees for every node have a height disparity of at most +/-1

In such a tree, Search would be O(lg N)

Note: alternative to height-balanced --> "weight"-balanced (# nodes) ... motivation/implementation?

3

Keyword: MAINTAINING; i.e., not RECONSTRUCTING nor MASSIVELY REPAIRING

i.e., after each operation that can potentially unbalance a tree, we should apply an incremental fix in order to re-balance it.

Q: What operations?
A: Insertion & Deletion

Q: How much taller can a tree get after a single insertion or deletion?
A: 1

Q: So, in a previously balanced tree, how imbalanced can a given node become
after a single insertion or deletion? A: +/-2

Q: What might an "incremental fix" that balances such a node look like?
A: ...

4

Build and, if needed, balance, the trees constructed from the following (ordered) input sequences:

2 1 3 # B
1 2 3 # RR
3 2 1 # LL
1 3 2 # RL
3 1 2 # LR

5

Draw diagrams for right & left rotations (on nodes with subtrees!)

6

Rotation prescriptions (for insertion):

RR => rotate LEFT about root
LL => rotate RIGHT about root
RL => rotate RIGHT about right subtree (to obtain RR), then rotate LEFT about root
LR => rotate LEFT about left subtree (to obtain LL), then rotate RIGHT about root

Et voila: the AVL tree!