Avl

Balanced Search Trees Compiled by :  Surya Prakash Pandit 232/05  Gaurav Gupta 20/05 IIIrd I.T.

Binary Search Trees (reminder)  

Each tree node contains a value. For every node,  



its left subtree contains smaller values, and its right subtree contains larger values.

The time complexity of a search operation is proportional to the tree’s depth.  The good case: If the tree is balanced, then every operation takes O(logn) time.  The bad case: The tree might get very unbalanced. For example, when inserting ordered numbers to the tree, the resulting height will be exactly n. AVL Trees

2

Balanced Search Trees : 

Balanced Tree: A binary tree in which the heights of the two sub trees of every node differ by at most 1. 

Several Varieties  AVL trees  Red-Black trees  B-Trees (used for searching secondary memory)

AVL Trees

3

Balanced Search Trees (Contd…) 

Nodes are added and deleted so that the height of the tree is kept under control.



Insertion and deletion has more work to do, but retrieval never has more than log2 n because height is already controlled in case of retrieval.

AVL Trees

4

AVL Trees : 

Motivation: We want to guarantee O(log n) running time on searching/insertion/deletion operations.



Idea: Keep the tree balanced after each operation.



Solution: AVL (Adelson-Velskii and Landis) trees.



AVL tree property: For every node in the tree, the height of the left and right subtrees differs by at most 1. AVL Trees

5

AVL Trees (Contd…) : 

a BST where each node has a balance factor  

balance factor of a leaf node is 0 balance factor of any node: Height (left subtree) – Height (right subtree)

Insertions or deletions can change the balance factor of one or more nodes.  if a balance factor becomes 2 or -2 the AVL tree must be rebalanced 



It is done by rotating the nodes AVL Trees

6

Some AVL Trees : 0

Balance value

-1

0 0

1 0

-1 0

-1 0

Balance Factor : height( left subtree ) - height( right subtree ) AVL Trees

7

Depth of an AVL tree Theorem: Any AVL tree with n nodes has height than 1.441 log n.

less

Proof: Given an n-node AVL tree, we want to find an upper bound on the height of the tree. Fix h. What is the smallest n such that there is an AVL tree of height h with n nodes? Let Sh be the set of all AVL trees of height h that have as few nodes as possible. AVL Trees

8

Depth of an AVL tree (contd…) Let wh be the number of nodes in any one of these trees. w0 = 1, w1 = 2 Suppose T ∈ Sh, where h ≥ 2. Let TL and TR be T’s left and right sub trees. Since T has height h, either TL or TR has height h-1. Suppose it’s TR. By definition, both TL and TR are AVL trees. In fact, TR ∈ Sh-1 or else it could be replaced by a smaller AVL tree of height h-1 to give an AVL tree of height h that is smaller than T. AVL Trees

9

Depth of an AVL tree (contd…) Similarly, TL ∈ Sh-2. Therefore, wh = 1 + wh-2 + wh-1 . Claim: For h ≥ 0, wh ≥ ϕh , where ϕ = (1 + √5) / 2 ≈ 1.6. Proof: The proof is by induction on h. Basis step: h=0. w0 = 1 = ϕ0. h=1. w1 = 2 > ϕ1. Induction step: Suppose the claim is true for 0 ≤ m ≤ h, where h ≥ 1. AVL Trees

10

Depth of an AVL tree (contd…) Then wh+1 = 1 + wh-1 + wh ≥ 1 + ϕh-1 + ϕh (by the i.h.) = 1 + ϕh-1 (1 + ϕ) = 1 + ϕh+1 (1+ϕ = ϕ2) > ϕh+1 Thus, the claim is true. From the claim, in an n-node AVL tree of height h, n ≥ wh ≥ ϕh (from the Claim) h ≤ log ϕ n = (log n) / (log ϕ) AVL Trees < 1.441 log n

11

AVL trees: During Runtime Search :takes O(log n) time, because height of the tree is always O(log n).  Insertion : O(log n) time because we do a search (O(log n) time), and then we may have to visit every node on the path back to the root, performing up to 2 single rotations (O(1) time each) to fix the tree.  Deletion : O(log n) time. 

AVL Trees

12

AVL Trees: Search, Insertion 

AVL tree Search :is the same as BST Search.



AVL tree Insertion: same as BST insertion, except that we might have to fix the AVL tree after an insert.



These operations will take time O(d), where d is the depth of the node being found/inserted.



What is the maximum height of an n-node AVL tree? AVL Trees

