AVL Tree

Download as ppt, pdf, or txt
Download as ppt, pdf, or txt
You are on page 1of 36

AVL Tree

1
Height of a tree
• Max number of nodes in path from root to any leaf
 Height(empty tree) = 0
 height(a leaf) = ?
 height(A) = ? A

 Hint: it's recursive!


A.left A.right
 height(a leaf) = 1
 height(A) = 1 + max(
height(A.left), height(A.right))

2
Some height numbers

• For binary tree of height h: root

 max # of leaves: 2h-1


15
 max # of nodes: 2h - 1
8 20
 min # of leaves: 1

 min # of nodes: h
2 14 18 21

3
Trees and balance
• Disadvantage(BST) : height can be N-1

• Worst Case insertion and deletion : O(N) time

• We want a tree with small height

1
“Not balanced” 4
2
3
2 5
4
“Balanced”
4
5 1 3
2 6
6
Is this “balanced”?
1 3 5 7 7

binary tree is said to be balanced if for every node, height of its children differ by at most one
4
AVL trees - Adelson-Velsky & Landis
• AVL tree is a self balanced binary search tree.

• binary search tree + balanced tree

• Balanced binary tree : Difference between the heights of


left and right subtrees of every node in the tree is either -1,
0 or +1.

• Every node maintains a extra information known as balance


factor.

• 1962 - Introduced by Adelson-Velsky and Landis.

5
AVL tree examples
• Two binary search trees:
 (a) an AVL tree
 (b) not an AVL tree (unbalanced nodes are darkened)

An AVL tree is a balanced binary search tree with balance factor of every node is either -1, 0 or +1.

Balance factor = Height of Left Subtree – Height of Right Subtree


6
AVL trees
Every AVL Tree is a binary search tree but all the Binary Search Trees need not to be AVL trees

7
AVL Tree Rotations
• After performing every operation like insertion and deletion
we need to check the balance factor of every node in the
tree.

• If every node satisfies the balance factor condition then we


conclude the operation otherwise we must make it
balanced.

• Rotation operations are used to make a tree balanced.

8
AVL Rotations
Rotation is the process of moving the nodes to either left or right to make tree balanced.

9
Single Left Rotation (LL Rotation)
Every node moves one position to left from the current position.

10
Single Right Rotation (RR Rotation)
Every node moves one position to right from the current position

11
Left Right Rotation (LR Rotation)
• Combination of single left rotation followed by single right rotation.
• First every node moves one position to left then one position to right from the
current position

12
Right Left Rotation (RL Rotation)
• Combination of single right rotation followed by single left rotation.
• First every node moves one position to right then one position to left from
the current position

13
Operations on an AVL Tree
• Insertion/Deletion

• Step 1: Insert/delete new element into tree using BST insertion

• Step 2: check the Balance Factor of every node

• Step 3: If the Balance Factor of every node is more then step4

• Step 4: Perform the suitable Rotation to make it balanced.

14
Insertion

15
Insertion

16
Insertion

17
Insertion

18
Insertion

19
Insertion

20
Insertion

21
Initial AVL tree with balance factors:

0 57

0 26 +1 72

-1 25 0 38 0 63 -1 94

0 3 0 37 0 47 0 78

Balance ok

22
Insert 1 and recalculate balance factors

-1 57

-1 26 +1 72

-2 25 0 38 0 63 -1 94

-1 3 0 37 0 47 0 78

0 1

Balance not ok
(Balance factor of -2 is not allowed)

23
-1 57

-1 26 +1 72

Left Left Case


-2 25 0 38 0 63 -1 94
Pivot

-1 3 0 37 0 47 0 78

0 1

Balance not ok

24
0 57

0 26 +1 72

0 3 0 38 0 63 -1 94

0 1 0 25 0 37 0 47 0 78

Balance ok

25
Insert 30 and recalculate balance factors

-1 57

+1 26 +1 72

0 3 -1 38 0 63 -1 94

0 1 0 25 -1 37 0 47 0 78

0 30

Balance ok

26
Insert 32 and recalculate balance factors

-2 57

+2 26 +1 72

0 3 -2 38 0 63 -1 94

0 1 0 25 -2 37 0 47 0 78

+1 30

0 32

Balance not ok

27
-2 57

+2 26 +1 72

0 3 -2 38 0 63 -1 94

0 1 0 25 -2 37 0 47 0 78

+1 30
Left Right Case
0 32

Balance not ok

28
-2 57

+2 26 +1 72

0 3 -2 38 0 63 -1 94

0 1 0 25 -2 37 0 78
0 47

-1 32

0 30

Balance not ok

29
-1 57

+1 26 +1 72

0 3 -1 38 0 63 -1 94

0 1 0 25 0 32 0 47 0 78

0 30 0 37

Balance ok

30
Insert 35 and recalculate balance factors

-2 57

+2 26 +1 72

0 3 -2 38 0 63 -1 94

0 1 0 25 +1 32 0 47 0 78

0 30 -1 37

0 35

Balance not ok
31
-2 57

+2 26 Start from first spot (from +1 72


bottom of tree) where
balance factor is incorrect.

0 3 -2 38 0 63 -1 94

0 1 0 25 +1 32 0 47 0 78

0 30 -1 37
Left Right Case

0 35

Balance not ok

32
-2 57

+2 26 +1 72

0 3 -2 38 0 63 -1 94

0 1 0 25 -2 37 0 47 0 78

0 32

0 30 0 35

Balance not ok
33
-1 57

+1 26 +1 72

0 3 0 37 0 63 -1 94

0 1 0 25 0 32 +1 38 0 78

0 30 0 35 0 47

Balance ok
34
-1 57

+1 26 +1 72

0 3 0 37 0 63 -1 94

0 1 0 25 0 32 +1 38 0 78

0 30 0 35 0 47

Balance ok

Exercise: insert 36
35
Remove 24 and 20 from the AVL tree.

13 13

10 24 10 20

7 20 30 7 15 30

15 25 36 25 36

13 13

10 30 10 15

7 15 36 7 30

25 25 36

36

You might also like