AVL Trees

Binary Search Tree - Best

Time
• All BST operations are O(d), where d is
tree depth
• minimum d is d = ⎣log2N⎦ for a binary tree
with N nodes
› What is the best case tree?
› What is the worst case tree?
• So, best case running time of BST
operations is O(log N)
 Binary Search Tree - Worst
Time
• Worst case running time is O(N)
› What happens when you Insert elements in
ascending order?
• Insert: 2, 4, 6, 8, 10, 12 into an empty BST
› Problem: Lack of “balance”:
• compare depths of left and right subtree
› Unbalanced degenerate tree
Balanced and unbalanced BST
1 4
2 2 5
3
1 3
4
4 Is this “balanced”?
5
2 6 6

1 3 5 7 7
Approaches to balancing trees
• Don't balance
› May end up with some nodes very deep
• Strict balance
› The tree must always be balanced perfectly(might
not be possible in many cases.)
• Pretty good balance
› Only allow a little out of balance(gives O(log(n) as
we’ll prove.)
• Adjust on access
› Self-adjusting
 Balancing Binary Search
Trees
• Many algorithms exist for keeping
binary search trees balanced
› Adelson-Velskii and Landis (AVL) trees
(height-balanced trees)
› Splay trees and other self-adjusting trees
› B-trees and other multiway search trees
 Perfect Balance
• Want a complete tree after every operation
› tree is full except possibly in the lower right
• This is expensive
› For example, insert 2 in the tree on the left and
then rebuild as a complete tree
6 5
Insert 2 &
4 9 complete tree 2 8

1 5 8 1 4 6 9
 AVL - Good but not Perfect
Balance
• AVL trees are height-balanced binary
search trees
• Balance factor of a node
› height(left subtree) - height(right subtree)
• An AVL tree has balance factor
calculated at every node
› For every node, heights of left and right
subtree can differ by no more than 1
› Store current heights in each node
 Height of an AVL Tree
• N(h) = minimum number of nodes in an
AVL tree of height h.
• Basis
› N(0) = 1, N(1) = 2
h
• Induction
› N(h) = N(h-1) + N(h-2) + 1
• Solution (recall Fibonacci analysis)
h-2
› N(h) > φh (φ ≈ 1.62) h-1
 Height of an AVL Tree
• N(h) > φh (φ ≈ 1.62)
• Suppose we have n nodes in an AVL
tree of height h.
› n > N(h) (because N(h) was the minimum)
› n > φh hence logφ n > h (relatively well
balanced tree!!)
› h < 1.44 log2n (i.e., Find takes O(logn))
 Node Heights
Tree A (AVL) Tree B (AVL)
height=2 BF=1-0=1 2
6 6
1 0 1 1
4 9 4 9
0 0 0 0 0
1 5 1 5 8

height of node = h
balance factor = hleft-hright
empty height = -1
 Node Heights after Insert 7
Tree A (AVL) Tree B (not AVL)
balance factor
2 3 1-(-1) = 2
6 6
1 1 1 2
4 9 4 9
0 0 0 0 0 1 -1
1 5 7 1 5 8
0
7
height of node = h
balance factor = hleft-hright
empty height = -1
 Insert and Rotation in AVL
Trees
• Insert operation may cause balance factor
to become 2 or –2 for some node
› only nodes on the path from insertion point to
root node have possibly changed in height
› So after the Insert, go back up to the root
node by node, updating heights
› If a new balance factor (the difference hleft-
hright) is 2 or –2, adjust tree by rotation around
the node
 Single Rotation in an AVL
Tree
2 2
6 6
1 2 1 1
4 9 4 8
0 0 1 0 0 0 0
1 5 8 1 5 7 9
0
7
 Insertions in AVL Trees
Let the node that needs rebalancing be α.

There are 4 cases:

Outside Cases (require single rotation) :
1. Insertion into left subtree of left child of α.
2. Insertion into right subtree of right child of α.
Inside Cases (require double rotation) :
3. Insertion into right subtree of left child of α.
4. Insertion into left subtree of right child of α.
The rebalancing is performed through four
separate rotation algorithms.
 AVL Insertion: Outside Case
Consider a valid
AVL subtree
j

k h

h
h
Z
X Y
AVL Insertion: Outside Case
j Inserting into X
destroys the AVL
property at node j
k h

h+1 h Z
Y
X
AVL Insertion: Outside Case
j Do a “right rotation”

k h

h+1 h Z
Y
X
 Single right rotation
j Do a “right rotation”

k h

h+1 h Z
Y
X
Outside Case Completed
“Right rotation” done!
k (“Left rotation” is mirror
symmetric)

h+1
j
h h

X Y Z
AVL property has been restored!
 AVL Insertion: Inside Case
Consider a valid
AVL subtree
j

k h

h h Z
X Y
 AVL Insertion: Inside Case
Inserting into Y
destroys the j Does “right rotation”
restore balance?
AVL property

k
at node j h

h h+1 Z
X
Y
AVL Insertion: Inside Case

k “Right rotation”
does not restore
balance… now k is
h j out of balance

X h+1
h

Z
Y
 AVL Insertion: Inside Case
Consider the structure
of subtree Y… j
k h

h h+1 Z
X
Y
 AVL Insertion: Inside Case
Y = node i and
subtrees V and W
j
k h

h
i h+1 Z
X h or h-1

V W
AVL Insertion: Inside Case
j We will do a left-right
“double rotation” . . .

k
i Z
X
V W
Double rotation : first rotation
j left rotation complete

i
k Z
W
X V
Double rotation : second
rotation
j Now do a right rotation

i
k Z
W
X V
 Double rotation : second
rotation
right rotation complete

Balance has been

i restored

k j
h h
h or h-1

X V W Z
Example of Insertions in an
AVL Tree
2
20 Insert 5, 40
0 1
10 30
0 0
25 35
 Example of Insertions in an
AVL Tree
2
3
20 20
1 1 1 2
10 30 10 30
0 0 0 1
0 0
5 25 35 5 25 35
0
40
Now Insert 45
Single rotation (outside case)
3
3
20 20
1 2 1 2
10 30 10 30
0 0 2
0 0
5 25 35 5 25 40 1
0 0
35 45
Imbalance 1 40

0 45 Now Insert 34
Double rotation (inside case)
3
3
20 20
1 3 1 2
10 30 10 35
0 0 2
0 1
5 Imbalance 25 40 5 30 40 1
0
1 0 25 34 45
35 45 0
Insertion of 34 0
34
 Deletion in BST
There are 3 cases.
1. Node to be deleted is a leaf-simply
remove the node.
2. When node has only one child-attach
the child to the parent.
3. When the node to be deleted has 2
children-
Delete 12
Delete 15
Delete 15
1. Copy the contents of inorder successor
of the node and delete it.
 AVL Tree Deletion
• Similar but more complex than insertion
› Rotations and double rotations needed to
rebalance
› Imbalance may propagate upward so that
many rotations may be needed.
Removing a node from an AVL tree may
cause more than one AVL imbalance
– Like insert, delete must check after it has
been successfully called on a child to see if it
caused an imbalance
– Unfortunately, it may cause multiple
imbalances that must be corrected
• Insertions will only cause one imbalance that must
be fixed
 Deletion
Consider the following AVL tree
Suppose we delete the front node: 1
While its previous parent, 2, is not unbalanced, its
grandparent 3 is
– The imbalance is in the right-right subtree
 Erase
We can correct this with a simple balance
 Erase
Recursing to the root, however, 8 is also unbalanced
– This is a right-left imbalance
 Erase
Promoting 11 to the root corrects the imbalance
 Erase
At this point, the node 11 is balanced
 Erase
Still, the root node is unbalanced
– This is a right-right imbalance
 Erase
Again, a simple balance fixes the imbalance
 Erase
The resulting tree is now AVL balanced