Module-3

Non-Linear Data Structure

Tree

Dr. Ram Kishan Dewangan

Associate Professor, SCSET
Bennett University, Gr. Noida
Construct AVL Search Tree
Construct AVL Search tree by inserting following elements in order of
their occurrence 6, 5, 4, 3, 2, 1
Insert 6 Insert 3 Insert 2
5 1 5
0 6 1 5
Critical Node 4 6 Case 1 0 3 0 6
Insert 5
1 4 0 6
Right Rotation
of Node 4
1 6 1 3 0 2 0 4
0 3

0 5 0 2

Insert 4 Insert 1
5 Critical Node 0 3
Critical Node 6
0 5 1 3 0 6 1 2 0 5
1 5 2
Case 1 0 4 0 6 1 2 0 4 Case 1 0 1 0 4 0 6
Right Rotation Right Rotation
0 4 of Node 6 0 1 4 of Node 5

2
 Construct AVL Search Tree
Construct AVL Search tree by inserting following elements in order of
their occurrence 64, 1, 44, 26, 13, 110, 98, 85
Insert 64 Insert 26 , 13 Case 3: Right Left Rotation
Right Rotation of Right Child 26
0 64 1 44 Followed By 1 44
44
0 Left Rotation of Parent 1
Critical
Insert 1
Node
-1 1 64 1 64 0 13 0 64

1 64 Right Rotation Left Rotation

0 1’ 26 of Right Child 26 13 of Parent 1 0 1 0 26

0 1 0’ 13 26
Insert 44
Case 2: Left Right Rotation
Left Rotation of Left Child 1 64
Critical Node 64 0 44
Followed By
- 1 Right Rotation of Parent 64 44
1 Right Rotation 0 1 0 64
0 44 1 of Parent 64
Left Rotation of Left Child 1

3
Construct AVL Search Tree
Construct AVL Search tree by inserting following elements in order of
their occurrence 64, 1, 44, 26, 13, 110, 98, 85
Insert 110 , 98 Case 3: Right Left Rotation
Right Rotation of Right Child 110
0 44 Followed By 44 0 44
Left Rotation of Parent 64
0 13 -1 64 Critical Node 13 64 0 13 0 98
Right Rotation Left Rotation
0 1 0 26 0 1’ 110 1 26 98
of Right Child 110 of Parent 64 0 1 0 26 0 64 0 110

0’ 98 110

Insert 85
-1 44

0 13 1 98

0 1 0 26 -1 64 0 110

0 85
4
Construct AVL Search Tree
Construct AVL Search tree by inserting following elements in order of
their occurrence 60,73,75,76,79,81,82,300,0,5,73
Insert 60 Insert 76 ,79 Insert 82

0 60 -1 73 76 Critical 0 76
-1 73 Case 4
Left Rotation 73 79 Case 4 0 73 0 81
Insert 73 0 60 75 -1 Critical of Node 75 0 60 0 76 Left Rotation
60 75 -1 81 of Node 79 60 75 79 82
-1 60 0 76 -1’ 0 75 0 79
0 0 0 0
0 73 79 0’ 0 82

Insert 75 Insert 81
0 76
60 Critical Node 0 73 Critical Node
73 0 73 -1 79
Case 4 0 60 76 -1 Case 4
-1 73 Left Rotation Left Rotation
60 75 0 60 0 75 0 81
of Node 60 of Node 73
0 0 0 75 -1 79
0 75
75
0 81
5
Construct AVL Search Tree
Construct AVL Search tree by inserting following elements in order of
their occurrence 60,73,75,76,79,81,82,300,0,5,73
Insert 300 , 0 Insert 5 Case 2: Left Right Rotation,
76 Critical Left Rotation of Left Child 0, 76
76 0
Followed By
73 81 Right Rotation of Parent 60 73 81
1 73 81 -1
60 75 79 82 5 75 79 82
1 60 75 79 82 -1
0 0 0 60
-1 0 300 300
0 0 0 300

0 5

Insert 73

Can not Insert 73 as duplicate key found

6
Deleting node from AVL Tree
 If element to be deleted does not have empty right sub-tree, then element is replaced with its