13

AVL Tree : Insertion 

Follow a search path as for a BST



Allocate a node and insert the item at the end of the path (as for BST) 



balance factor of new node is 0

if a balance factor becomes 2 or -2 perform a rotation to bring the AVL tree back in balanced form.

AVL Trees

14

Insertion (contd…) : 

Let x be the deepest node where an imbalance occurs.



Four cases to consider. The insertion is in the n Left sub tree of the Left child of x. (LL) n Right sub tree of the Left child of x. (LR) n Left sub tree of the Right child of x. (RL) n Right sub tree of the Right child of x. (RR)

Right Rotation Left - Right Right - Left Left Rotation

Idea: LL & RR - Single rotation. LR & RL - Double rotation. AVL Trees

15

Four Imbalance Cases : k2

Case 1: The left subtree is higher than the right subtree, and this is caused by the left subtree of the left LL child.

Case 4: The symmetric case to case 1

k1 C

k2 A

B

B

A

C

RR k2

Case 2: The left subtree is higher than the right subtree, and this is caused by the right subtree of the leftLR child.

k1

Case 3:

k1 R P Q

k1

The symmetric case to case 2

RL

k2 R Q

16

P

1) Simple Insertion : #'s are Balance Factors

-1 1

-1

0

0

1 0

1 0

-1 0 0

0

0

1 0

0 0

0

No Rotation Required AVL Trees

17

2) Insertion with Right Rotation : -1 0

-1

1 22 0 1 0

LL

0

Right Rotation

1 0

0 0

0 0

0

0 0

1 0

0 0

0

Simple Right Rotation Required AVL Trees

18

Example # 12

12

k2

8

16

k1

A

2

LL

C

4

10 6

k1

14

Right Rotation

4 k2

A

2

8 B

B

16

1

6

14 C

10

1 AVL Trees

19

3) Insertion with Left Rotation: -1 -2

0

0 0

0 -1 0

RR Left Rotation

1 0

0

0 -1 0

-1

0 0 -1

0

1 0

0

0

-1 0

0

Simple Left Rotation Required AVL Trees

20

4)Insertion with Double Rotation: -1 -2

Double Rotation Needed (RL) :

1

10

0

0 -1

-1 10

0 0

a). Right rotation around right subtree of the unbalanced subtree 0

b). Left Rotation around root of the unbalanced subtree AVL Trees

21

(i) The Right Rotation : -2

-2

1

1

0

-1

-1 1

0 0

1 0

-2 0

0

0 1

0

-1 0

22

(ii) The Left Rotation : -2

0

1 0

-2 0

0 1

0

1 1 -1

0

0 0

1 0

-1 0

0

23

In nutshell (RL : Insertion) -1 -2

0

1

1

10

0

On balancing

0

0 -1

-1 10

0

1 0

0

0

1 0

-1 0

0

AVL Trees

24

Example # (LR Insertion) k3

k3

8 k1

12

12

12

k2

8

16

16

6

k2

4

10 k2

2

6

14

D

10

14

4

4

6

2

A

2

5 B

A Left rotation on 4

5

k3

k1

D

k1

16 8

5

B

14 10

D

A B AVL Trees

Right rotation on 8

25

Extended Example # 1 : 

Insert : 3 , 2 , 1 , 4 , 5 , 6 , 7 , 16 3

2

1

4

Balancing by 5 Right Rotation Balancing by (LL) Left Rotation (RR) AVL Trees

26

Extended Example # 1 : 

Insert : 3 , 2 , 1 , 4 , 5 , 6 , 7 , 16 2

1

3

4

6 5

AVL Trees

27

Extended Example # 1 : 

Insert : 3 , 2 , 1 , 4 , 5 , 6 , 7 , 16 2

4

1 3

5

7 6 Balancing node 2 by Left AVLRotation Trees (RR)

28

Extended Example # 1 : 

Insert : 3 , 2 , 1 , 4 , 5 , 6 , 7 , 16 4

5

2

1

3

6

16 7 Balancing node 5 by Left AVLRotation Trees (RR)

Ans. 29

Extended Example # 2 : 

Insert : 64 , 1 , 14 , 26 , 13 , 110 , 98 , 85 64

Since node 64 is imbalanced, thus by LR Insertion

1

14

AVL Trees

30

Extended Example # 2 : 

Insert : 64 , 1 , 14 , 26 , 13 , 110 , 98 , 85

64

1

13 14 26

110

98

31

Inserting 85 :

14

