Data Structures

Div A
SY EXCP
Sem III
Dr. Rajashree Daryapurkar
2024-25
 Outline
• Types of trees
• Threaded binary trees.
• Search Trees –
– AVL tree, Multiway Search Tree, B Tree, B+ Tree
• Applications/Case study of trees.
• Summary
 Types of trees
• General tree
• Binary tree
• Binary search tree
• Threaded binary tree
• AVL Tree
• B tree
• B+ Tree
• Trie
• Heap
• Red black tree
• Splay tree
Binary Tree Binary search Tree

Red Black Tree

AVL Tree
 Splay Tree

Trie
Heap (MinHeap)
B Tree

B+ Tree
 AVL tree
Named after their inventors Adelson, Velski &
Landis, AVL trees are height balancing binary
search tree.
 The AVL Tree Data Structure
AVL Tree

AVL Trees are Self-Balanced Binary Search Trees.

In AVL trees, the balancing factor of each node is

either 0 or 1 or -1.

Balance Factor of AVL Tree calculated as = Height of

Left Sub-tree - Height of Right Sub-tree
 The AVL Tree Data Structure
Construction of AVL Trees -
Insertion Operation is performed to construct the AVL Tree.
Inserting the element in the AVL tree is same as the insertion
performed in BST.
After insertion, check the balance factor of each node of the
resulting tree.
After the insertion, the balance factor of each node is either 0 or
1 or -1, then the tree is considered to be balanced, concludes
the operation, and inserts the next element if any.
After the insertion, the balance factor of at least one node is not
0 or 1 or -1, then the tree is considered to be imbalanced,
perform the suitable rotation to balance the tree, and after the
tree is balanced, insert the next element if any.
 The AVL Tree Data Structure
• Rotations used to Balance the AVL Tree -
After inserting an element in the AVL tree,
If a tree becomes imbalanced, then there exists one particular
node in the tree by balancing which the entire tree becomes
balanced automatically.
To rebalance the tree, balance that particular node.
• To find that particular node:
Traverse the path from the newly inserted node to the root
node.
Check the balance factor of each node that is encountered while
traversing the path.
The first encountered imbalanced node will be the node that
needs to be balanced.
 The AVL Tree Data Structure
• To balance that node:
Count three nodes in the direction of the leaf node.
Then, use the concept of AVL Tree Rotations to rebalance the
tree.
– LL Rotation - In LL rotation, every node moves one position to
left from the current position.
– RR Rotation - In RR rotation, every node moves one position to
right from the current position.
– LR Rotation - In LR rotation, at first, every node moves one
position to the left and then one position to right from the
current position.
– RL Rotation - In RL rotation, at first every node moves one
position to right and then one position to left from the current
position.
 Example #1: Is this an AVL Tree?
Balance Condition:
6
balance of every node is between -1
and 1

where balance(node) = 4
height(node.left) – 8
height(node.right)

1 7 11

10 12
 Example #2: Is this an AVL Tree?
6
Balance Condition:
balance of every node is between -1
and 1
4 8
where balance(node) =
height(node.left) –
height(node.right)
1 5 7 11

2
Construction of the AVL Tree for the given
Sequence 21, 26, 30, 9, 4, 14, 28, 18,15,10,
2, 3, 7
 AVL Trees
3
10

2 2
5 20

0 1 1 0
2 9 15 30

0 0
7 17
 Rotations
• Insert 1,2,3
• Right-Right or R-R case
• Solution: rotate left
 Rotations
• Insert 3,2,1
• Left-Left or L-L situation
• Solution: Rotate right
 Rotations
• Insert 1,2,3
• Right-Right or R-Right situation
• Solution: one rotation
 Rotations
• Insert 1,3,2
• Right-Left or R-L situation
• Solution: Two rotations
– Rotate right  R-R
– Rotate left
 Rotations
• Insert 1,3,2
• Right-Left or R-L situation
• Solution: Two rotations
– Rotate right R-R
– Rotate left
 Rotations
• Insert 3,1, 2
• Left-Right or L-R situation
• Solution: Two rotations
– Rotate left L-L
– Rotate right
 Rotation summary
• L-L then single rotation --> rotate right
• R-R then single rotation--> rotate left
• L-R then double rotation --> rotate left to get
L-L then rotate right
• R-L then double rotation --> rotate right to get
R-R then rotate left
Example- 12, 45, 65, 23, 89, 50, 4,
35,100
Create AVL tree:10, 20, 30, 25, 40, 50,
35, 33, 37, 60,38
Balance the tree
Example 3: 8,3,5,25,76, 45,
30,26,28,27
 Example for right-right case:
insert(26)

15
15

8 24
8 22

24 4 10 22 25
4 10 19

3 6 3 6 19 23
23 25 26

26
 Practice time! Example of Case #4
Starting with 60 Which of the
this AVL tree: following is the
30 80 updated AVL
tree after
10 50 inserting 42?

A) B) C) D)
42 30 50 50

30 60 10 50 30 60 30 60

10 50 80 42 60 80 10 42 80 10 42 80
 Pros and Cons of AVL Trees
Arguments for AVL trees:
1. All operations logarithmic worst-case because trees
are always balanced
2. Height balancing adds no more than a constant factor
to the speed of insert and delete

Arguments against AVL trees:

1. Difficult to program & debug [but done once in a
library!]
2. More space for height field
3. Asymptotically faster but rebalancing takes a little
time
4. If amortized logarithmic time is enough, use splay
trees (also in the text, not covered in this class)