Lect 13, 14 (final)AVL Tree and Rotations.pdf

data structure lec 13 and 14

1. Data Structures & Algorithm
CS-102
Lecture 13,14
AVL TREES
Lecturer: SyedaNazia Ashraf
1

2. Problem with BST
•The disadvantage of skewed BST is that the
worst case time complexity of a search is O(n)

3. Insertion in Binary Search Tree
BST for 3 4 5 7 9 14 15 16 17 18 20
14
15
4
9
7
18
3
5
16
20
17
Linked List!
3
•Data not Symmetric i.eRight Skewed
•Less nodes, but Height is more
•Go for Linear Search and its efficiency lost
•Time complexity for linear search = O(n),
which is less efficient and take more time
to search

4. Insertion in Binary Search Tree
BST for 14, 15, 4, 9,18, 3
14
154
9 183
4
Level 0, 2
0
= 1 node
Level 1, 2
1
= 2nodes
Level 2, 2
2
= 4nodes
Height=3, i.emax 3 comparisons for searching
Search9 ?
we move on one side
of the Tree according
to BST comparison
order
•For 10 levels, 2
9
=512 nodes (at last level 9)
•Sum of all nodes=1023 nodes, i.eneed max 10 comparisons (Advantage of BST)
•Time complexity for Binary Search= O(log
2n), which is more efficient than Linear Searchbecause it takes
less time
•To make sure when value inserted in BST its height should be balanced, we use AVL TREE

5. Balanced BST
•We should keep the tree balanced.
•One idea would be to have the left and right
subtrees have the same height
5

6. Balanced BST
Does not force the tree to be shallow.
14
15
18
16
20
17
4
9
7
3
5
6

7. Balanced BST
•We could insist that every node must have left and
right subtrees of same height.
•But this requires that the tree be a complete binary
tree
•To do this, there must have (2
d+1
–1)data items,
where dis the depth of the tree.
•This is too rigid a condition.
7

8. AVL
•There is a need to maintain the binary search tree to
be of balanced height, so that it is possible to
obtained for the search option a time complexity of
O(log n) in the worst case
•One of the most popular balanced tree was
introduced by Adelson-Velskiiand Landis (AVL)

9. AVL Tree
•AVL (Adelson-Velskiiand Landis) tree (are 2 Russian scientists,
proposed technique in their research paper published in 1962 to
balance binary tree and to save BST from degenerated form )
•An AVL tree is identical to a BST except
▪height of the left and right subtrees can differ by at
most 1.
▪height of an empty tree is defined to be (–1).
9

10. AVL Tree
•An empty binary tree is an AVL Tree.
•A nonempty binary tree T is an AVL Tree iffgiven
T
L
and T
R
to be the left and right subtrees of T
and h(T
L
)and h(T
R
) to be the heights of subtrees
T
L
and T
R
respectively, T
L
and T
R
are AVL Trees
and | h(T
L
) -h(T
R
) | ≤ 1

11. Balanced Binary Tree
•The heightof a binary tree is the maximum level of its
leaves (also called the depth).
•The balance of a node in a binary tree is defined as
the height of its left subtree minus height of its right
subtree.
•In balanced tree, each node has an indicated balance
of 1, 0, or –1.
11

12. Balance Factor
•h(T
L
) -h(T
R
) is called Balance Factor (BF)
•For AVL Tree, the balance factor of a node can
be either 0, 1, -1

13. AVL Tree
50
T
L
T
R
h=2h=3
BF = h(T
L
)-h(T
R
)
BF = 3-2
BF = 1

14. Balanced Binary Tree
-1
01
0
0
0
0
-1
0
1
00 0
0 00 0
This tree contains balance factors instead of data
14

15. Balanced Binary Tree
Insertions and effect on balance
-1
01
0
0
0
0
-1
0
1
00 0
0 00 0U
1 U
2U
3 U
4
U
5 U
6U
7 U
8 U
9U
10U
11U
12
BBB B
B B
15

16. Balanced Binary Tree
•Tree becomes unbalanced only if the newly inserted
node
▪is a left descendant (grand child) of a node that
previously had a balance of 1 (U
1to U
8),
▪or is a right descendant (grand child) of a node
that previously had a balance of –1 (U
9to U
12)
16

17. Balanced Binary Tree
Insertions and effect on balance
-1
01
0
0
0
0
-1
0
1
00 0
0 00 0U
1 U
2U
3 U
4
U
5 U
6U
7 U
8 U
9U
10U
11U
12
BBB B
B B
17

18. Inserting New Node in AVL Tree
1
0
A
B
T
1
T
3
T
2
1
Use triangle notation for rest of the nodes
18

19. Inserting New Node in AVL Tree
2
1
A
B
T
1
T
3
T
2
new
1
2
Violate AVL condition
19

20. Searching in AVL Tree
•Searching an AVL search tree for an element is
exactly similar to the method used in a binary
search tree.

21. An AVL Tree
5
82
4
3
1
7
Height = 4
0
1
2
3
21

22. Not an AVL tree
6
81
4
1
5
Height = 4
0
1
2
3
22
•After insertion of node 5, BF of 6 node disturb
•Before next insertion, we have to balance BST
•To balance BST, we use Rotations
•Rotations do shuffling of nodes and make BST balance and transform BFs to -1, 0 and 1

23. Rotations
•To perform the rotations it is necessary to identify a
specific node A whose balance factor (BF) is neither 0,
1, -1 and which is the nearest ancestor to the inserted
node on the path from the inserted node to the root.

24. Rotation Types
Note: The insertion occurs on the “outside” (i.e., left-left or right-right rotations)
Insertion occurs on the “inside” i.e., right-left or left-right rotations)
•LL rotation: Inserted node is in the left subtree of left
subtree of node A.
•RR rotation: Inserted node is in the right subtree of right
subtree of node A.
•LR rotation:Inserted node is in the right subtree of left
subtree of node A.
•RL rotation: Inserted node is in the left subtree of right
subtree of node A.

25. Trick to solve
Note: We also say, LL and RR rotations can fix through Single Rotation.
LR and RL Rotation can fix through Double Rotation
•For LL and RR rotations, identify A and B, then
make A as a child of B.
•FOR LR and RL rotations, identify A, B and C, then
make A and B child of C.

26. Example of Rotation
•Generate AVL Tree for values:
5, 7, 19, 12, 10, 15, 18, 20, 25, 23
•Solve Example on board….