AVL-Trees
AVL Trees / Slide 2
Balance Binary Search Tree
Worst
case height of binary search tree: N-1
Insertion, deletion can be O(N) in the worst case
We
want a tree with small height Height of a binary tree with N node is at least (log N) Goal: keep the height of a binary search tree O(log N) Balanced binary search trees
Examples: AVL tree, red-black tree
AVL Trees / Slide 3
Balanced Tree?
Suggestion 1: the left and right subtrees of root have the same height Suggestion 2: every node must have left and right subtrees of the same height Our choice: for each node, the height of the left and right subtrees can differ at most 1,-1,0.
AVL Trees / Slide 4
AVL Tree
An
AVL (Adelson-Velskii and Landis 1962) tree is a binary search tree in which
for every node in the tree, the height of the left and right subtrees differ by at most 1.
AVL tree AVL property violated here
AVL Trees / Slide 5
AVL Tree with Minimum Number of Nodes
N0 = 1
N1 = 2
N2 =4
N3 = N1+N2+1=7
AVL Trees / Slide 6
Height of AVL Tree
Denote Nh the minimum number of nodes in an AVL tree of height h N0=1, N1 =2 (base) Nh= Nh-1 + Nh-2 +1 (recursive relation) many operations (i.e. searching) on an AVL tree will take O(log N) time
AVL Trees / Slide 7
Insertion in AVL Tree
Basically
follows insertion strategy of binary search tree
But may cause violation of AVL tree property
Restore
the destroyed balance condition if
needed
7 6 6 8
Original AVL tree
Insert 6 Property violated
Restore AVL property
AVL Trees / Slide 8
Some Observations
After an insertion, only nodes that are on the path from the insertion point to the root might have their balance altered
Because only those nodes have their subtrees altered
Rebalance the tree at the deepest such node guarantees that the entire tree satisfies the AVL property
7
6 6 Node 5,8,7 might have balance altered Rebalance node 7 guarantees the whole tree be AVL 8
AVL Trees / Slide 9
Different Cases for Rebalance
Denote
the node that must be rebalanced
Case 1: an insertion into the left subtree of the left child of Case 2: an insertion into the right subtree of the left child of Case 3: an insertion into the left subtree of the right child of Case 4: an insertion into the right subtree of the right child of
Cases
1&4 are mirror image symmetries with respect to , as are cases 2&3
AVL Trees / Slide 10
Rotations
Rebalance
of AVL tree are done with simple modification to tree, known as rotation Insertion occurs on the outside (i.e., left-left or right-right) is fixed by single rotation of the tree Insertion occurs on the inside (i.e., left-right or right-left) is fixed by double rotation of the tree
AVL Trees / Slide 11
Insertion Algorithm
First,
insert the new key as a new leaf just as in ordinary binary search tree Then trace the path from the new leaf towards the root. For each node x encountered, check if heights of left(x) and right(x) differ by at most 1
If yes, proceed to parent(x) If not, restructure by doing either a single rotation or a double rotation
Note:
once we perform a rotation at a node x, we wont need to perform any rotation at any ancestor of x.
AVL Trees / Slide 12
CASE 1
When the AVL property is lost we can rebalance the tree via rotations Single Right Rotation (SRR)
If
Tree is left heavy, and new node is added in left sub-tree as a left or right child, SRR is required for balancing Tree.
A B T3
SRR at A
B T1 A T2 T3
T1 T2
AVL Trees / Slide 13
CASE 4
Single
If
Left Rotation (SLR)
Tree is right heavy, and new node is added in left sub-tree as a left or right child, SRR is required for balancing Tree.
A T1 B
SLR at A A
B T3
T2 T3
T1 T2
AVL Trees / Slide 14
CASE 2
Double
Left Rotation (DLR)
If Tree is left heavy, and new node is added in right-tree as a left or right child, double rotation needed 1st SLR and then 2nd SRR is required for balancing Tree.
C A
A is balanced
SLR at A T4 B
C T4
SRR at C A
B C
T1 B
T2 T3
T3
T1 T2 T3 T4
DLR = SLR + SRR
T1 T2
Intermediate step, get B
AVL Trees / Slide 15
CASE 3
Double
Right Rotation (DRR)
If Tree is right heavy, and new node is added in left sub-tree as a left or right child, double rotation needed 1st SRR and then 2nd SLR is required for balancing Tree.
A T1 C
SRR at C
A T1 B
SLR at A A
B C
T4
T2 C
T3 T4
T1 T2 T3 T4
DRR = SRR + SLR
T2 T3
AVL Trees / Slide 16
Insertion Analysis
Insert
logN
the new key as a new leaf just as in ordinary binary search tree: O(logN) Then trace the path from the new leaf towards the root, for each node x encountered: O(logN)
Check height difference: O(1) If satisfies AVL property, proceed to next node: O(1) If not, perform a rotation: O(1)
The
insertion stops when
A single rotation is performed Or, weve checked all nodes in the path
Time
complexity for insertion O(logN)
AVL Trees / Slide 17
Deletion from AVL Tree
Delete
a node x as in ordinary binary search
tree
Note that the last (deepest) node in a tree deleted is a leaf or a node with one child
Then
trace the path from the new leaf towards the root
For each node x encountered, check if heights of left(x) and right(x) differ by at most 1. If yes, proceed to parent(x) If no, perform an appropriate rotation at x
Continue to trace the path until we reach the root
AVL Trees / Slide 18
Deletion Example 1
20 10 5 15 18 25 35 40 45 50 Delete 5, Node 10 is unbalanced Single Rotation 10 15 18 25 20 35 40 45 50
30 38
30 38
AVL Trees / Slide 19
Contd
20 15 10 18 25 35 40 45 10 15 18 20 25 30 35 40 38 45 50
30 38
50 Continue to check parents Oops!! Node 20 is unbalanced!!
Single Rotation
For deletion, after rotation, we need to continue tracing upward to see if AVL-tree property is violated at other node. Different from insertion!
AVL Trees / Slide 20