In-Order successor and its In-Order successor is deleted instead
 During winding up phase, we need to revisit every node on the path from the point of deletion
up to the root, rebalance the tree if require
28 0

-1 23 0 32

0 22 -1 26 -1 30 -1 34

0 27 0 31 0 36

7
Deleting node from AVL Tree
Delete 30
28
30
31
23 32
23 32 Critical Node
34
22 26 30
22 26 31 34 -1

27 31 36
27 36 0
In-Order Traversal
22, 23, 26, 27, 28, 30, 31, 32, 34, 36 Case 4:
Left Rotation of
Delete 28 Node 32
28 0
30 1 31
-1 23 32 -1 23 -1 34 0

0 22 -1 26 31 -1 -1 34
30 32 0 36 0
0 22 -1 26

27 31 36 27 0
0 0 0

8
Deleting node from AVL Tree
Delete 73, 74 Delete 73
73
1 74
73
13 75
1 13 75 -1
10 28 74 89
1 10 0 28 74 0 89 0
5 In-Order Traversal
5, 10, 13, 28, 73, 74, 75, 89 5 0

Delete 74

74 Critical
75 0
13
Case 1: Right Rotation
1 13 75 0
89 of Node 75 1 10 75 0
1 10 28 0 0 89
28 5 0 28 89 0
0
0 5

9
Multiway Search Tree (B - Tree)
 The nodes in a binary tree like AVL tree contains only one record
 AVL tree is commonly stored in primary memory
 In database applications where huge volume of data is handled, the search tree can not be
accommodated in primary memory
 B-Trees are primarily meant for secondary storage
 B-Tree is a M-way tree which can have maximum of M Children

10, 15, 20

2, 3 11, 14 16 21

4 – way Tree

10
Multiway Search Tree (B - Tree)
 An M- way tree contains multiple keys in a node
 This leads to reduction in overall height of the tree
 If a node of M-way tree holds K keys then it will have k+1 children

No of Keys = 3

K1, K2, K3
No of Ways or children = 4

11
Multiway Search Tree (B - Tree)
 A tree of order M is a M-way search tree with the following properties
1. The Root can have 1 to M-1 keys
2. All nodes (except Root) have (M-1)/2 to (M-1) keys
3. All leaves are at the same level
4. If a node has ‘t’ number of children, then it must have ‘t-1’ keys
5. ​Keys of the nodes are stored in ascending order

K0, K1, K2, ……… ,Kn-1

P0 P1 P2 Pn-1 Pn

12
Multiway Search Tree (B - Tree)

K0, K1, K2, ……… ,Kn-1

P0 P1 P2 Pn-1 Pn
 K0, K1, K2, ……… ,Kn-1 are keys stored in the node
 Sub-Trees are pointed by P0, P1, P2, ……… ,Pn then
 K0 >= all keys of sub-tree P0
 K1 >= all keys of sub-tree P1
 ………..

 ………..

 Kn-1 >= all keys of sub-tree Pn-1

 Kn-1 < all keys of sub-tree Pn
13
Multiway Search Tree (B - Tree)

20

10, 15 25, 40, 50

2, 8 11 16, 18 22 30, 35 42, 44 55, 60

B-Tree of Order 4 (4 way Tree)

14
Insertion of Key in B-Tree
1. If Root is NULL, construct a node and insert key
2. If Root is NOT NULL
I. Find the correct leaf node to which key should be added
II. If leaf node has space to accommodate key, it is inserted and sorted
III. If leaf node does not have space to accommodate key, we split node into two parts

15
Split Node (5 way Tree, max 4 Keys)

P
5, 10, 15, 20 1, 5, 9, 11

Insert - 3 Insert - 3 Overflow

3, 5, 10, 15, 20 1, 3, 5, 9, 11
Overflow
5
10
1, 3 9, 11
3, 5 15, 20

16
Split Node (5 way Tree, max 4 Keys)

10, 20, 30, 40

3, 5, 6, 8 12, 14 21, 25, 27 31, 35 42, 45, 48

Insert - 38

10, 20, 30, 40

3, 5, 6, 8 12, 14 21, 25, 27 31, 35 ,38 42, 45, 48

17
Split Node (5 way Tree, max 4 Keys)
10, 20, 30, 40

