Data Structures and Algorithms

(m-way search tree)

Dr. Ramesh Kumar Mohapatra

Dept. of CSE, NIT Rourkela

1
 m-Way Search Tree
 An m-way search tree T may be an empty tree.
 If T is non-empty, it satisfies the following properties:
(i) For some integer m known as the order of the tree, each node
has at most m child nodes.
(ii) A node may be represented as
A0 , (K1, A1), (K2, A2) …. (Km-1 , Am-1 )
where Ki , 1 ≤ i ≤ m-1 are the keys and Ai, 0 ≤ i ≤ m-1 are the
pointers to the subtree of T
(iii) If the node has c child nodes where c ≤ m, then the node can
have only (c-1) keys, K1 , K2 , …… Kc-1
(iv) The keys in a node are ordered, i.e., K1<K2< …… <Kc-1

2
 m-Way Search Tree
(v) For a node A0 , (K1 , A1), (K2 , A2) , …. (Km-1 , Am-1 ), if Si is
the subtree pointed by Ai, 0 ≤ i ≤ m-1then
 Key(S0)<K1
 Key(Sm-1)>Km-1
 Ki < Key(Si) < Ki+1 , 1 ≤ i ≤ m-2

A0 A1 A2 A3

< < >

3
 m-Way Search Tree
(vi) Each of the subtree Ai , 0 ≤ i ≤ m-1 are also m-way search tree

m-Way Search Tree [ m=4]

4
 m-Way Search Tree [ m=5]
18 44 76 198
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

5
 Searching in an m-Way Search Tree
Look for 77
18 44 76 198
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

6
 Insertion in an m-Way Search Tree
Insert 6
18 44 76 198
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

7
 Insertion in an m-Way Search Tree
Insert 6
18 44 76 198
X X Insert 146

80 92 141 262
6 7 12
X X X
X X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

8
 Insertion in an m-Way Search Tree
Insert 6
18 44 76 198
X X Insert 146

80 92 141 262
6 7 12
X X X
X X X

77 148 151 172 186

8 10
X X X X X X
X X X

272 286 350

146 X X X X
X X
9
 Deletion in an m-Way Search Tree
Let K be the key to be deleted from the m-way search tree.

K
Ai Aj

K : Key
Ai , Aj : Pointers to subtree

10
 Deletion in an m-Way Search Tree
1) If (Ai = Aj = NULL) then delete K
2) If (Ai  NULL, Aj = NULL ) then choose the largest of
the key elements K’ in the subtree pointed to by Ai and
replace K by K’.
3) If (Ai = NULL, Aj  NULL ) then choose the smallest of
the key element K” from the subtree pointed to by Aj ,
delete K” and replace K by K”.
4) If (Ai  NULL, Aj  NULL ) then choose the largest of
the key elements K’ in the subtree pointed to by Ai or the
smallest of the key element K” from the subtree pointed to
by Aj to replace K.
11
 5-Way Search Tree
18 44 76 198
Delete 151
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

12
 5-Way Search Tree
18 44 76 198
Delete 151
X X

80 92 141 262
7 12
X X X
X X

77 148 172 186

8 10
X X X X X X
X X X

272 286 350

X X X X

13
 5-Way Search Tree
18 44 76 198
Delete 12
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

14
 5-Way Search Tree
18 44 76 198
Delete 12
X X

80 92 141 262
7 10
X X X
X X

77 148 151 172 186

8
X X X X X X X
X X

272 286 350

X X X X

15
 5-Way Search Tree
18 44 76 198
Delete 18
X X --Delete 12
--Replace 18 by 12

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

16
 5-Way Search Tree
18 44 76 198
Delete 18
X X --Delete 12
--Replace 18 by 12

80 92 141 262
7 10
X X X
X X

77 148 151 172 186

8
X X X X X X X
X X

272 286 350

X X X X

17
 5-Way Search Tree
12 44 76 198
Delete 18
X X --Delete 12
--Replace 18 by 12

80 92 141 262
7 10
X X X
X X

77 148 151 172 186

8
X X X X X X X
X X

272 286 350

X X X X

18
 5-Way Search Tree
18 44 76 198
Delete 262
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

19
 5-Way Search Tree
18 44 76 198
Delete 262
X X

80 92 141 272
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

286 350
X X X

20
 5-Way Search Tree
18 44 76 198
Delete 198
X X --delete186
--replace 198 by 186

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

21
 5-Way Search Tree
18 44 76 198
Delete 198
X X --delete186
--replace 198 by 186

