AVL Trees

http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch10.html#QQ1-42-67

Chapter 10
AVL Trees

10.1 Definitions

Named after Adelson, Velskii, and Landis.

Trees of height O(log n) are said to be balanced. AVL trees consist of a special case in which the subtrees of each node differ by at most 1 in their height.

Balanced trees can be used to search, insert, and delete arbitrary keys in O(log n) time. In contrast, height-biased leftist trees rely on non-balanced trees to speed-up insertions and deletions in priority queues.

10.2 Height

Claim: AVL trees are balanced.

Proof. Let N_h denote the number of nodes in an AVL tree of depth h

Nh	> Nh-1 + Nh-2 + 1
	> 2Nh-2 + 1
	> 1 + 2(1 + 2Nh-4)
	= 1 + 2 + 2^2N h-4
	> 1 + 2 + 2^2 + 2^3N h-6
	...
	> 1 + 2 + 2^2 + 2^3 + ... + 2^h/2
	= 2^h/2 - 1

Hence,

2^h/2 - 1	< n
h/2	< log 2(n + 1)
h	< 2 log 2(n + 1)

A more careful analysis, based on Fibonacci numbers theory, implies the tighter bound of 1.44 log ₂(n + 2).

10.3 Rotations

LL
RR
LR
RL
LL & LR LL

10.4 Insertions and Deletions

Insertions and deletions are performed as in binary search trees, and followed by rotations to correct imbalances in the outcome trees. In the case of insertions, one rotation is sufficient. In the case of deletions, O(log n) rotations at most are needed from the first point of discrepancy going up toward the root.

Delete 4
Imbalance at ‘3’ implies a LL rotation with ‘2’
Imbalance at ‘5’ implies a RR rotation with ‘8’.

10.5 Demo Applets

• demo of AVL trees
• demo of AVL trees

10.6 Assignment #4 (due We, Oct 20)

1. Provide an algorithm that, when given a binary search tree, removes in constant space all the nodes from the tree, in ascending order of keys. How much time your algorithm requires? Show the time and space analysis of your algorithm.

2. Provide an algorithm that, when given a binary search tree, removes in linear time all the nodes from the tree, in ascending order of keys. How much space your algorithm requires? Show the time and space analysis of your algorithm.

3. Construct a binary search tree by introducing the following keys in the given order: 1, 2, 7, 6, 3, 4, 5. Then repeatedly use AVL rotations to transform the tree into an AVL tree, while showing all the intermediate trees being created in the process. In each stage, the AVL transformation should be conducted at a discrepancy that is farthest from the root.

[next] [prev] [prev-tail] [front] [up]