3, 5, 6, 8 12, 14 21, 25, 27 31, 35, 38 42, 45, 48

Insert 7

10, 20, 30, 40

3, 5, 6, 7, 8 12, 14 21, 25, 27 31, 35, 38 42, 45, 48

Overflow

18
Split Node (5 way Tree, max 4 Keys)

6, 10, 20, 30, 40 Overflow

3, 5 7, 8 12, 14 21, 25, 27 31, 35, 38 42, 45, 48

20

6, 10 30, 40

3, 5 7, 8 12, 14 21, 25, 27 31, 35, 38 42, 45, 48

19
Construct M-Way Tree
Construct 5 Order (5 Way) Tree from following data
1, 7, 6, 2, 11, 5, 10, 13, 12, 20, 16, 24, 3, 4, 18, 19, 14, 25
We are asked to create 5 Order Tree (5 Way Tree) maximum 4 records can be accommodated in a node

Insert 1 Insert 7 Insert 6 Insert 2 Insert 11

1, 2, 6, 7, 11 6
1 1, 7 1, 6, 7 1, 2, 6, 7
Overflow 1, 2 7, 11
Insert 5 Insert 10 Insert 13
6 6 6

1,2,5 7,11 1,2,5 7,10,11 1,2,5 7,10,11,13

20
Construct M-Way Tree
Construct 5 Order (5 Way) Tree from following data
1, 7, 6, 2, 11, 5, 10, 13, 12, 20, 16, 24, 3, 4, 18, 19, 14, 25
Insert 12 Insert 20, 16, 24

6 6, 11 6, 11
Overflow Overflow
1,2,5 7,10,11,12,13 1,2,5 7,10 12,13 1,2,5 7,10 12,13,16,20,24

Insert 3,4
3, 6, 11, 16
6, 11, 16 6, 11, 16
Overflow
1,2 4,5 7,10 12,13 20,24
1,2,5 7,10 12,13 20,24 1,2, 3,4,5 7,10 12,13 20,24

21
Construct M-Way Tree
Construct 5 Order (5 Way) Tree from following data
1, 7, 6, 2, 11, 5, 10, 13, 12, 20, 16, 24, 3, 4, 18, 19, 14, 25
Insert 18,19,14
3, 6, 11, 16

1,2 4,5 7,10 12, 13, 14 18, 19, 20, 24

Insert 25
3, 6, 11, 16 11
Overflow
1,2 4,5 7,10 12, 13, 14 18, 19, 20, 24, 25 3, 6 16, 20

3, 6, 11, 16, 20 Overflow 1,2 4,5 7,10 12, 13, 14 18, 19 24, 25

22
Deletion in B-Tree
 Case 1: If the key k is in node x and x is a leaf, delete the key k from x.

23
Deletion in B-Tree
 Case 2: If the key k is in node x and x is an internal node, do the following.

(a) If the child y that precedes k in node x has at least t keys, then find the predecessor k0 of k in the sub-tree rooted at y.
Recursively delete k0, and replace k with k0 in x. (We can find k0 and delete it in a single downward pass.)

24
Deletion in B-Tree
(b) If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least
t keys, then find the successor k0 of k in the subtree rooted at z. Recursively delete k0, and replace k with k0
in x. (We can find k0 and delete it in a single downward pass.)

(c) Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the
pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.

25
Deletion in B-Tree
 Case 3: If the key k is not present in internal node x, determine the root x.c(i) of the appropriate subtree that must
contain k, if k is in the tree at all. If x.c(i) has only t-1 keys, execute steps 3a or 3b as necessary to guarantee that we
descend to a node containing at least t keys. Then finish by recursing on the appropriate child of x.

(a) If x.c(i) has only t-1 keys but has an immediate sibling with at least t keys, give x.c(i) an extra key by moving a key from
x down into x.c(i), moving a key from x.c(i) ’s immediate left or right sibling up into x, and moving the appropriate child
pointer from the sibling into x.c(i).

26
(b) If x.c(i) and both of x.c(i)’s immediate siblings have t-1 keys, merge x.c(i) with one sibling, which involves moving a key
from x down into the new merged node to become the median key for that node.

27