80 92 141 262
7 12
X X X
X X

77 148 151 172

8 10
X X X X X X
X X X

272 286 350

X X X X

22
 5-Way Search Tree
18 44 76 186
Delete 198
X X --delete186
--replace 198 by 186

80 92 141 262
7 12
X X X
X X

77 148 151 172

8 10
X X X X X X
X X X

272 286 350

X X X X

23
 5-Way Search Tree
18 44 76 198
Delete 198
X X --delete 262
--replace 198 by 262

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

X X X X

24
 5-Way Search Tree
18 44 76 198
Delete 198
X X --delete 262
--replace 198 by 262

80 92 141 272
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

286 350
X X X

25
 5-Way Search Tree
18 44 76 262
Delete 198
X X --delete 262
--replace 198 by 262

80 92 141 272
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

286 350
X X X

26
 B Trees
B tree is a balanced m-way search tree
 A B tree of order m, if non empty, is an m-way
search tree in which
i. the root has at least two child nodes and at most m
child nodes
ii. internal nodes except the root have at least m/2 child
nodes and at most m child nodes
iii. all leaf nodes are on the same level

27
 B Tree of order 5
48

56 64 85
31 45

46 47
X X X 87 88 100 112
10 18 21
X X X X X
X X X X
58 62
X X X 49 51 52
36 40 42 X X X X
X X X X 67 75
X X X
28
 Searching a B Tree
 Searching for a key in a B-tree is similar to the
one on an m-way search tree.
 The number of accesses depends on the height h
of the B-tree

29
 Insertion in a B-Tree
1. Attempt to insert the new key into a leaf
2. If this would result in that leaf becoming too big, split the
leaf into two, promoting the middle key to the leaf’s
parent
3. If this would result in the parent becoming too big, split
the parent into two, promoting the middle key
4. This strategy might have to be repeated all the way to the
top
5. If necessary, the root is split in two and the middle key is
promoted to a new root, making the tree one level higher

30
 Constructing a B-tree
• Suppose we start with an empty B-tree and keys arrive in the
following order:1 12 8 2 25 6 14 28 17 7 52 16 48
68 3 26 29 53 55 45
• We want to construct a B-tree of order 5
• The first four items go into the root:

1 2 8 12

• To put the fifth item in the root would over-fill it

• Therefore, when 25 arrives, pick the middle key to make a
new root

31
 1
12
8 Constructing a B-tree
2
25 Add 25 to the tree
6
14
28
17
7
52 Exceeds Order.
16 Promote middle and
48 split.
68 1 2 8 12 25
3
26
29
53
55
45

32
 1
12
8 Constructing a B-tree (contd.)
2
25
6 8
14
28
17
7
52 1 2 12 25
16
48 6, 14, 28 get added to the leaf nodes:
68
3 8
26
29
53
55
45 1 2 1 6 2 12 14
25 28
33
 1
12
8 Constructing a B-tree (contd.)
2
25
6 Adding 17 to the right leaf node would over-fill it, so we take
14 the middle key, promote it (to the root) and split the leaf
28
17
7 8
52
16
48
68
3 1 2 6
2 25 28 28
12 14 17
26
29
53
55
45

34
 1
12
8 Constructing a B-tree (contd.)
2
25 7, 52, 16, 48 get added to the leaf nodes
6
14
28
17
7 8 17
52
16
48
68
3 1 2 76 12 14
16 25 28 52
48
26
29
53
55
45

35
 1
12
8 Constructing a B-tree (contd.)
2
25
6 Adding 68 causes us to split the right most leaf,
14 promoting 48 to the root
28
17
7
52
16
48 8 17
68
3
26
29 1 2 6 7 12 14 16 25 28 48 52 68
53
55
45

36
 1
12
8 Constructing a B-tree (contd.)
2
25
6 Adding 3 causes us to split the left most leaf
14
28
17 8 17 48
7
52
16
48
68 1 2
3 6 7 12 14 16 25 28 52 68
3
26
29
53
55
45

37
 1
12
8 Constructing a B-tree (contd.)
2
25
6 Add 26, 29, 53, 55 then go into the leaves
14
28
17 3 8 17 48
7
52
16
48
68 1 2 6 7 12 14 16 25262829 52536855
3
26
29
53
55
45

38
 1