1

64

13

26

110

98

85

Performing Right Rotation (LL)

Node 110 becomes imbalanced. Ans. 32

AVL Trees : Deletion 

AVL tree Deletion: same as BST deletion.



In event of an imbalance due to deletion, one or more rotation are needed to be applied to balance the AVL trees.



On deletion of a node X from the AVL tree let A be the closest ancestor node on the path from X to the root node, with balance factor = +2 or -2.



To restore balance the rotation is first classified as L or R depending on whether the deletion occurred on the left or right subtree of A AVL Trees

33

Deletion : (contd…) 

Now depending on the value of BF(B) where B is the left or right subtree of A, the R or L imbalance is further classified as:  



R0, R1 or R-1, L0, L1 or L-1.

The L and R rotations are the mirror images of each other. Thus,    

L0 L1 L-1

R0 R1 R-1

Here we are considering the Right Rotations, Left Rotations can be done in the similar way.

AVL Trees

34

1) Deletion by R(0) Rotation :  

Delete node 60 Deletion is to be done on the right side of root node A(46) and BF(B)=0 A (+2) (-1) B 46 20 B (0) RightDelete Rotation 60 R(0) (+1)A

A(+2) (+1) 46

BB(0) (0) 20

18 7

20 18

54 60

23

7 18 7

24

AVL Trees

54 46

60 54

23 23 24

35

2) Deletion by R(1) Rotation : 

Delete node 39



Deletion is to be done on the Right side of root node A(37) and BF(B)=+1 A (+1) (+1) AA(+2) (0) B 37 37 B 26 RightDelete Rotation B (+1) (+1) 39 R(1) (0) B 26 41 26 41 A 18

18

28

39

18 16

16

37

28 28

39

41

16 AVL Trees

36

3) Deletion by R(-1) Rotation : 

Delete node 52



Deletion is to be done on the Right side of root node A(44) and BF(B)=-1 A (+1) A (+1) 44

B (-1)

B (-1) 22 18

48

22

22 18

52

28 23

Right Rotation R(-1) Delete 52 (0) B 18

29 AVL Trees

44 28 48

52

28 23 23

(0) 44 A

29

48

29 37

Deletion Examples : 

Delete elements 120,64,130 from the following search tree. 128 (+1) (0)

(0)

(0)

26

98

135 110 (-1)

64

(0)

85

99

(0)

130 (0)

120 AVL Trees

(-1)

(0) 38



Delete 120 : 128 (+1) (0)

(0)

26

98

135 110 (-1)

64

(0)

85

99

(0)

(-1)

120

130 (0)

(0) Ans.

AVL Trees

39



Delete 64 : 128 (+1) (0)

(0) (1)

(0)

26

98

135 110 (-1)

64

(0)

85

99

(-1)

130 (0)

(0) Ans. AVL Trees

40



Delete 130 : 128 (+2) (+1) (0)

(1)

(0)

135 110 (-1)

85

26 

98

99

(-1)

130 (0)

(0)

Node 128 becomes unbalanced BF(128)=+2 

So we Follow R(0) Rotation.

41



Delete 130 : 128 (+2) 98 (-1)

(0) (+1) R(0) Rotation 98 85 (1) (0) 85

(0)

26 

(-1) (-1) 110 110

26

99

(-1) (+1) 135 128 (0) 135

99 (0) (0)

Ans.

Node 128 becomes unbalanced BF(128)=+2 

So we Follow R(0) Rotation.

42

Example : Insertion + Deletion Ques 1(a). Insert the following keys in order shown to construct an AVL search tree A, B, C, D, E Ques 1(b). Then Delete the last two keys in order of Last in First out. Soln.  AVL Trees

43

Solution. 

Insert A, B A

B

AVL Trees

44

Solution. 

Now Insert C A

B

C AVL Trees

45

Solution. 

Now Insert C A B RR Rotation B A

The tree is unbalanced at A

C C

AVL Trees

46

Solution. 

Now insert D B

A

C

D AVL Trees

47

Solution. 

Now insert E B

C

A The tree is unbalanced at B and C

D

AVL Trees

E48

Solution. By Left Rotation B

RR

D

A

E

C AVL Trees

49

Solution. 

Delete E : B

D

A

E

C AVL Trees

50

Solution. 

Delete D : B

D

A

C

Ans. AVL Trees

51

Special Thanks to: Prof. Vinay Kumar Pathak HOD Of CSE Department HBTI, Kanpur.

AVL Trees

52