Design and Analysis of Algorithms

Lecture-15

Manoj Mishra (Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
 Unit-2

Red-Black Tree
 Red-Black Tree
Binary Search Tree(BST)
A binary tree is said to be binary search tree if the
value at the left child is less than value at the parent
node and value at the right child is greater or equal
than value at the parent node.
Example:
 Red-Black Tree
Definition
A red-black tree is a binary search tree that satisfies
the following red-black properties:
1. Every node is either red or black.
2. The root is black.
[Link] color of every leaf node is black and its value is
always NIL.
4. If a node is red, then both its children are black.
[Link] each node, all simple paths from the node to
descendant leaves contain the same number of black
nodes.
 Red-Black Tree
Example:
 Red-Black Tree
Sentinel
For a red-black tree T, the sentinel is an object with
the same attributes as an ordinary node in the tree.
Its color is black and its value is nil. It is represented
by [Link] or nil[T].
A Sentinel is a special dummy node that replaces all null pointers in a

black tree
 Red-Black Tree
Red-Black tree without leaf node
 Red-Black Tree
Black height of a node
Black height of a node x in the red-black tree is the
number of black nodes on any downward path from
node x to a leaf node but not including node x. It is
denoted by bh(x).

Black height of a Red-Black tree

Black height of a red-black tree is equal to the black
height of the root node.
 Red-Black Tree
Theorem: A red-black tree with n internal nodes has height at most
2lg(n+1).
Proof: Before proving the theorem, first we will prove the following
statement.
“The subtree rooted at any node x contains at least 2bh(x)-1 internal
nodes.” ……………………………. (1)
We will prove the statement (1) using induction method. We will use
induction parameter as the height of the red-black tree.
For height, h = 0.
Red-black tree of height 0 is only single node i.e. it will be following :-
x nil

Clearly, minimum number of internal nodes in this tree = 0

and 2bh(x)-1 = 20-1 = 1-1 = 0
Therefore, statement (1) is true for height h=0.
 Red-Black Tree
For height, h = 1.
Red-black tree of height h = 1 will be the following:-
x

nil nil

Clearly, minimum number of internal nodes in this tree = 1

And 2bh(x)-1 = 21-1 = 2-1 = 1
Therefore, statement (1) is also true for height h=1.
Now, we assume statement (1) is true for children of node x.
We will prove the statement for node x.
 Red-Black Tree
Now,
The minimum number of internal nodes in the subtree rooted at node x
= Minimum number of internal nodes in the subtree rooted at left child
of node x + Minimum number of internal nodes in the subtree rooted at
right child of node x + 1
Since black height of each child of node x has either bh(x) or bh(x)-1,
depending on the color of child. If the color of the child is red then black
height of child is bh(x) but if the color of the child is black then black
height of child is bh(x) -1. Therefore,
The minimum number of internal nodes in the subtree rooted at node x
= 2 (bh(x) -1) -1+ 2 (bh(x) -1) -1 + 1
= 2 . 2 (bh(x) -1) -1
= 2 bh(x) -1
Therefore, statement (1) is also proved for node x of any height.
 Red-Black Tree
Now, we will prove the given theorem using statement (1).
Let h is the height of the red-black tree.
Using property (4) of the red-black tree, minimum number of black
nodes on any path from root node to the leaf node will be h/2.
Therefore, minimum black height of red-black tree of height h will be
h/2.
Now, the minimum number of internal nodes in red-black tree of height
h = 2h/2 - 1
Since the gien number of internal nodes in red-black tree is n, therefore
2h/2 – 1 ≤ n ⇒ 2h/2 ≤ n +1
⇒ h/2 ≤ lg(n +1) ⇒ h ≤ 2lg(n +1)
Therefore, the maximum height of red-black tree will be 2lg(n+1).
Now, it is proved.
 Design and Analysis of Algorithms

Lecture-16

Manoj mishra (Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
 Rotation operation
We use two types of rotations in the insertion and deletion of a node in
the red-black tree.
(1) Left rotation
(2) Right rotation
Left rotation algorithm
 Left rotation algorithm
.
 Right rotation algorithm
RIGHT-ROTATION(T, y)
1. x = [Link]
2. [Link] = [Link]
3. if [Link] ≠ [Link]
4. [Link].p = y
5. x.p = y.p
6. if y.p = = [Link]
7. [Link] = x
8. else if y = = [Link]
9. [Link] = x
10. else [Link] = x
11. [Link] = y
12. y.p = x
 Insertion operation
Suppose we want to insert a node z into red-black tree T. We use the
following steps for this purpose:-
1. Insert node z into red-black tree using binary search tree insertion
process.
2. Make the color of new node z to be red.
3. If the color of parent of node z is black then we make the color of
root node to be black and stop the process.
4. Otherwise we maintain the properties of red-black tree using the
following procedure.
(4-a) We start a loop and continue until color of parent of
node z turns black.
(4-b) If parent of node z is the left child of its parent then we
do the following actions:-
(4b-i) Find the sibling of parent of node z i.e. uncle of z.
Let it is denoted by node y.
 Insertion operation
(4b-ii) Now, there will be three cases.
Case-1: If color of y is red then we do the following actions:-
(1) [Link] = black
(2) [Link] = black
(3) [Link] = red
(4) z = z.p.p
Case-2: If color of y is black and z is right child then we do
following actions:-
(1) z = z.p
(2) Perform left rotation at node z.
Case-3: If color of y is black and z is left child then we do
following actions:-
(1) [Link] = black
(2) [Link] = red
(3) Perform right rotation at node z.p.p i.e. at grandparent of z
 Insertion operation
(4-c) If parent of node z is the right child of its parent then we
do the following actions:-
(4c-i) Find the sibling of parent of node z i.e. uncle of z.
Let it is denoted by node y.
(4c-ii) Now, there will be three cases.

Case-1: If color of y is red then we do the following

actions:-
(1) [Link] = black
(2) [Link] = black
(3) [Link] = red
(4) z = z.p.p
 Insertion operation
Case-2: If color of y is black and z is left child then we do
following actions:-
(1) z = z.p
(2) Perform right rotation at node z.
Case-3: If color of y is black and z is right child then we do
following actions:-
(1) [Link] = black
(2) [Link] = red
(3) Perform left rotation at node z.p.p i.e. at grandparent
of z
(4-d) After exit from the loop, we make the color of root node to
be black i.e.
[Link] = black
 Insertion Algorithm 2
1- If tree is empty, create new node as root node with color black.
2- If tree is not empty, create new node as leaf node with color RED.
3- If parent of new node is black then exit.
4- If parent of new node is RED, then check the color of parent’s
sibiling of new node:
(a) If color is black or null then do suitable rotation and recolor.
(b) If color is RED then recolor and also check if parent’s parent of
new node is not root node then recolor it and recheck.
------------------------------------------------------------------------------------------
- Root = Black
- No two adjacent RED nodes
- Count no. of black nodes in each path
Insertion operation
 Insertion operation
Example: Create the red-black tree by inserting following sequence of
numbers:- 8, 18, 5, 15, 17, 25, 40 and 80.
Initially, red-black tree is empty.
Solution: Initially tree is empty. First insert element 8.

z 8 8
⇒

Now, Insert next element 18. 8

18 z

Now, Insert next element 5.

8
z
5 18
 Insertion operation
Now, Insert next element 15.
8 z
8

5 18
5 18
y ⇒
z 15
15

5 18
⇒

15
 Insertion operation
Now, Insert next element 17.
8
8
5 18
5 18
y
y ⇒ 17
15
15
17 z z
8

5 17

⇒ 15
18

z
 Insertion operation
Now, Insert next element 25.

8
8
z
5 17 ⇒ 5 17

18
18 15
15
y 25
z 25
 Insertion operation
Now, Insert next element 40.
8

5 17
8

17 25
5 15
⇒
18
15 18 40

y
25 z
40
z
 Insertion operation
Now, Insert next element 80.
8 8
17 17
5
25
5 y z
25
15 ⇒ 15

18 40 18 40

y
80 17 80
z 25 z
8

40
18
⇒ 5 15

80
Final red-black tree
Insertion Algorithm
Insertion Algorithm

Time complexity of
insertion algorithm is
θ(log n).
 Question
Insert the following elements into
Red-Black tree:
10,18,7,15,16,30,25,40,60,2,1,70
 Design and Analysis of Algorithms

Lecture-17

Manoj Mishra (Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
 Deletion operation
Suppose we want to delete a node z from a red-black tree T.
We use the following steps for this purpose:-
1. First we delete node z using binary search tree deletion
process.
2. Find node y in the following way:-
 If node z has two children then y will be successor of z
otherwise y will be z.
3. After finding y, we find x in the following way:-
 If node y has left child then x will be left child of y
otherwise x will be right child of y.
4. If color of y is red, then we terminate the process.
5. If color of y is black, then we maintain the properties of
red-black tree in the following way:-
 Deletion operation
(5-a) We start and continue a loop if x is not root node and color of x is
black.
(5-b) if x is the left child then we do the following actions:-
(i) Find sibling of x. Let it is denoted by w.
(ii) There will be four cases:-
Case-1: If color of w is red, then we do the following
actions:-
(1) [Link] = black
(2) [Link] = red
(3) Apply left rotation at parent of node x.
Case-2: If color of w is black and color of its both children is also
black, then we do the following actions:-
(1) [Link] = red
(2) x = x.p
 Deletion operation
Case-3: If color of w is black and color of its left child is red
and color of its right child is black, then we do the
following actions:-
(1) [Link] = black
(2) [Link] = red
(3) Apply right rotation at node w.
Case-4: If color of w is black and color of its right child is red,
then we do the following actions:-
(1) [Link] = black
(2) [Link] = [Link]
(3) [Link] = black
(4) Apply left rotation at parent of node x.
(5) x = [Link]
 Deletion operation
(5-c) if x is the right child then we do the following actions:-
(i) Find sibling of x. Let it is denoted by w.
(ii) There will be four cases:-
Case-1: If color of w is red, then we do the following
actions:-
(1) [Link] = black
(2) [Link] = red
(3) Apply right rotation at parent of node x.
Case-2: If color of w is black and color of its both
children is also black, then we do the following
actions:-
(1) [Link] = red
(2) x = x.p
 Deletion operation
Case-3: If color of w is black and color of its right child is red and color
of its left child is black, then we do the following actions:-
(1) [Link] = black
(2) [Link] = red
(3) Apply left rotation at node w.
Case-4: If color of w is black and color of its left child is red, then we do
the following actions:-
(1) [Link] = black
(2) [Link] = [Link]
(3) [Link] = black
(4) Apply right rotation at parent of node x.
(5) x = [Link]
(5-d) After exit from the loop, we make the color of node x to the black
i.e. [Link] = black
 Deletion Steps
Step1:
•Perform BST deletion.
Step2:
Case 1: If node is to be deleted is RED, just delete it.
Case2: If root is DB(Double Black), just remove DB.
Case3: If DB’s sibiling is BLACK & both its children are black:
 Remove DB
Add BLACK to its parent(P):
3.1 : If P is RED its becomes black.
3.2: If P is BLACK it becomes double black(DB)
 Make sibiling RED.
If still DB exist, apply other cases.
Case 4: If DB’s sibiling is RED:
Swap colors of parents & its sibiling.
Rotate parent in DB direction.
Re-apply cases.
 Deletion Steps Contd..
Case5: DB’s sibiling is BLACK, sibiling’s child who is far from
DB is BLACK, but near child to DB is RED:
•Swap color of DBs sibiling & sibiling child who is near to
DB.
•Rotate sibiling in opposite direction to DB.
•Apply Case 6
Case 6:
•Swap color of parent & sibiling
•Rotate parent in DB’s direction
•Remove DB
•Change color of RED child to BLACK.
Deletion operation
Deletion operation
Binary search tree deletion
45

25 60

10
72
35 50

15 65 80
47
 Deletion operation
Example: Consider the following red-black tree
47

32 71

z
87
65

82
93 y

Delete the element 87, 32 and 71 in order.

 Deletion operation
Deletion of 87
47

47
32 71

32 71
93
z 65

65
87 ⇒
82
x=nil
93 y
82

x=nil
 Deletion operation
Deletion of 32

47
47

y w
x=nil 71
32
z
71
⇒
93
93 65
x=nil 65

82
82
 Deletion operation
Deletion of 32(continue)
71
71

⇒ 93
47 93 ⇒ x 47

x=nil 65 82
65 82

w 71

47 93
⇒
65 82
 Deletion operation
Deletion of 71

71
z
82

93
47 ⇒ 47 93

65 82 y 65

Final tree
x=nil
 Deletion operation
Example: Consider the following red-black tree
61

52 85

20 76 95
55
16

90 98
71 82

65

Delete the element 20, 85, 95 and 98 in order.

 Deletion operation
Deletion of 20
61

61 52 85
⇒
52 85 16 55
z 76 95
x
20 55 76 95 71 82 90 98
y x
16 65
71 82 90 98
x
65
 Deletion operation
Deletion of 85
61

52
61
⇒ 90

52 85
z 16 55 76 95

16 55 76 95 71 x=nil
82 98

71 65 w
82 90 98

65
y
x=nil
 Deletion operation
Deletion of 85(continue)
61
61

52 90
52 90 ⇒
16 55
16 55 76 95
76 95
⇒ x 71 82
71 82 98
98
65
65
 Deletion operation
Deletion of 95
61

61 52 90
⇒
52 90 16 55 76
y 98
16 55 76 95 71 82
z
71 82 65
98
x
65
 Deletion operation
Deletion of 98

61
61
52 90
52 90
⇒ w
16 55
y 76 x = nil
16 55 76 98
71 82
z
71 82 x = nil
65
65
 Deletion operation
Deletion of 98(continue)

61
61
52 76
⇒ 52 76
⇒ x
16 55 90
71
16 55 90
71 82
65
82
65 x = nil
w Final red-black tree
 AKTU EXAM. QUESTION

1. Insert the elements 8, 20, 11, 14, 9, 4, 12 in a Red-Black

Tree and delete 12, 4, 9, 14 respectively.
2. What is Red-Black tree? Write an algorithm to insert a
node in an empty red-black tree explain with suitable
example.
3. Insert the following element in an initially empty RB-Tree.
12, 9, 81, 76, 23, 43, 65, 88, 76, 32, 54. Now Delete 23 and
81.
4. Write the properties of Red-Black Tree. Illustrate with an
example, how the keys are inserted in an empty red-black
tree.
 Design and Analysis of Algorithms

Lecture-18

Manoj Mishra (Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
B-Tree
 B-Tree
Definition
•B-tree is m-way search tree.
• It is specialized multi-way tree used to store the records in a disk.
•There are number of sub-tree to each node. So that the height of the
tree is relatively small.
•Only small no. of nodes must be read from disk to retrieve an item.
•The goal of B-tree is to get fast access of the data.
•B-tree is a multi-way search tree of order ‘m’. Order ‘m’ means an
ordered tree where each node has at most ‘m’ children.
•If there are ‘n’ number of children in a node then (n -1) is the number
of keys in the node.
 B-Tree Property
•Balance M-way tree.
•Generalization of BST in which a node can have more than 1 key and
more than two children.
•Maintains sorted data(Ascending)
•All leaf node must be at same level.
•B-tree of order m has following properties:
•(a) Every node has max. m children.
•(b) min children:
leaf=0
root = 2
internal node = ceil(m/2)
•Every node has max. (m-1) keys.
•Min Keys:
Root node = 1
all others node = ceil(m/2) – 1
 Properties of B-Trees
Balanced Structure:
A B-tree is a self-balancing tree, ensuring that the height of the tree remains
relatively constant, which results in efficient data access operations.
The balance is maintained through a set of rules, and these rules are followed during
insertion and deletion operations.
Multiple Children:
Unlike binary trees, B-trees can have more than two children for each node. A B-tree
of order 'm' can have at most 'm' children.
Sorted Keys:
The keys in a B-tree node are stored in sorted order. This allows for efficient
searching and range queries.
Variable Node Sizes:
B-trees allow for variable node sizes, which means that the number of keys in a node
can vary within a specified range.
 Structure of a B-Tree
A B-tree node can have the following components:
Keys: The data items stored in the tree.
Pointers: Pointers to child nodes.
Leaf/Non-Leaf Indicator: A flag to distinguish between
leaf and non-leaf nodes.
 Operations on B-Trees
Insertion:
When inserting a new key, the B-tree follows these steps:
•Locate the appropriate leaf node where the key should be
inserted.
•Insert the key in sorted order within the leaf node.
•If the leaf node becomes too full after the insertion, it may
need to be split into two nodes, and the median key is
pushed up to the parent node.
•Continue the process up the tree, potentially splitting
nodes and promoting median keys until the root node is
reached.
 Deletion:
When deleting a key, the B-tree follows these steps:
•Locate the leaf node containing the key.
•Remove the key from the leaf node.
•If the number of keys in the node falls below a certain
threshold, borrow or merge keys from neighboring
nodes to rebalance the tree.
•Continue the rebalancing process up the tree until
the root node is reached.
 Search:
Searching in a B-tree is similar to binary
search, where you compare the target key
with the keys in each node to navigate
through the tree.
 Advantages of B-Trees
•Balanced Structure: B-trees maintain balance, ensuring consistent
performance for data access operations.
Efficient Disk Access: B-trees are well-suited for secondary storage
systems like hard drives, as they minimize the number of disk
accesses during data retrieval.
Range Queries: B-trees are efficient for range queries due to their
sorted key structure.
Scalability: B-trees can manage large datasets effectively.
 Applications of B-Trees
File Systems: B-trees are used to organize file systems
efficiently, ensuring fast file access.
Databases: B-trees are commonly used to index data in
database systems, enabling quick query execution.
DNS Servers: B-trees are used in DNS servers to store
domain names and IP addresses.
File Organization: B-trees are used in external sorting and
indexing in various file management systems.
 B-Tree
Theorem: If n ≥ 1, then for any n-key B-tree T of height h and minimum
degree t ≥ 2,
h≤ logt(𝑛+1)
2
Proof: To prove this, first we will find the minimum number of keys in
the B-tree with minimum degree t and height h.
Consider following structure of B-tree with minimum keys:-
h=0 1 ………..……………………………………..………. 1

h=1 ………..………………… ……. 2(t-1)

t-1 t-1

t-1 ……….t.……… t-1 ………..…t…… t-1 …….. 2t(t-1)

h=2 t-1
. .
h=3 …………………………………………………………………………………………..………. …….. …….. 2t2(t-1)
h=4 …………………………………………………………………………………………..………. ……….….. 2t3(t-1)

at h ………………………………………………………………………………………………………..………. 2th-1(t-1)
 B-Tree
Therefore, the minimum number of the keys in B-tree with
minimum degree t and height h
= 1+ 2(t-1) + 2t(t-1) + 2t2(t-1) + 2t3(t-1) + …….+2th-1(t-1)
= 1 + 2(t-1) ( 1 + t + t2 + t3 + ………… + th-1 )
= 1 + 2(t-1) (th−1)
(t−1)
= 1 + 2(th-1)
= 1 + 2th-2
= 2th-1
Now, since the number of keys in given B-tree is n, therefore
(𝑛 +1) (𝑛 +1)
2t -1 ≤ n ⇒ t ≤
h h ⇒ h≤ logt
2 2
It is proved.
 B-Tree
Question: As a function of the minimum degree t , what is
the maximum number of keys that can be stored in a B-tree
of height h?
Solution: Consider following structure of B-tree with
maximum keys:-
h=0 ………..………………… ……. (2t-1)
2t-1

h=1 2t-1 …..……….2t….……..……. 2t-1 ………..………… 2t(2t-1)

.

h=2 2t-1 ……2t….… 2t-1 .…….… 2t-1 ……..2t…. 2t-1 … (2t)2(2t-1)

…………………………………………………………………………………………..………. (2t)3(2t-1)

at h …………………………………………………………………………………………..………. (2t)h(2t-1)
 B-Tree
Therefore maximum number of keys in B-tree with minimum degree t
and height h
= (2t-1) + 2t (2t-1) + (2t)2(2t-1) + (2t)3(2t-1) + …………….. + (2t)h(2t-1)
= (2t-1) (1+2t + (2t)2+ (2t)3 + …………………..+ (2t)h )
((2t)h +1 −1)
= (2t-1)
(2t−1)
= (2t)h +1 −1
 B-Tree
Note:
The simplest B-tree occurs when t = 2. Every internal node
then has either 2, 3, or 4 children, and we have a 2-3-4 tree.
In practice, however, much larger values of t yield B-trees
with smaller height.
 B-Tree of order m
B-tree of order m is a tree which satisfies the following properties:

1. Every node has at most m children.

2. Every non-leaf node (except root) has at least ⌈m/2⌉ child
nodes.
3. The root has at least two children if it is not a leaf node.
4. A non-leaf node with k children contains k − 1 keys.
5. All leaves appear in the same level and carry no information.

Each internal node's keys act as separation values which divide its
subtrees. For example, if an internal node has 3 child nodes (or
subtrees) then it must have 2 keys: a1 and a2. All values in the
leftmost subtree will be less than a1, all values in the middle
subtree will be between a1 and a2, and all values in the rightmost
subtree will be greater than a2.
 Searching operation in B-Tree
Searching a B-tree is much like searching a binary search tree, except
that instead of making a binary, or “two-way,” branching decision at
each node, we make a multiway branching decision according to the
number of the node’s children.
 Searching operation in B-Tree
 B-TREE-SEARCH takes as input a pointer to the root node x
of a subtree and a key k to be searched for in that subtree.
 The initial call of this algorithm will be
B-TREE-SEARCH([Link], k)
 If k is in the B-tree, B-TREE-SEARCH returns the ordered
pair (y, i) consisting of a node y and an index i such that
[Link] = k. Otherwise, the procedure returns NIL.
Design and Analysis of Algorithms

Lecture-19

Manoj Mishra (Assistance Professor)

Department of Computer Science and

Engineering United College of Engineering and
Research, Prayagraj
 B-Tree creation
Example: Create B-tree for the following elements with minimum
degree t = 2.
F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E
Solution:
Minimum number of keys in a node = t-1 = 1
Maximum number of keys in a node = 2t-1 = 3
Initial consider 2t-1 elements in the sequence i.e. 3 elements. These are
F, S and Q. B-tree for this will be
F Q S
After inserting next element K, the B-tree will be
Q

F K S
 B-Tree
After inserting next element C, the B-tree will be
Q

C F K S
After inserting next element L , the B-tree will be
F Q
C K L S

After inserting next element H,T, and V, the B-tree will be

F Q

C H K L S T V
 B-Tree
After inserting next element W, the B-tree will be
F Q T

C H K L S V W

Now, insert element M. Since root node is full,

therefore first, we split it.

Q
F T

C H K L S V W
 B-Tree
. After splitting and inserting M, B-tree will be
Q
F K T

C H L M S V W

After inserting next element R and N, the B-tree will be

Q
F K T

C H L M N R S V W
 B-Tree
After inserting next element P, the B-tree will be

Q
F K M T

C H L N P R S V W

After splitting and inserting next element A, B and X, the B-tree will be
K Q
F M T

AB C H L N P R S V WX
 B-Tree
After splitting and inserting next element Y, the B-tree will be

K Q
F M T W

AB C H L N P RS V X Y
After splitting and inserting next element D, the B-tree will be
K Q
B F M T W

A C D H L N P RS V X Y
 B-Tree
After inserting next element Z and E, the B-tree will be

K Q
B F M T W

A C D E H L N P R S V X Y Z

Final B-Tree
 B-Tree
Example: Create B-tree for the following elements with minimum
degree t = 3.
F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E, G, I.
Example: Insert the following keys in a 2-3-4 B Tree:
40, 35, 22, 90, 12, 45, 58, 78, 67, 60
Example: Using minimum degree ‘t’ as 3, insert following sequence of
integers
10, 25, 20, 35, 30, 55, 40, 45, 50, 55, 60, 75, 70, 65, 80, 85 and 90
in an initially empty B-Tree. Give the number of nodes splitting
operations that take place.
B-Tree Insertion Algorithm
 B-Tree Insertion Algorithm
Splitting the root with t = 4. Root node r splits in two, and a new root
node s is created. The new root contains the median key of r and has
the two halves of r as children. The B-tree grows in height by one when
the root is split.
B-Tree Insertion Algorithm
 B-Tree Insertion Algorithm
Splitting a node with t = 4. Node y = [Link] splits into two nodes,
y and z, and the median key S of y moves up into y’s parent.
B-Tree Insertion Algorithm

Time complexity of
insertion algorithm
= O(th)
= O(t logtn)
Design and Analysis of Algorithms

Lecture-20

Manoj Mishra(Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
 Deletion operation
Procedure: Suppose we want to delete key k from the B-tree
with minimum degree t. Then we use following steps for this
purpose:-
[Link] the key k is in node x and x is a leaf, then delete the key k
from x.
[Link] the key k is in node x and x is an internal node, then we
do the following:
2a. If the child y that precedes k in node x has at least t
keys, then find the predecessor k’ of k in the subtree
rooted at y. Recursively delete k’, and replace k by k’ in x.
 Deletion operation
2b. 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 k’ of k in the
subtree rooted at z. Recursively delete k’ , and replace
k by k’ in x.
2c. 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.
 Deletion operation
3. If the key k is not present in internal node x, then determine the
root [Link] of the appropriate subtree that must contain k, if k is in
the tree at all. If [Link] has only t-1 keys, execute step 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.
3a. If [Link] has only t-1 keys but has an immediate sibling with at
least t keys, give [Link] an extra key by moving a key from x down
into [Link], moving a key from [Link]’s immediate left or right sibling
up into x, and moving the appropriate child pointer from the
sibling into [Link] .
3b. If [Link] and both of [Link]’s immediate siblings have t-1 keys,
merge [Link] with one sibling, which involves moving a key from x
down into the new merged node to become the median key for
that node.
 Deletion operation
Example: Consider the following B-tree with minimum degree t = 3.

Delete the following elements from this B-tree in-order.

F, M, G, D and B.
 Deletion operation
Solution:
Deletion of F
 Deletion operation
Deletion of M
 Deletion operation
Deletion of G
 Deletion operation
Deletion of D
 Deletion operation
Deletion of D
 Deletion operation
Deletion of B

Final B-tree
Time complexity of deletion operation is O(th) i.e.
O(th) = O(t logt n)
 AKTU Questions
1. Discuss the advantages of using B-Tree. Insert the following
Information 86, 23, 91, 4, 67, 18, 32, 54, 46, 96, 45 into an empty
B-Tree with degree t = 2 and delete 18, 23 from it.
2. Define a B-Tree of order m. Explain the searching operation in a
B-Tree.
3. Using minimum degree ‘t’ as 3, insert following sequence of
integers 10, 25, 20, 35, 30, 55, 40, 45, 50, 55, 60, 75, 70, 65, 80,
85 and 90 in an initially empty B-Tree. Give the number of nodes
splitting operations that take place.
4. Insert the following information F, S, Q, K, C, L, H, T, V, W, M, R, N,
P, A, B, X, Y, D, Z, E, G, I. Into an empty B-tree with degree t=3.
5. Prove that if n>=1, then for any n-key B-Tree of height h and
minimum degree t >=2, h<=log t ((n +1)/2).
6. Insert the following keys in a 2-3-4 B Tree: 40, 35, 22, 90, 12, 45,
58, 78, 67, 60 and then delete key 35 and 22 one after other.
 Design and Analysis of Algorithms

Lecture-21

Manoj Mishra (Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
Binomial Heap
 Binomial Tree
Definition
The binomial tree Bk is an ordered tree defined recursively.
1. The binomial tree B0 consists of a single node.
2. The binomial tree Bk consists of two binomial trees Bk−1 i.e.
Bk = Bk-1 + Bk-1
They are linked together in the following way:
The root of one is the leftmost child of the root of the other.
Example: Some binomial trees are the following:-
B0:
 Binomial Tree
Example: Some binomial trees are the following:-
B 0: B 1: B2:

B3:
B4:
 Properties of binomial trees
For the binomial tree Bk,
1. There are 2k nodes.
2. The height of the tree is k.
𝑘
3. There are exactly nodes at depth i for i = 0, 1, ..., k.
𝑖
4. The root has degree k, which is greater than that of any other
node. Moreover if the children of the root are numbered from left
to right by k−1, k−2, ..., 2, 1, 0, then child i is the root of a subtree
Bi.
 Properties of binomial trees(cont.)
Proof: The proof is by induction on k. For each property, the
basis is the binomial tree B0. Verifying that each property
holds for B0 is trivial. For the inductive step, we assume that
all the properties holds for Bk−1.
1. Since binomial tree Bk consists of two copies of binomial
tree Bk−1, therefore
Number of nodes in Bk = 2k−1 + 2k−1 = 2.2k-1 = 2k
2. Since in Bk, one Bk-1 is child of the other Bk-1, therefore
the height of Bk = the height of Bk-1 +1
= (k-1) + 1
=k
 Properties of binomial trees(cont.)
[Link] D(k, i) be the number of nodes at depth i of binomial
tree Bk. Since Bk is composed of two copies of Bk−1 linked
together, a node at depth i in Bk−1 appears in Bk once at depth
i and i in Bk is the number of nodes at depth i in Bk−1 plus the
number of nodes at depth i−1 in Bk−1. Thus,
D(k,i) = D(k-1,i) + D(k-1, i-1)
𝑘−1 𝑘−1
= +
𝑖 𝑖−1
𝑘
=
𝑖
 Properties of binomial trees(cont.)
4. The only node with greater degree in Bk than in Bk−1 is the root,
which has one more child than in Bk−1. Since the root of Bk−1 has
degree k−1, therefore the root of Bk has degree k.

Now, by the inductive hypothesis, and as figure shows, from left to

right, the children of the root of Bk−1 are roots of Bk−2, Bk−3, ..., B0. When
Bk−1 is linked to Bk−1, therefore, the children of the resulting root are
roots of Bk−1, Bk−2, ..., B0.
 Binomial Tree
Lemma: The maximum degree of any node in an n-node
binomial tree is lg n.
Proof: Let the maximum degree of any node is k.
According to property (4), the root node has a maximum
degree . Therefore degree of root node is k. This imply that
the binomial tree will be Bk.
According to property (1), the total number of nodes in
binomial tree Bk is 2k. Since the number of nodes in binomial
tree is n, therefore
2k = n ⇒ k = lg n
It is proved.
 Binomial Heap
Definition: A binomial heap H is a set of binomial trees that satisfies the
following binomial heap properties.
[Link] binomial tree in H obeys the min-heap property: the key of a
node is greater than or equal to the key of its parent. We say that each
such tree is min-heap-ordered.
[Link] any non-negative integer k, there is at most one binomial tree in H
whose root has degree k.

Note: An n-node binomial heap H consists of at most ⌊lg n⌋ + 1 binomial

trees.
Example: Construct binomial heap for 27 nodes.
Solution: First we find binary number of 27. After it, we compare this
number with B4B3B2B1B0. If the corresponding binary number is 1, then
we use the corresponding binomial tree in the Binomial heap.
Binary number of 27 = 11011
Therefore, binomial tree in binomial heap will be B4, B3, B1, B0.
 Binomial heaps
Therefore, binomial heap for 27 nodes will be
 Representation of binomial heaps
 Each binomial tree within a binomial heap is stored in the left-child,
right-sibling representation.
 Each node x in binomial heap consists of following fields:-
Key[x]  value stored in the node x
p[x]  pointer representing parent of node x
child[x]  pointer representing left most child of node x
sibling[x]  pointer representing immediate right sibling of node x
degree[x]  the number of children of node x

p[x]
Key[x]
Degree[x]
Child[x] Sibling[x]
 Representation of binomial heaps
 The roots of the binomial trees within a binomial heap are
organized in a linked list, which we refer to as the root list.
The degrees of the roots strictly increase as we traverse the
root list.
 The sibling field has a different meaning for roots than for
non roots. If x is a root, then sibling[x] points to the next
root in the root list.
 A given binomial heap H is accessed by the field head[H],
which is simply a pointer to the first root in the root list of
H. If binomial heap H has no elements, then head[H] = NIL.
 Representation of binomial heaps
Example: Consider the following binomial heap:-

Find the representation of this binomial heap.

 Representation of binomial heaps
Representation of binomial heap is
 Design and Analysis of Algorithms

Lecture-22

Manoj Mishra (Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
 Operations defined on binomial heaps
Finding the minimum key
The procedure BINOMIAL-HEAP-MINIMUM returns a pointer to the
node with the minimum key in an n-node binomial heap H.

Note: The running time of BINOMIAL-HEAP-MINIMUM is O(lg n).

 Union of two binomial heaps
Example: Consider following two binomial heaps H1 and H2. Find the
union of these binomial heaps.
 Union oftwo binomial heaps
Solution:
Step-1: Merge both binomial heaps.

Step-2: Apply the linking process of equal degree root nodes.

Union oftwo binomial heaps
Union oftwo binomial heaps

Final binomial heap

Union oftwo binomial heaps
 Union of two binomial heaps
The BINOMIAL-HEAP-UNION procedure has two phases.
 The first phase, performed by the call of BINOMIAL-HEAP-MERGE,
merges the root lists of binomial heaps H1 and H2 into a single linked
list H that is sorted by degree into monotonically increasing order.
 In the second phase, we link roots of equal degree until at most one
root remains of each degree.

Time Complexity:
Time complexity of BINOMIAL-HEAP-UNION is O(lg n).
 Inserting a node
The following procedure inserts node x into binomial heap H,
assuming that x has already been allocated and key[x] has
already been filled in.

Time Complexity:
Time complexity of this algorithm is O(lg n).
Inserting a node into Binomial min Heap

1- Create a binomial heap H’ containing

new element
2-Apply union of two binomial min heap
H and H’
EXAMPLE:
Insert following elements in a binomial
heap
4, 6, 3, 11, 9, 5,14, 10, 21, 7, 13, 20, 2
127
 Design and Analysis of Algorithms

Lecture-23

Manoj Mishra (Assistance Professor)

Department of Computer Science and Engineering

United College of Engineering and Research,
Prayagraj
 Extracting the node with minimum key
Example: Extract the node with the minimum key from the following
binomial heap H:-

Solution: Step-1: Find the node with minimum key and remove that
node.
Extracting the node with minimum key
Step-2: Make the binomial heap H’ from children of minimum node.

Step-3: Find the union of H and H’.

Extracting the node with minimum key
The following procedure extracts the node with the minimum
key from binomial heap H and returns a pointer to the
extracted node.

Time Complexity:
Time complexity of this algorithm is O(lg n).
 Decreasing a key
Example: Decrease the value of a node y to be 7.
Decreasing a
key
 Decreasing a key
The following procedure decreases the key of a node x in a binomial
heap H to a new value k. It signals an error if k is greater than x’s current
key.

Time Complexity:
Time complexity of this algorithm is O(lg n).
 Deleting a key
Following procedure is used to delete the key value of a node.
This implementation assumes that no node currently in the
binomial heap has a key of −∞.

Time Complexity:
Time complexity of this algorithm is O(lg n).
EXAMPLE

136
 AKTU examination questions
1. Explain various properties of Binomial Tree.
2. Prove that maximum degree of any node in an n node binomial tree
is log n.
3. Explain the algorithm to extract the minimum elements in a
binomial Heap. Give an example for the same.
4. Define Binomial Heap with example.
5. Explain the algorithm to delete a given element in a binomial Heap.
Give an example for the same.
6. Explain properties of Binomial Heap. Write an algorithm to perform
uniting two Binomial Heaps. And also to find Minimum Key.
7. Explain the different conditions of getting union of two existing
binomial Heaps. Also write algorithm for union of two Binomial
Heaps. What is its complexity?
Design and Analysis of Algorithms

Lecture-24

Manoj Mishra (Assistance Professor)

Department of Computer Science and

Engineering United College of Engineering and
Research, Prayagraj
Fibonacci Heap
 Fibonacci Heap
Definition
A Fibonacci heap is a collection of rooted trees that are min-
heap ordered. That is, each tree obeys the min-heap
property: the key of a node is greater than or equal to the
key of its parent.
Example:
 Representation of Fibonacci Heap
 Circular doubly linked list is used to represent Fibonacci heap.
 Each node x in binomial heap consists of following fields:-
x.p  pointer points to parent of x
[Link]  pointer points to any child of x
[Link]  pointer points to left sibling of x
[Link]  pointer points to right sibling of x
[Link]  value stored at node x
[Link] number of children of node x
[Link]  The boolean-valued attribute indicates whether node x has lost
a child since the last time x was made the child of another node.
 Fibonacci heap H has two fields:- [Link] and H.n .
[Link]  pointer points to the root of a tree containing the
minimum key;
H.n  the number of nodes currently in H
 Representation of Fibonacci Heap
.
 Potential Function
To analyze the performance of Fibonacci heap, we use the
potential function.
We then define the potential Φ(H) of Fibonacci heap H by
Φ(H) = t(H) + 2m(H)
Where, t(H) is the number of tree in H and m(H) is the
number of marked nodes.
Example: Consider the Fibonacci heap of previous slide.
Here, t(H) = 5 and m(H) = 3. Therefore
Φ(H) = 5 + 2*3 = 11
Maximum degree
Maximum degree of any n-node Fibonacci is denoted by D(n).
D(n) ≤ ⌊log n⌋
 Amortized Cost
Amortized cost is computed for an operation. It is defined as following:-
Amortized cost = Actual cost + change in potential function due to
operation
 Mergeable-heap operations
1. Inserting a node
2. Finding the minimum node
3. Uniting two Fibonacci heaps
4. Extracting the minimum node
5. Decreasing a key
6. Deleting a node
 Inserting a node
Example: Insert a node with key 21 in the following Fibonacci
heap.
 Inserting a node
Solution: Fibonacci heap after inserting element 21 in the
Fibonacci heap.
 Inserting a node
The following procedure inserts node x into Fibonacci heap H, assuming
that the node has already been allocated and that x:key has already
been filled in.
 Inserting a node
To determine the amortized cost of FIB-HEAP-INSERT, let H be the input
Fibonacci heap and H’ be the resulting Fibonacci heap. Then,
t(H’) = t(H) + 1
and
m(H’) = m(H),
and the increase in potential = Φ(H’) - Φ(H)
= t(H’) + 2m(H’) – (t(H) + 2m(H) )
= t(H) + 1 + 2m(H) – (t(H) + 2m(H) )
=1
The actual cost = O(1), therefore
Amortized cost = Actual cost + Φ(H’) - Φ(H)
= O(1) + 1 = O(1)
 Finding the minimum node

The minimum node of a Fibonacci heap H is given by the

pointer [Link], so we can find the minimum node in O(1)
actual time. Because the potential of H does not change,
therefore the amortized cost of this operation is equal to its
O(1) actual cost.
 Uniting two Fibonacci heaps
The following procedure unites Fibonacci heaps H1 and H2, destroying
H1 andH2 in the process. It simply concatenates the root lists of H1 and
H2 and then determines the new minimum node. Afterward, the
objects representing H1 and H2 will never be used again.
 Uniting two Fibonacci heaps
Amortied cost:
The change in potential function
Φ(H) – (Φ(H1) + Φ(H2))
= t(H) + 2m(H) –(t(H1) + 2m(H1) + t(H2) + 2m(H2) )
=0
Because t(H) = t(H1) + t(H2) and m(H) = m(H1) + m(H2)
Therefore the amortized cost
= actual cost + change in potential
= O(1) + 0
= O(1)
Design and Analysis of Algorithms

Lecture-25

Manoj Mishra(Assistance Professor)

Department of Computer Science and

Engineering United College of Engineering and
Research, Prayagraj
 Extracting the minimum node
To extract the minimum key from a Fibonacci Heap, follow these
steps:
Identify the Minimum Node:
•Locate the node min\text{min}min with the smallest key, which
is the root of the minimum tree in the root list of the Fibonacci
Heap. This node is pointed to by the min\text{min}min pointer of
the heap.
Remove the Minimum Node:
•If the minimum node has no child, simply remove it from the
root list.
•If the minimum node has children, remove the minimum node
from the root list and then add each of its children to the root
list. The children become individual trees in the root list.
 Extracting the minimum node
Update the Root List:
To add the children of the minimum node to the root list:
•Make each child’s parent pointer None\text{None}None.
•Insert each child into the root list as individual trees.
Consolidate the Heap:
•The heap may now have multiple trees with the same degree (number of
children). The consolidation process merges trees with the same degree to
maintain the property that no two trees in the root list have the same degree:
Create an array A where A[i] will point to a tree of degree iii.
Traverse the root list and, for each tree x perform the following:
•While there is another tree y with the same degree as x:
•If y has a smaller key, swap x and y so that xxx has the smaller key.
•Link y as a child of xxx (making xxx the new root) and increase the
degree of X.
•Update the A array accordingly.
•After consolidation, the A array will contain pointers to unique-degree trees.
Reconstruct the root list using these trees.
 Extracting the minimum node
Update the Minimum Pointer:
After consolidation, scan the root list to find the new minimum
node and update the min\text{min}min pointer.
Decrease the Total Node Count:
Reduce the node count of the Fibonacci Heap by 1, as the
minimum node has been removed.
Summary of Operations:
Finding the minimum node: O(1)
Consolidating the heap: O(logn)
The overall time complexity of extracting the minimum key from a
Fibonacci Heap is O(logn).
 Extracting the minimum node
Example: Extract the minimum node from the following
Fibonacci heap.
 Extracting the minimum node
Solution:
Step-1:

Step-2:
 Extracting the minimum node
Step-3:

Step-4:
 Extracting the minimum node
Step-5:

Step-6:
 Extracting the minimum node
Step-7:

Step-8:
 Extracting the minimum node
Step-9:

Step-10:
 Extracting the minimum node
Step-11:

Step-12:

Final Fibonacci Heap

Extracting the minimum node
Extracting the minimum node
 Extracting the minimum node

Computation of Amortized cost:

Let H denote the Fibonacci heap just prior to the FIB-HEAP-EXTRACT-
MIN operation. Let n is the number of nodes in Fibonacci heap H. Let H’
is the Fibonacci heap after this operation. Therefore,
Actual cost = O(t(H)-1 + D(n)) = O(D(n) + t(H))
Now, t(H’) = D(n) and m(H’) = m(H)
Therefore, amortized cost = actual cost + change in potential
= O(D(n) + t(H)) + (Φ(H’) - Φ(H) )
= O(D(n) + t(H)) + (D(n) + 2m(H) – t(H) -2m(H))
= O(D(n) + t(H) + D(n) – t(H))
= O(D(n)) = O(log n))
 Decreasing a key
The decrease key operation in a Fibonacci Heap reduces the value
of a given node’s key. It is essential for algorithms like Dijkstra’s
shortest path, where updating node values frequently is necessary.
The decrease key operation may involve restructuring the heap to
maintain the Fibonacci Heap properties. There are different cases to
consider based on the node's relationship with its parent and its
position in the heap.

167
 Decreasing a key
Case 1: The New Key is Greater Than or Equal to the Parent's Key
Action: If the new key value is still greater than or equal to the key
of its parent, the structure of the heap remains unchanged.
Example: Suppose you have a Fibonacci Heap where the node x has
a key of 20, and its parent has a key of 15. If you decrease the key of
x to 18 (still greater than or equal to 15), no restructuring is needed
because the heap property is still satisfied.
Case 2: The New Key is Less Than the Parent's Key (Violating the
Min-Heap Property)
Action: If the new key is less than the key of its parent, the node x is
cut from its parent and added to the root list. This operation breaks
the node away from its parent and makes it a root node.
Example: Suppose x has a key of 20, and its parent has a key of 15. If
you decrease the key of x to 10, this violates the min-heap property.
So, x is cut from its parent and added to the root list. 168
 Decreasing a key
Sub-case: Cascading Cuts
When a node is cut and added to the root list, if its parent was
already marked (indicating a previous child was cut), the parent
must also be cut and added to the root list. This process continues
up the tree until an unmarked node or the root is reached.
Example: Consider a Fibonacci Heap with the following structure:
Node P (parent) with a key of 5 has a child node C with a key of
10, and node C has another child node x with a key of 20.
If node x is decreased to 3, it violates the heap property. Node x
is cut and moved to the root list.
If node C was already marked, it must also be cut and moved to
the root list, and this process repeats for Parent(P) if it is
marked.

169
 Decreasing a key
Case 3: The Node is Already a Root Node
Action: If the node whose key is being decreased is already a root
node, the operation simply updates the key without any further
action.
Example: Suppose a root node has a key of 25, and you decrease it
to 15. Since it's already a root node, the structure remains intact,
and only the key value is updated.
Case 4: Updating the Minimum Node
After the decrease key operation, if the node with the decreased
key value becomes smaller than the current minimum node in the
heap, the pointer to the minimum node is updated to this node.
Example: If the current minimum node has a key of 10, and you
decrease another node’s key to 5, the minimum pointer is updated
to point to the node with the key value of 5.
170
 Decreasing a key
Example: Consider following Fibonacci heap.
(1) Decrease the node with key 46 to key value 15.
(2) After this, decrease node with key 35 to key value 5.
 Decreasing a key
Solution:
(1) Decrease the node with key 46 to key value 15.
 Decreasing a key
2. Decrease the node with key 35 to key value 5.
Step-1:

Step-2:
 Decreasing a key
Step-3:

Final Fibonacci heap

Decreasing a key
Decreasing a key
 Decreasing a key
Amortized cost:
Suppose the cascading cut function is called c times.
Therefore, the actual cost of FIB-HEAP-DECREASE-KEY is O(c).
Now, Let H is the initial Fibonacci heap and H’ is the Fibonacci heap after this
operation. Therefore,
t(H’) = t(H) + c
(the original t(H) trees, c-1 trees produced by cascading cuts, and the tree
rooted at x)
Maximum number of marked nodes,
m(H’) = m(H) – c + 2
(c -1 were unmarked by cascading cuts and the last call of CASCADING-CUT
may have marked a node)
Therefore, amortized cost = O(c) + ((t(H’) + 2m(H’)) –( t(H) + 2m(H)))
= O(c) + (t(H) + c + 2(m(H) – c + 2 ) – ( t(H) + 2m(H)))
= O(c) – c + 4 = O(4) = O(1)
Thank You.