12
8 Constructing a B-tree (contd.)
2
25 Exceeds Order.
6 Add 45 increases the trees level Promote middle and
14 split.
28
17
7
52 Exceeds Order.
16 Promote middle and
3 8 17 48 split.
48
68
3
26
29 1 2 6 7 12 14 16 25 26 28 29 45 52 53 55 68
53
55
45

39
 Exercise in Inserting a B-Tree
 Insert the following keys to a 5-way B-tree:
3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56

40
 Answer to Exercise

41
 Delete from a B-tree
1. If the key is already in a leaf node, and removing
it doesn’t cause that leaf node to have too few
keys, then simply remove the key to be deleted.
2. If the key is not in a leaf then it is guaranteed (by
the nature of a B-tree) that its predecessor or
successor will be in a leaf -- in this case can we
delete the key and promote the predecessor or
successor key to the non-leaf deleted key’s
position.

42
 Removal from a B-tree (2)
• If (1) or (2) lead to a leaf node containing less than the
minimum number of keys then we have to look at the siblings
immediately adjacent to the leaf in question:
– 3: if one of them has more than the min’ number of keys then
we can promote one of its keys to the parent and take the
parent key into our lacking leaf
– 4: if neither of them has more than the min’ number of keys
then the lacking leaf and one of its neighbours can be combined
with their shared parent (the opposite of promoting a key) and
the new leaf will have the correct number of keys; if this step
leave the parent with too few keys then we repeat the process
up to the root itself, if required

43
 Type #1: Simple leaf deletion

Assuming a 5-way
B-Tree, as before... 12 29 52

2 7 9 15 22 31 43 56 69 72

Delete 2: Since there are enough

keys in the node, just delete it
Note when printed: this slide is animated

44
 Type #2: Simple non-leaf deletion

12 29 56
52 Delete 52

7 9 15 22 31 43 56 69 72

Borrow the predecessor

or (in this case) successor

Note when printed: this slide is animated

45
 Type #3: Enough siblings

12 29
Demote root key and
promote leaf key

7 9 15 22 31 43 56 69

Delete 22

Note when printed: this slide is animated

46
 Type #3: Enough siblings

12 31

7 9 15 29 43 56 69

Note when printed: this slide is animated

47
 Type #4: Too few keys in node and its
siblings

12 29 56

Join back together

7 9 15 22 31 43 69 72
Too few keys!
Delete 72

Note when printed: this slide is animated

48
 Type #4: Too few keys in node and its
siblings

12 29

7 9 15 22 31 43 56 69

Note when printed: this slide is animated

49
 Exercise in Removal from a B-Tree
 Given 5-way B-tree created by these data (last
exercise):
3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56

 Add these further keys: 2, 6,12

 Delete these keys: 4, 5, 7, 3, 14

50
 Answer to Exercise

51
 5-Way B Tree (insertion examples)
8 96 116

2 7 104 110 137 145

37 46 55 86
X X X X X X X X X X X X X X

Insert 4, 5, 58, 6 in the order

52
 5-Way B Tree (insertion examples)
8 96 116

104 110 137 145

37 46 55 86
X X X X X X X X X X X

2 4 7
X X X X

Search tree after inserting 4

53
 5-Way B Tree (insertion examples)
8 96 116

104 110 137 145

37 46 55 86
X X X X X X X X X X X

2 4 5 7
X X X X X

Search tree after inserting 4, 5

54
 5-Way B Tree (insertion examples)
Insert 58
8 96 116

104 110 137 145

37 46 55 86
X X X X X X X X X X X

2 4 5 7
X X X X X
37,46,55,58,86
Split the node at its median into two node, pushing
the median element up by one level
55
 5-Way B Tree (insertion examples)
Insert 55 in the root
8 96 116

104 110 137 145

37 46
X X X X X X
X X X
2 4 5 7 58 86
X X X X X X X X

56
 5-Way B Tree (insertion examples)
8 55 96 116

104 110 137 145

37 46
X X X X X X
X X X
2 4 5 7 58 86
X X X X X X X X

Search tree after inserting 4, 5, 58

57
 5-Way B Tree (insertion examples)
Insert 6
8 55 96 116

104 110 137 145

37 46
X X X X X X
X X X
2 4 5 7 58 86
X X X X X X X X
2,4,5,6,7
Split the node at its median into two node, pushing
the median element up by one level
58
 5-Way B Tree (insertion examples)
Insert 5 at the root
8 55 96 116

104 110 137 145

37 46
X X X X X X
X X X
58 86
2 4 6 7 X X X
X X X X X X

59
 5-Way B Tree (insertion examples)
55
Insert 5 at the root
5 8 96 116

104 110 137 145

37 46
X X X X X X
X X X
58 86
2 4 6 7 X X X
X X X X X X

60
 5-Way B Tree (insertion examples)
55
Insert 5 at the root

96 116
5 8

137 145
58 86
2 4 37 46 X X X
X X X
X X X X X X
104 110
6 7 X X X
X X X
61
 B-tree of Order 5 (deletion examples)
110

65 86 120 226

32 44 70 81 115 118
200 221
X X X X X X X X X
X X X

90 95 100
X X X X 300 440 550 601
X X X X X

Delete 95, 226, 221, 70

62
 B-tree of Order 5
110 delete 226

65 86 120 226

32 44 70 81 115 118
200 221
X X X X X X X X X
X X X

90 100
X X X 300 440 550 601
X X X X X

B-tree after deleting 95

63
 B-tree of Order 5
110

65 86 120 300

32 44 70 81 115 118
200 221
X X X X X X X X X
X X X

90 100
X X X 300 440 550 601
X X X X X

64
 B-tree of Order 5
110
Delete 221

65 86 120 300

32 44 70 81 115 118
200 221
X X X X X X X X X
X X X

90 100
X X X 440 550 601
X X X X

B-tree after deleting 95, 226

65
 B-tree of Order 5
110 Delete 70

65 86 120 440

32 44 70 81 115 118
200 300
X X X X X X X X X
X X X

90 100
X X X 550 601
X X X

B-tree after deleting 95, 226, 221

66
 B-tree of Order 5
110 Delete 65

65 86 120 440

32 44 65 81 115 118
200 300
X X X X X X X X
X X X

90 100
X X X 550 601
X X X

67
 B-tree of Order 5

86 110 120 440

32 44 65 81 115 118
200 300
X X X X X X X X
X X X

90 100
X X X 550 601
X X X

B-tree after deleting 95, 226, 221, 70

68
 Heap
Suppose H is a complete binary tree with n elements

H is called a heap or maxheap if each node N of H has the

following property

Value at N is greater than or equal to the value at each of the

children of N.

69
 Heap
97

88 95

95 48
66 55

25 38
66 35 48 55 62 77

18 40 30 26 24

97 88 95 66 55 95 48 66 35 48 55 62 77 25 38 18 40 30 26 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
70
 Inserting into a Heap
Suppose H is a heap with N elements
Suppose an ITEM of information is given.

Insertion of ITEM into heap H is given as follows:

[1] First adjoin ITEM at the end of H so that H is still a complete

tree, but necessarily a heap

[2] Let ITEM rise to its appropriate place in H so that H is finally a

heap

71
 Heap
97 Insert 70

88 95

95 48
66 55

25 38
66 35 48 55 62 77

26 24 70
18 40 30

97 88 95 66 55 95 48 66 35 48 55 62 77 25 38 18 40 30 26 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
72
 Heap
97 Insert 70

88 95

95 48
66 55

25 38
66 35 48 55 62 77

26 24 70
18 40 30

97 88 95 66 55 95 48 66 35 48 55 62 77 25 38 18 40 30 26 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
73
 Heap
97 Insert 70

88 95

95 48
66 55

25 38
66 35 70 55 62 77

26 24 48
18 40 30
97 88 95 66 55 95 48 66 35 48 55 62 77 25 38 18 40 30 26 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

74
 Heap
97 Insert 70

88 95

95 48
66 70

25 38
66 35 55 55 62 77

26 24 48
18 40 30
97 88 95 66 55 95 48 66 35 48 55 62 77 25 38 18 40 30 26 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

75
 Build a Heap
Build a heap from the following list

44, 30, 50, 22, 60, 55, 77, 55

76
 44, 30, 50, 22, 60, 55, 77, 55

44 44 44 50 50
30 30 50 44
30 30 44

22

Complete the Rest Insertion

77

55 60

50 30 44 55

22
77
 Deleting the Root of a Heap
Suppose H is a heap with N elements
Suppose we want to delete the root R of H
Deletion of root is accomplished as follows
[1] Assign the root R to some variable ITEM
[2] Replace the deleted node R by the last node L of H so that H is
still a complete tree but necessarily a heap
[3] Reheap. Let L sink to its appropriate place in H so that H is
finally a heap.

78
 95 22

85 70 85 70

55 33 30 65 55 33 30 65

15 20 15 22 15 20 15

85 85

22 70 55 70

55 33 30 65 22 33 30 65

15 20 15 15 20 15

79