UNIT-3

Tree Data Structure

A tree is also one of the data structures that represent hierarchical data.
Suppose we want to show the employees and their positions in the hierarchical
form then it can be represented as shown below:

The above tree shows the organization hierarchy of some company. In the above
structure, john is the CEO of the company, and John has two direct reports named
as Steve and Rohan. Steve has three direct reports named Lee, Bob, Ella where Steve is a
manager. Bob has two direct reports named Sal and Emma. Emma has two direct reports
named Tom and Raj. Tom has one direct report named Bill. This particular logical structure is
known as a Tree. Its structure is similar to the real tree, so it is named a Tree. In this structure,
the root is at the top, and its branches are moving in a downward direction. Therefore, we can
say that the Tree data structure is an efficient way of storing the data in a hierarchical way.

Some basic terms used in Tree data structure.

Let's consider the tree structure, which is shown below:

o Root: The root node is the topmost node in the tree hierarchy. In other words, the root
node is the one that doesn't have any parent. In the above structure, node numbered
1 is the root node of the tree. If a node is directly linked to some other node, it would
be called a parent-child relationship.
o Child node: If the node is a descendant of any node, then the node is known as a child
node.
o Parent: If the node contains any sub-node, then that node is said to be the parent of
that sub-node.
o Sibling: The nodes that have the same parent are known as siblings.
o Leaf Node:- The node of the tree, which doesn't have any child node, is called a leaf
node. A leaf node is the bottom-most node of the tree. There can be any number of
leaf nodes present in a general tree. Leaf nodes can also be called external nodes.
o Internal nodes: A node has atleast one child node known as an internal
o Ancestor node:- An ancestor of a node is any predecessor node on a path from the
root to that node. The root node doesn't have any ancestors. In the tree shown in the
above image, nodes 1, 2, and 5 are the ancestors of node 10.
 o Descendant: The immediate successor of the given node is known as a descendant of
a node. In the above figure, 10 is the descendant of node 5

Properties of Tree data structure

o Recursive data structure: The tree is also known as a recursive data structure. A tree can be
defined as recursively because the distinguished node in a tree data structure is known as
a root node. The root node of the tree contains a link to all the roots of its subtrees. The left
subtree is shown in the yellow color in the below figure, and the right subtree is shown in
the red color. The left subtree can be further split into subtrees shown in three different
colors. Recursion means reducing something in a self-similar manner. So, this recursive
property of the tree data structure is implemented in various applications.

o Number of edges: If there are n nodes, then there would n-1 edges. Each arrow in the
structure represents the link or path. Each node, except the root node, will have atleast
one incoming link known as an edge. There would be one link for the parent-child
relationship.
o Depth of node x: The depth of node x can be defined as the length of the path from
the root to the node x. One edge contributes one-unit length in the path. So, the depth
of node x can also be defined as the number of edges between the root node and the
node x. The root node has 0 depth.
o Height of node x: The height of node x can be defined as the longest path from the
node x to the leaf node.
Implementation of Tree

The above figure shows the representation of the tree data structure in the memory. In the
above structure, the node contains three fields. The second field stores the data; the first
field stores the address of the left child, and the third field stores the address of the right
child.

Applications of trees
The following are the applications of trees:
o Storing naturally hierarchical data: Trees are used to store the data in the
hierarchical structure. For example, the file system. The file system stored on the disc
drive, the file and folder are in the form of the naturally hierarchical data and stored
in the form of trees.
o Organize data: It is used to organize data for efficient insertion, deletion and
searching. For example, a binary tree has a logN time for searching an element.
o Trie: It is a special kind of tree that is used to store the dictionary. It is a fast and
efficient way for dynamic spell checking.
o Heap: It is also a tree data structure implemented using arrays. It is used to
implement priority queues.
o B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to
implement indexing in databases.
o Routing table: The tree data structure is also used to store the data in routing tables
in the routers.

Types of Tree data structure

The following are the types of a tree data structure:
o General tree: The general tree is one of the types of tree data structure. In the
general tree, a node can have either 0 or maximum n number of nodes. There is no
restriction imposed on the degree of the node (the number of nodes that a node can
contain). The topmost node in a general tree is known as a root node. The children of
the parent node are known as subtrees.
 There can be n number of subtrees in a general tree. In the general tree, the subtrees
are unordered as the nodes in the subtree cannot be ordered.
Every non-empty tree has a downward edge, and these edges are connected to the
nodes known as child nodes. The root node is labeled with level 0. The nodes that
have the same parent are known as siblings.

o Binary tree: Here, binary name itself suggests two numbers, i.e., 0 and 1. In a
binary tree, each node in a tree can have utmost two child nodes. Here, utmost
means whether the node has 0 nodes, 1 node or 2 nodes.

Binary Tree
The Binary tree means that the node can have maximum two children. Here, binary name
itself suggests that 'two'; therefore, each node can have either 0, 1 or 2 children.
Let's understand the binary tree through an example.
The above tree is a binary tree because each node contains the utmost two children. The
logical representation of the above tree is given below:

In the above tree, node 1 contains two pointers, i.e., left and a right pointer pointing to the
left and right node respectively. The node 2 contains both the nodes (left and right node);
therefore, it has two pointers (left and right). The nodes 3, 5 and 6 are the leaf nodes, so all
these nodes contain NULL pointer on both left and right parts.

Properties of Binary Tree

Properties of Binary Search Tree
Following are some main properties of the binary search tree in C:
• All nodes of the left subtree are less than the root node and nodes of the right
subtree are greater than the root node.
• The In-order traversal of binary search trees gives the values in ascending order.
• All the subtrees of BST hold the same properties.
Example:

Binary Tree Structure in C

struct BinaryTreeNode {
int key;
 struct nodeBinaryTreeNode *left, *right;
};
here,
• key: It will be the data stored.
• left: Pointer to the left child.
• right: Pointer to the right child
Operations on BST C
• Search in BST
• Insertion in BST
• Deletion in BST

1. Search Operation on BST in C

The algorithm for the search operation is:
1. If the root is NULL or the key of the root matches the target:
a) Return the current root node.
2. If the target is greater than the key of the current root:
a) Recursively call searchNode with the right subtree of the current root and the target.
b) Return the result of the recursive call.
3) If the target is smaller than the key of the current root:
a) Recursively call searchNode with the left subtree of the current root and the target.
b) Return the result of the recursive call.

4) If the target is not found in the current subtree, return NULL.

Time Complexity: O(log n)

2. Insertion in BST

The insertNode function inserts a new node with a specific value into
a Binary Search Tree while maintaining the binary search tree
property.
Algorithm
1. If the current node is NULL
1. Return a new node created with the specified value.
2. If the value is less than the key of the current node:
1. Recursively call insertNode with the left subtree of the
current node and the value.
2. Update the left child of the current node with the result of
the recursive call.
3. If the value is greater than the key of the current node:
1. Recursively call insertNode with the right subtree of the
current node and the value.
2. Update the right child of the current node with the result of
the recursive call.
4. Return the current node (the root of the modified tree).

Time Complexity: O(log n)

4. Deletion in BST

There are few cases at the time of deleting a node in BST

Algorithm

1. If the root is NULL:

1. Return NULL (base case for recursion).
2. If the value to be deleted (x) is greater than the key of the current
root:
1. Recursively call delete with the right subtree of the current
root and the value x.
2. Update the right child of the current root with the result of
the recursive call.
3. If the value to be deleted (x) is smaller than the key of the current
root:
 1. Recursively call delete with the left subtree of the current
root and the value x.
2. Update the left child of the current root with the result of the
recursive call.
4. If the value to be deleted (x) is equal to the key of the current root:
1. If the current node has no child:
1. Free the current node.
2. Return NULL.
2. If the current node has one child:
1. Set temp to the non-null child of the current node.
2. Free the current node.
3. Return temp.
3. If the current node has two children:
1. Find the minimum node in the right subtree (temp).
2. Replace the key of the current node with the key of
temp.
3. Recursively call delete with the right subtree of the
current node and the key of temp.
5. Return the current node (the root of the modified tree).

Time Complexity: O(log n)

Types of Binary Tree:

There are four types of Binary tree:
o Full/ proper/ strict Binary tree
o Complete Binary tree
o Perfect Binary tree
o Degenerate Binary tree
o Balanced Binary tree
1. Full/ proper/ strict Binary tree
The full binary tree is also known as a strict binary tree. The tree can only be considered as
the full binary tree if each node must contain either 0 or 2 children. The full binary tree can
also be defined as the tree in which each node must contain 2 children except the leaf
nodes.

In the above tree, we can observe that each node is either containing zero or two children;
therefore, it is a Full Binary tree.

Complete Binary Tree

The complete binary tree is a tree in which all the nodes are completely filled except the last
level. In the last level, all the nodes must be as left as possible. In a complete binary tree, the
nodes should be added from the left.

The above tree is a complete binary tree because all the nodes are completely filled, and all
the nodes in the last level are added at the left first.
Perfect Binary Tree
A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf nodes
are at the same level.
Let's look at a simple example of a perfect binary tree.
The below tree is not a perfect binary tree because all the leaf nodes are not at the same
level.

Note: All the perfect binary trees are the complete binary trees as well as the full binary
tree, but vice versa is not true, i.e., all complete binary trees and full binary trees are the
perfect binary trees.
Degenerate Binary Tree
The degenerate binary tree is a tree in which all the internal nodes have only one children.
Let's understand the Degenerate binary tree through examples.
The above tree is a degenerate binary tree because all the nodes have only one child. It is
also known as a right-skewed tree as all the nodes have a right child only.

The above tree is also a degenerate binary tree because all the nodes have only one child.
It is also known as a left-skewed tree as all the nodes have a left child only.
Balanced Binary Tree
The balanced binary tree is a tree in which both the left and right trees differ by atmost 1.
For example, AVL and Red-Black trees are balanced binary tree.
Let's understand the balanced binary tree through examples.

The above tree is a balanced binary tree because the difference between the left subtree
and right subtree is zero.
The above tree is not a balanced binary tree because the difference between the left
subtree and the right subtree is greater than 1.

Binary Search Tree

A Binary Search Tree is a data structure used in computer science for organizing and storing data in a
sorted manner. Each node in a Binary Search Tree has at most two children, a left child and
a right child, with the left child containing values less than the parent node and the right child
containing values greater than the parent node. This hierarchical structure allows for

efficient searching ,insertion, and deletion operations on the data stored in the tree.

Insertion in Binary Search Tree (BST)

Given a BST, the task is to insert a new node in this BST.

Example:
How to Insert a value in a Binary Search Tree:
A new key is always inserted at the leaf by maintaining the property of the binary
search tree. We start searching for a key from the root until we hit a leaf node.
Once a leaf node is found, the new node is added as a child of the leaf node. The
below steps are followed while we try to insert a node into a binary search tree:
• Check the value to be inserted (say X) with the value of the current node
(say val) we are in:
o If X is less than val move to the left subtree.
o Otherwise, move to the right subtree.
• Once the leaf node is reached, insert X to its right or left based on the
relation between X and the leaf node’s value.
Time Complexity:
• The worst-case time complexity of insert operations is O(h) where h is
the height of the Binary Search Tree.
• In the worst case, we may have to travel from the root to the deepest
leaf node. The height of a skewed tree may become n and the time
complexity of insertion operation may become O(n).
Auxiliary Space: The auxiliary space complexity of insertion into a binary
search tree is O(1)

Searching in Binary Search Tree (BST)

Algorithm to search for a key/data in a given Binary Search Tree:

Let’s say we want to search for the number X, We start at the root. Then:
• We compare the value to be searched with the value of the root.
• If it’s equal we are done with the search if it’s smaller we know that we
need to go to the left subtree because in a binary search tree all the
elements in the left subtree are smaller and all the elements in the right
subtree are larger.
• Repeat the above step till no more traversal is possible
• If at any iteration, key is found, return True. Else False.
Time complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(h) This is because of the space needed to store the
recursion stack.

Deletion in Binary Search Tree (BST)

Given a BST, the task is to delete a node in this BST, which can be broken down
into 3 scenarios:
Case 1. Delete a Leaf Node in BST

Case 2. Delete a Node with Single Child in BST

Deleting a single child node is also simple in BST. Copy the child to the node
and delete the node.
Case 3. Delete a Node with Both Children in BST
Deleting a node with both children is not so simple. Here we have to delete the
node is such a way, that the resulting tree follows the properties of a BST.
The trick is to find the inorder successor of the node. Copy contents of the
inorder successor to the node, and delete the inorder successor.
Note: Inorder predecessor can also be used.

Note: Inorder successor is needed only when the right child is not empty. In
this particular case, the inorder successor can be obtained by finding the
minimum value in the right child of the node.
Time Complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(h)

Binary Search Tree (BST) Traversals – Inorder, Preorder, Post Order

Inorder Traversal:
Below is the idea to solve the problem:
At first traverse left subtree then visit the root and then traverse the right
subtree.
Follow the below steps to implement the idea:
• Traverse left subtree
• Visit the root and print the data.
• Traverse the right subtree
The inorder traversal of the BST gives the values of the nodes in sorted order.
To get the decreasing order visit the right, root, and left subtree.
• Input:

•
• Binary Search Tree

• Output:
Inorder Traversal: 8 12 20 22 25 30 40
Preorder Traversal: 22 12 8 20 30 25 40
Postorder Traversal: 8 20 12 25 40 30 22

Preorder Traversal:
Below is the idea to solve the problem:
At first visit the root then traverse left subtree and then traverse the right
subtree.
Follow the below steps to implement the idea:
• Visit the root and print the data.
• Traverse left subtree
• Traverse the right subtree
• Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree
• Input:

•
• Binary Search Tree

• Output:
Inorder Traversal: 8 12 20 22 25 30 40
Preorder Traversal: 22 12 8 20 30 25 40
Postorder Traversal: 8 20 12 25 40 30 22

• Postorder Traversal:
• Below is the idea to solve the problem:
• At first traverse left subtree then traverse the right subtree and
then visit the root.
Follow the below steps to implement the idea:
• Traverse left subtree
• Traverse the right subtree
• Visit the root and print the data.
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree
 • Input:

•
• A Binary Search Tree

• Output:
Inorder Traversal: 10 20 30 100 150 200 300
Preorder Traversal: 100 20 10 30 200 150 300
Postorder Traversal: 10 30 20 150 300 200 100

Balance a Binary Search Tree

Given a BST (Binary Search Tree) that may be unbalanced, convert it into a
balanced BST that has minimum possible height.
Examples :
Input:
30
/
20
/
10
Output:
20
/ \
10 30
Input:
4
/
3
/
2
/
1
Output:
3 3 2
/ \ / \ / \
1 4 OR 2 4 OR 1 3 OR ..
\ / \
2 1 4

Input:
4
/ \
3 5
/ \
2 6
/ \
1 7
Output:
4
/ \
2 6
/ \ / \
1 3 5 7
Time Complexity: O(n), As we are just traversing the tree twice. Once in
inorder traversal and then in construction of the balanced tree.
Auxiliary space: O(n), The extra space is used to store the nodes of the inorder
traversal in the vector. Also the extra space taken by recursion call stack is O(h)
where h is the height of the tree.
 Threaded Binary Tree
In the linked representation of binary trees, more than one half of the link fields
contain NULL values which results in wastage of storage space. If a binary tree
consists of n nodes then n+1 link fields contain NULL values. So in order to
effectively manage the space, a method was devised by Perlis and Thornton in
which the NULL links are replaced with special links known as threads. Such
binary trees with threads are known as threaded binary trees. Each node in a
threaded binary tree either contains a link to its child node or thread to other
nodes in the tree.

Types of Threaded Binary Tree

There are two types of threaded Binary Tree:
o One-way threaded Binary Tree
o Two-way threaded Binary Tree
One-way threaded Binary trees:
In one-way threaded binary trees, a thread will appear either in the right or left link field of a
node. If it appears in the right link field of a node then it will point to the next node that will
appear on performing in order traversal. Such trees are called Right threaded binary trees. If
thread appears in the left field of a node then it will point to the nodes inorder predecessor.
Such trees are called Left threaded binary trees. Left threaded binary trees are used less often
as they don't yield the last advantages of right threaded binary trees. In one-way threaded
binary trees, the right link field of last node and left link field of first node contains a NULL. In
order to distinguish threads from normal links they are represented by dotted lines.

The above figure shows the inorder traversal of this binary tree yields D, B, E, A, C, F. When
this tree is represented as a right threaded binary tree, the right link field of leaf node D which
contains a NULL value is replaced with a thread that points to node B which is the inorder
successor of a node D. In the same way other nodes containing values in the right link field
will contain NULL value.

Two-way threaded Binary Trees:

a) Keep the leftmost and rightmost pointer as “NULL”
b) Inorder traversal is: 1 3 5 6 7 8 9 11 13
Left- inorder predecessors(before node)
Right- inorder successor (after node)

In two-way threaded Binary trees, the right link field of a node containing NULL values is
replaced by a thread that points to nodes inorder successor and left field of a node
containing NULL values is replaced by a thread that points to nodes inorder predecessor.

The above figure shows the inorder traversal of this binary tree yields D, B, E, G,
A, C, F. If we consider the two-way threaded Binary tree, the node E whose left
field contains NULL is replaced by a thread pointing to its inorder predecessor
i.e. node B. Similarly, for node G whose right and left linked fields contain NULL
values are replaced by threads such that right link field points to its inorder
successor and left link field points to its inorder predecessor. In the same way,
other nodes containing NULL values in their link fields are filled with threads.
In the above figure of two-way threaded Binary tree, we noticed that no left thread is possible
for the first node and no right thread is possible for the last node. This is because they don't
have any inorder predecessor and successor respectively. This is indicated by threads pointing
nowhere. So in order to maintain the uniformity of threads, we maintain a special node called
the header node. The header node does not contain any data part and its left link field points
to the root node and its right link field points to itself. If this header node is included in the
two-way threaded Binary tree then this node becomes the inorder predecessor of the first
node and inorder successor of the last node. Now threads of left link fields of the first node
and right link fields of the last node will point to the header node.

Following diagram demonstrates inorder order traversal using threads.

Advantages of Threaded Binary Tree
• In this Tree it enables linear traversal of elements.
• It eliminates the use of stack as it perform linear traversal, so save
memory.
• Enables to find parent node without explicit use of parent pointer
• Threaded tree give forward and backward traversal of nodes by in-order
fashion
• Nodes contain pointers to in-order predecessor and successor
 • For a given node, we can easily find inorder predecessor and successor.
So, searching is much more easier.
• In threaded binary tree there is no NULL pointer present. Hence memory
wastage in occupying NULL links is avoided.
• The threads are pointing to successor and predecessor nodes. This makes
us to obtain predecessor and successor node of any node quickly.
• There is no need of stack while traversing the tree, because using thread
links we can reach to previously visited nodes.
Disadvantages of Threaded Binary Tree
• Every node in threaded binary tree need extra information(extra memory)
to indicate whether its left or right node indicated its child nodes or its
inorder predecessor or successor. So, the node consumes extra memory
to implement.
• Insertion and deletion are way more complex and time consuming than
the normal one since both threads and ordinary links need to be
maintained.
• Implementing threads for every possible node is complicated.
• Increased complexity: Implementing a threaded binary tree requires
more complex algorithms and data structures than a regular binary tree.
This can make the code harder to read and debug.
• Extra memory usage: In some cases, the additional pointers used to
thread the tree can use up more memory than a regular binary tree. This
is especially true if the tree is not fully balanced, as threading a skewed
tree can result in a large number of additional pointers.
• Limited flexibility: Threaded binary trees are specialized data structures
that are optimized for specific types of traversal. While they can be more
efficient than regular binary trees for these types of operations, they may
not be as useful in other scenarios. For example, they cannot be easily
modified (e.g. inserting or deleting nodes) without breaking the
threading.
• Difficulty in parallelizing: It can be challenging to parallelize operations on
a threaded binary tree, as the threading can introduce data dependencies
 that make it difficult to process nodes independently. This can limit the
performance gains that can be achieved through parallelism.
Applications of threaded binary tree –
• Expression evaluation: Threaded binary trees can be used to evaluate
arithmetic expressions in a way that avoids recursion or a stack. The tree
can be constructed from the input expression, and then traversed in-order
or pre-order to perform the evaluation.
• Database indexing: In a database, threaded binary trees can be used to
index data based on a specific field (e.g. last name). The tree can be
constructed with the indexed values as keys, and then traversed in-order
to retrieve the data in sorted order.
• Symbol table management: In a compiler or interpreter, threaded binary
trees can be used to store and manage symbol tables for variables and
functions. The tree can be constructed with the symbols as keys, and then
traversed in-order or pre-order to perform various operations on the
symbol table.
• Disk-based data structures: Threaded binary trees can be used in disk-
based data structures (e.g. B-trees) to improve performance. By threading
the tree, it can be traversed in a way that minimizes disk seeks and
improves locality of reference.
• Navigation of hierarchical data: In certain applications, threaded binary
trees can be used to navigate hierarchical data structures, such as file
systems or web site directories. The tree can be constructed from the
hierarchical data, and then traversed in-order or pre-order to efficiently
access the data in a specific order.

AVL Tree
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the
difference between heights of left and right subtrees for any node cannot be
more than one.
The difference between the heights of the left subtree and the right subtree
for any node is known as the balance factor of the node.
The AVL tree is named after its inventors, Georgy Adelson-Velsky and Evgenii
Landis, who published it in their 1962 paper “An algorithm for the organization
of information”.
Example of AVL Trees:

The above tree is AVL because the differences between the heights of left and
right subtrees for every node are less than or equal to 1.
Balance Factor (k) = height (left(k)) - height (right(k))
If balance factor of any node is 1, it means that the left sub-tree is one level
higher than the right sub-tree.
If balance factor of any node is 0, it means that the left sub-tree and right sub-
tree contain equal height.
If balance factor of any node is -1, it means that the left sub-tree is one level
lower than the right sub-tree.
An AVL tree is given in the following figure. We can see that, balance factor
associated with each node is in between -1 and +1. therefore, it is an example
of AVL tree.
Complexity

Algorithm Average case Worst case

Space o(n) o(n)

Search o(log n) o(log n)

Insert o(log n) o(log n)

Delete o(log n) o(log n)

Example of a Tree that is NOT an AVL Tree:

The above tree is not AVL because the differences between the heights of the
left and right subtrees for 8 and 12 are greater than 1.
 AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1,
0, and 1. There are basically four types of rotations which are as follows:
An AVL tree may rotate in one of the following four ways to keep itself
balanced:

1. RR Rotation
(Left Rotation)
When a node is added into the right subtree of the right subtree, if the tree
gets out of balance, we do a single left rotation.
When BST becomes unbalanced, due to a node is inserted into the right
subtree of the right subtree of A, then we perform RR rotation, RR rotation is
an anticlockwise rotation, which is applied on the edge below a node having
balance factor -2
In above example, node A has balance factor -2 because a node C is inserted in
the right subtree of A right subtree. We perform the RR rotation on the edge
below A.

LL Rotation
(Right Rotation)
If a node is added to the left subtree of the left subtree, the AVL tree may get
out of balance, we do a single right rotation.
When BST becomes unbalanced, due to a node is inserted into the left subtree
of the left subtree of C, then we perform LL rotation, LL rotation is clockwise
rotation, which is applied on the edge below a node having balance factor 2.

In above example, node C has balance factor 2 because a node A is inserted in

the left subtree of C left subtree. We perform the LL rotation on the edge
below A.
Left-Right Rotation:
3. LR Rotation
Double rotations are bit tougher than single rotation which has already
explained above. LR rotation = RR rotation + LL rotation, i.e., first RR rotation
is performed on subtree and then LL rotation is performed on full tree, by full
tree we mean the first node from the path of inserted node whose balance
factor is other than -1, 0, or 1.

A left-right rotation is a combination in which first left rotation takes place

after that right rotation executes.

Let us understand each and every step very clearly:

State Action

A node B has been inserted into the

right subtree of A the left subtree of C,
because of which C has become an
unbalanced node having balance factor
2. This case is L R rotation where:
Inserted node is in the right subtree of
left subtree of C
 As LR rotation = RR + LL rotation, hence
RR (anticlockwise) on subtree rooted at
A is performed first. By doing RR
rotation, node A, has become the left
subtree of B.

After performing RR rotation, node C is

still unbalanced, i.e., having balance
factor 2, as inserted node A is in the left
of left of C

Now we perform LL clockwise rotation

on full tree, i.e. on node C. node C has
now become the right subtree of node
B, A is left subtree of B

Balance factor of each node is now

either -1, 0, or 1, i.e. BST is balanced
now.

4. RL Rotation
As already discussed, that double rotations are bit tougher than single rotation
which has already explained above. R L rotation = LL rotation + RR rotation,
i.e., first LL rotation is performed on subtree and then RR rotation is
performed on full tree, by full tree we mean the first node from the path of
inserted node whose balance factor is other than -1, 0, or 1.
A right-left rotation is a combination in which first right rotation takes place
after that left rotation executes.

State Action

A node B has been inserted into the left

subtree of C the right subtree of A,
because of which A has become an
unbalanced node having balance factor
- 2. This case is RL rotation where:
Inserted node is in the left subtree of
right subtree of A
As RL rotation = LL rotation + RR
rotation, hence, LL (clockwise) on
subtree rooted at C is performed first.
By doing RR rotation, node C has
become the right subtree of B.

After performing LL rotation, node A is

still unbalanced, i.e. having balance
factor -2, which is because of the right-
subtree of the right-subtree node A.

Now we perform RR rotation

(anticlockwise rotation) on full tree, i.e.
on node A. node C has now become the
right subtree of node B, and node A has
become the left subtree of B.

Balance factor of each node is now

either -1, 0, or 1, i.e., BST is balanced
now.
Example of rotating a tree:

Q: Construct an AVL tree having the following elements

H, I, J, B, A, E, C, F, D, G, K, L

On inserting the above elements, especially in the case of H, the BST becomes
unbalanced as the Balance Factor of H is -2. Since the BST is right-skewed, we
will perform RR Rotation on node H.
The resultant balance tree is:
2. Insert B, A

On inserting the above elements, especially in case of A, the BST becomes

unbalanced as the Balance Factor of H and I is 2, we consider the first node
from the last inserted node i.e. H. Since the BST from H is left-skewed, we will
perform LL Rotation on node H.
The resultant balance tree is:

3. Insert E
On inserting E, BST becomes unbalanced as the Balance Factor of I is 2, since if
we travel from E to I we find that it is inserted in the left subtree of right
subtree of I, we will perform LR Rotation on node I. LR = RR + LL rotation
Advertisement
3 a) We first perform RR rotation on node B
The resultant tree after RR rotation is:

3b) We first perform LL rotation on the node I

The resultant balanced tree after LL rotation is:

4. Insert C, F, D
On inserting C, F, D, BST becomes unbalanced as the Balance Factor of B and H
is -2, since if we travel from D to B we find that it is inserted in the right subtree
of left subtree of B, we will perform RL Rotation on node I. RL = LL + RR
rotation.
4a) We first perform LL rotation on node E
Advertisement
The resultant tree after LL rotation is:

4b) We then perform RR rotation on node B

The resultant balanced tree after RR rotation is:

5. Insert G
On inserting G, BST become unbalanced as the Balance Factor of H is 2, since if
we travel from G to H, we find that it is inserted in the left subtree of right
subtree of H, we will perform LR Rotation on node I. LR = RR + LL rotation.
5 a) We first perform RR rotation on node C
The resultant tree after RR rotation is:

5 b) We then perform LL rotation on node H

The resultant balanced tree after LL rotation is:
6. Insert K

On inserting K, BST becomes unbalanced as the Balance Factor of I is -2. Since

the BST is right-skewed from I to K, hence we will perform RR Rotation on the
node I.
The resultant balanced tree after RR rotation is:

7. Insert L
On inserting the L tree is still balanced as the Balance Factor of each node is
now either, -1, 0, +1. Hence the tree is a Balanced AVL tree
Operations on an AVL Tree:
• Insertion
• Deletion
• Searching [It is similar to performing a search in BST]

Insertion in an AVL Tree

Insertion in AVL Tree:

To make sure that the given tree remains AVL after every insertion, we must
augment the standard BST insert operation to perform some re-balancing.
Following are two basic operations that can be performed to balance a BST
without violating the BST property (keys(left) < key(root) < keys(right)).
• Left Rotation
• Right Rotation
1. A newNode is always inserted as a leaf node with a balance factor equal
to 0. After each insertion, the ancestors of the newly inserted node are
examined because the insertion only affects their heights, potentially
inducing an imbalance. This process of traversing the ancestors to find
the unbalanced node is called retracing.
Algorithm for Insertion in an AVL Tree
Step 1: START
Step 2: Insert the node using BST insertion logic.
Step 3: Calculate and check the balance factor of each node.
Step 4: If the balance factor follows the AVL criterion, go to step 6.
Step 5: Else, perform tree rotations according to the insertion done.
Once the tree is balanced go to step 6.
Step 6: END
Let's understand with an example
1. Let the initial tree be:

Let the node to be inserted be:

2. Go to the appropriate leaf node to insert a newNode using the
following recursive steps. Compare newKey with rootKey of the
current tree.
1. If newKey < rootKey, call the insertion algorithm on the left
subtree of the current node until the leaf node is reached.
2. Else if newKey > rootKey, call the insertion algorithm on the
right subtree of the current node until the leaf node is
reached.
3. Else, return leafNode.
3. Compare leafKey obtained from the above steps with newKey:
1. If newKey < leafKey, make newNode as
the leftChild of leafNode.
2. Else, make newNode as rightChild of leafNode.
4. Update balanceFactor of the nodes.
5. If the nodes are unbalanced, then rebalance the node.
1. If balanceFactor > 1, which means the height of the left
subtree is greater than that of the right subtree. So, do a
right rotation or left-right rotation
1. If newNodeKey < leftChildKey do the right rotation.
2. Else, do left-right rotation.
 2. If balanceFactor < -1, it means the height of the right
subtree is greater than that of the left subtree. So, do a right
rotation or right-left rotation
1. If newNodeKey > rightChildKey do a left rotation.
2. Else, do right-left rotation
6. The final tree is:
 Figure 1: final balanced tree

2. Deletion:A node is always deleted as a leaf node. After deleting a node,

the balance factors of the nodes get changed. To rebalance the balance
factor, suitable rotations are performed.
Algorithm for Deletion in an AVL Tree
Step 1: START
Step 2: Find the node in the tree. If the element is not found, go to step 7.
Step 3: Delete the node using BST deletion logic.
Step 4: Calculate and check the balance factor of each node.
Step 5: If the balance factor follows the AVL criterion, go to step 7.
Step 6: Else, perform tree rotations to balance the unbalanced nodes. Once the tree
is balanced go to step 7.
Step 7: END

Let's understand with an example

1. Locate nodeToBeDeleted (recursion is used to
find nodeToBeDeleted in the code used below).
2. There are three cases for deleting a node:
1. If nodeToBeDeleted is the leaf node (ie. does not have any
child), then remove nodeToBeDeleted.
2. If nodeToBeDeleted has one child, then substitute the
contents of nodeToBeDeleted with that of the child. Remove
the child.
3. If nodeToBeDeleted have two children, find the in-order
successor w of nodeToBeDeleted (ie. node with a minimum
value of key in the right subtree).
 ▪ Substitute the contents of nodeToBeDeleted with that of w.

▪ Remove the leaf node w.

3. Update balanceFactor of the nodes.

4. Rebalance the tree if the balance factor of any of the nodes is not
equal to -1, 0, or 1.
1. If balanceFactor of currentNode > 1,
1. If balanceFactor of leftChild >= 0, do right rotation.

2. Else do left-right rotation.

2. If balanceFactor of currentNode < -1,
1. If balanceFactor of rightChild <= 0, do left rotation.
2. Else do right-left rotation.
5. The final tree is:
Advantages of AVL Tree:
1. AVL trees can self-balance themselves and therefore provides time
complexity as O(Log n) for search, insert and delete.
2. It is a BST only (with balancing), so items can be traversed in sorted
order.
3. Since the balancing rules are strict compared to Red Black Tree, AVL
trees in general have relatively less height and hence the search is faster.
4. AVL tree is relatively less complex to understand and implement
compared to Red Black Trees.
Disadvantages of AVL Tree:
1. It is difficult to implement compared to normal BST and easier compared
to Red Black
2. Less used compared to Red-Black trees.
3. Due to its rather strict balance, AVL trees provide complicated insertion
and removal operations as more rotations are performed.
Applications of AVL Tree:
1. AVL Tree is used as a first example self balancing BST in teaching DSA as
it is easier to understand and implement compared to Red Black
2. Applications, where insertions and deletions are less common but
frequent data lookups along with other operations of BST like sorted
traversal, floor, ceil, min and max.
3. Red Black tree is more commonly implemented in language libraries
like map in C++, set in C++, TreeMap in Java and TreeSet in Java.
4. AVL Trees can be used in a real time environment where predictable and
consistent performance is required.

Example 2:
Let us understand with the help of an example. Consider we have following
elements given to us: [ 15 , 18 , 12 , 8 , 54 , 5 , 14 , 13 , 9 , 60].
Step 1:
 • Insert the first element 15.
• Check for the b_fact(BALANCE FACTOR) of the node.
• b_fact= 0

Step 2:

• Insert the next element 18.

• Check the b_fact (BALANCE FACTOR) each node.

Step 3:

• Insert the next element .s

• Check for the b_fact each node.
• The b_fact of each node in this case is 0.

Step 4:

• Insert the next element 8.

• Check for the b_fact of each node.

Step 5:

• Insert the next element 54.

• Check if the b_fact is anything other than -1 , 0 , 1.

Step 6:

• Insert the next element 5.

• Check the b_fact of each node.
 • We can see the b_fact of the node 12 is 2. The tree becomes
unbalanced.
• We have to balance the tree by identifying the rotation mechanism to be
applied.

Step 7:

• We observe the element is inserted to the ,left of the left subtree.

• Thus we have to apply LL Rotation.
• The nodes involved in the rotation are shown in red.

\
tep 8:

• In order to balance the tree, the tree is rotated towards the right.
• In this case the new parent is 8 and the nodes 5 and 12 becomes the
child nodes.
Step 9:

• The next element inserted in the tree is 14.

• Again check the b_fact of each node of the tree.

Step 10:

• The next element to be inserted in the tree is 13.

• After the insertion of the new node, we check for the b_fact of each
node.
• Now due to the latest insertion to the tree we can see that the balancing
factor of multiple nodes is distorted
 • We look for the first ancestor on which the balance factor is disturbed.
• We identify the rotation mechanism to be used.

Step 11:

• To balance the tree we use the RL Rotation Mechanism.

• We identify the nodes that are involved in thre rotation mechanism
which are shown in red.

Step 12:

• In this scenario, first a right rotation is applied.

• The tree after right rotation is shown as follows.

Step 13:

• Now to balance the tree, we apply a left rotation.

• After the rotation, the node 13 becomes the new parent node and the
nodes 12 and 14 become the new child nodes.
• If we check the balance factor for each node, the balance factor is eithe
0 , 1 or -1.
Step 14:

• The next element to be inserted is 9.

• As the new element is inserted, we observe that the balance factor of
the node 8 becomes (-2).

Step 15:

• We can see from the image that for balancing the tree we need to
apply RL Rotation.
• Again, first a right rotation is applied and then a left rotation is applied to
the tree structure.

Step 16:

• After applying the RL Rotation, the tree structure with the

optimal b_fact is shown as follows.
• We can see that the b_fact ranges between 0 , 1 and -1.
• Thus it is an AVL tree.
Step 17:

• The next element to be inserted is 60.

• As 60 is inserted the b_fact of the nodes of right subtree is disturbed.

Step 18:

• Since the disturbance in the balance factor is due to the insertion of an

element to the right of the right subtree, we use RR Rotation.

Step 19:

• After applying the RR Rotation the tree so obtained is shown below.

• All the nodes satisfy the condition of an AVL tree.
• The final tree at the end of insertion process with balanced nodes is
shown below.
 B Tree
The main difference between a binary search tree and a B-tree is that a B-tree
can have multiple children nodes for a parent node. However, a binary search
tree can contain only two child nodes for a parent node.
Unlike a binary search tree, a B-tree can have multiple keys in a node. The
number of keys and the number of children for any node depends on
the order of the B-tree. Keys are the values that are stored at any node. Let’s
take a look at an example of B-tree:
It can have multiple keys for a single node. A single node can have more than
two children.
All the leaf nodes must be at the same level. A leaf node is a node that doesn’t
have any child nodes.
Suppose the order of a B-tree is N. It means every node can have a maximum
of N children. Therefore, every node can have maximum N-1 keys and
minimum {(N/2)-1} keys except the root node.
Let’s take a B-tree of order N=6 . According to the properties of the B-tree, any
node can have a maximum of N-1 keys. Hence keys in this case. Furthermore,
any node can have minimum {(N/2)-1} keys. Hence, {(6/2-1)}=2 keys.

The limitations of traditional binary search trees can be frustrating. Meet the B-
Tree, the multi-talented data structure that can handle massive amounts of data
with ease. When it comes to storing and searching large amounts of data,
traditional binary search trees can become impractical due to their poor
performance and high memory usage. B-Trees, also known as B-Tree or
Balanced Tree, are a type of self-balancing tree that was specifically designed to
overcome these limitations.
Unlike traditional binary search trees, B-Trees are characterized by the large
number of keys that they can store in a single node, which is why they are also
known as “large key” trees. Each node in a B-Tree can contain multiple keys,
which allows the tree to have a larger branching factor and thus a shallower
height. This shallow height leads to less disk I/O, which results in faster search
and insertion operations. B-Trees are particularly well suited for storage systems
that have slow, bulky data access such as hard drives, flash memory, and CD-
ROMs.
B-Trees maintains balance by ensuring that each node has a minimum number
of keys, so the tree is always balanced. This balance guarantees that the time
complexity for operations such as insertion, deletion, and searching is always
O(log n), regardless of the initial shape of the tree.
Time Complexity of B-Tree:
Sr. No. Algorithm Time Complexity

1. Search O(log n)

2. Insert O(log n)

3. Delete O(log n)

B Tree is a specialized m-way tree that can be widely used for disk access. A B-
Tree of order m can have at most m-1 keys and m children. One of the main
reason of using B tree is its capability to store large number of keys in a single
node and large key values by keeping the height of the tree relatively small.
A B tree of order m contains all the properties of an M way tree. In addition,
it contains the following properties.
1. Every node in a B-Tree contains at most m children.
2. Every node in a B-Tree except the root node and the leaf node contain at
least m/2 children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.
It is not necessary that, all the nodes contain the same number of children but,
each node must have m/2 number of nodes.
A B tree of order 4 is shown in the following image.
While performing some operations on B Tree, any property of B Tree may
violate such as number of minimum children a node can have. To maintain the
properties of B Tree, the tree may split or join.

Operations
Searching :
Searching in B Trees is similar to that in Binary search tree. For example, if we
search for an item 49 in the following B Tree. The process will something like
following :
1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left
sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.
Searching in a B tree depends upon the height of the tree. The search
algorithm takes O(log n) time to search any element in a B tree.

Inserting
Insertions are done at the leaf node level. The following algorithm needs to be
followed in order to insert an item into B Tree.
1. Traverse the B Tree in order to find the appropriate leaf node at which
the node can be inserted.
 2. If the leaf node contain less than m-1 keys then insert the element in the increasing
order.
3. Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
o Split the node into the two nodes at the median.
o Push the median element upto its parent node.
o If the parent node also contain m-1 number of keys, then split it too by
following the same steps.

Example:
Insert the node 8 into the B Tree of order 5 shown in the following image.

8 will be inserted to the right of 5, therefore insert 8.

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore
split the node from the median i.e. 8 and push it up to its parent node shown
as follows.
Deletion
Deletion is also performed at the leaf nodes. The node which is to be deleted
can either be a leaf node or an internal node. Following algorithm needs to be
followed in order to delete a node from a B tree.
1. Locate the leaf node. ‘m’ is the order of tree.
2. If there are more than m/2 keys (suppose 3 keys) in the leaf node then
delete the desired key from the node.
3. If the leaf node doesn't contain m/2 keys (suppose 3 keys) then complete the keys
by taking the element from right or left sibling.
o If the left sibling contains more than m/2 elements(suppose 3+1=4 keys)
then push its largest element up to its parent and move the
intervening(existing between two) element down to the node where the
key is deleted.
o If the right sibling contains more than m/2 elements(suppose 3+1=4 keys)
then push its smallest element up to the parent and move intervening
element down to the node where the key is deleted.

4. If neither of the sibling contain more than m/2 elements(suppose 3+1=4

keys) then create a new leaf node by joining two leaf nodes
(left+right)and the intervening element of the parent node.
5. If parent is left with less than m/2 node (suppose 3-1=2 keys) then, apply
the above process on the parent too.
 Internal node deletion cases:
If the node which is to be deleted is an internal node, then replace the node
with its in-order successor or predecessor. Since, successor or predecessor will
always be on the leaf node hence, the process will be similar as the node is
being deleted from the leaf node.
Example 1
Here is a B tree of order 5 i.e m=5.
Min children are m/2 i.e 5/2 =2.5 approx ll be 3.
Max children=5
Min keys are: [m/2]-1 i.e 2 because (3-1=2)
Max keys: m-1 i.e 5-1= 4

Delete the node 53 from the B Tree of order 5 shown in the following figure.

53 is present in the right child of element 49. Delete it.

Now, 57 is the only element which is left in the node, the minimum number of elements that
must be present in a B tree of order 5, is 2(min.key should be here). it is less than that, the
elements in its left and right sub-tree are also not sufficient therefore, merge it with the left
sibling and intervening element of parent i.e. 49. Because 49 is the parent of both sides. So
while merging 57 it ll shift left side too.

The final B tree is shown as follows.

Example 2:
So:

Finally:

Second case:

Deleting 72:
After updating:

3rd case:
Neither left sibling nor right sibling have more than mi. no. of keys, then:
Ex: delete 65 now
Note; when we see 65, its left side is also min no of keys(2) and similarly in
right side also min no of keys(2). So it cant send value to them as we know min
keys are 2 and max keys should be 4. So here we’ll merge all elements with a
node value 60.
 Merging
Now after inserting 60, these are 5 keys,that ll not be possible. So now delete
65 from there. So after deleting 65 now it ll be shown like this :

We can also merge the right side of keys for balancing:

After merging the right nodes, we ll delete 65 and keys ll be 68,70,73,75

After updating:

Now delete value 20:

After merging(16 will come down):
14,15,16,20,27
Now 10 ll be alone and it ll violate the property of B tree, so we ll merge its
laeft and right parts.

Now Internal Node deletion process:

Delete 70:
 Here 68 is the largest value so replace it when we are deleting 70 . According
to inorder predecessor rule order ll be: 51,52,60,68,70 and 70 ll exchange with
68.

Application of B tree
B tree is used to index the data and provides fast access to the actual data
stored on the disks since, the access to value stored in a large database that is
stored on a disk is a very time consuming process.
Searching an un-indexed and unsorted database containing n key values needs
O(n) running time in worst case. However, if we use B Tree to index this
database, it will be searched in O(log n) time in worst case.

• It is used in large databases to access data stored on the disk

• Searching for data in a data set can be achieved in significantly less time
using the B-Tree
• With the indexing feature, multilevel indexing can be achieved.
• Most of the servers also use the B-tree approach.
• B-Trees are used in CAD systems to organize and search geometric data.
• B-Trees are also used in other areas such as natural language processing,
computer networks, and cryptography.
Advantages of B-Trees:
• B-Trees have a guaranteed time complexity of O(log n) for basic
operations like insertion, deletion, and searching, which makes them
suitable for large data sets and real-time applications.
• B-Trees are self-balancing.
• High-concurrency and high-throughput.
• Efficient storage utilization.
Disadvantages of B-Trees:
• B-Trees are based on disk-based data structures and can have a high disk
usage.
• Not the best for all cases.
• Slow in comparison to other data structures.
FOR MORE EXAMPLES: https://www.baeldung.com/cs/b-tree-data-
structure

B+ Tree

A B+ Tree is primarily utilized for implementing dynamic indexing on multiple

levels. Compared to B- Tree, the B+ Tree stores the data pointers only at the
leaf nodes of the Tree, which makes search more process more accurate and
faster.
B+ trees are employed to store enormous data that does not even fit in the
main memory. The internal nodes of the B+ Tree (nodes used to access records)
are saved to the secure memory whereas the leaf nodes are written to the
secondary memory because of limited main memory.
Rules for B+ Tree
Here are essential rules for B+ Tree.
• Leaves are used to store data records.
• It stored in the internal nodes of the Tree.
 • If a target key value is less than the internal node, then the point just to
its left side is followed.
• If a target key value is greater than or equal to the internal node, then
the point just to its right side is followed.
• The root has a minimum of two children.

Why use B+ Tree

Here, are reasons for using B+ Tree:
• Key are primarily utilized to aid the search by directing to the proper
Leaf.
• B+ Tree uses a “fill factor” to manage the increase and decrease in a
tree.
• In B+ trees, numerous keys can easily be placed on the page of memory
because they do not have the data associated with the interior nodes.
Therefore, it will quickly access tree data that is on the leaf node.
• A comprehensive full scan of all the elements is a tree that needs just
one linear pass because all the leaf nodes of a B+ tree are linked with
each other.
• An internal node of a B+ tree is commonly known as an index node.
 • Root Node
• The root node is a B+ tree topmost node. It functions as the
doorway for the searching of records in the tree. The root node
contains references to child nodes which allow traversal of the tree
structure.

• Internal Node
• The internal nodes in a B+ tree that do not store actual data
records are non-leaf nodes. Instead, they have search keys and
pointers to child nodes. Internal nodes allow fast traversal through
the tree during search operations.

• Leaf Node
• Leaf nodes are at the deepest level of a B+ tree. Different from
internal nodes, leaf nodes store data records together with pointers
to adjacent leaf nodes. Every leaf node represents a range of
values therefore they are the maximum and minimum values for
search operations.

• Search Key
• A search key is either unique attribute or one or many attributes
combined to search for specific records within a B+ tree. It is
helpful for finding the preferred data promptly. Characteristically,
the search key is either the primary key or an indexed field in the
database.

Search Operation
In B+ Tree, a search is one of the easiest procedures to execute and get fast and
accurate results from it.
The following search algorithm is applicable:
• To find the required record, you need to execute the binary search on
the available records in the Tree.
• In case of an exact match with the search key, the corresponding record
is returned to the user.
 • In case the exact key is not located by the search in the parent, current,
or leaf node, then a “not found message” is displayed to the user.
• The search process can be re-run for better and more accurate results.

Search Operation Algorithm

1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
The accurate result is returned and displayed to the user
Else, if the node being searched is the current and the exact key is not
found by the algorithm
Display the statement "Recordset cannot be found."
Output:
The matched record set against the exact key is displayed to the user;
otherwise, a failed attempt is shown to the user.

Insert Operation
The following algorithm is applicable for the insert operation:
• 50 percent of the elements in the nodes are moved to a new leaf for
storage.
• The parent of the new Leaf is linked accurately with the minimum key
value and a new location in the Tree.
• Split the parent node into more locations in case it gets fully utilized.
• Now, for better results, the center key is associated with the top-level
node of that Leaf.
• Until the top-level node is not found, keep on iterating the process
explained in the above steps.

Insert Operation Algorithm

1. Even inserting at-least 1 entry into the leaf container does not make it
full then add the record
2. Else, divide the node into more locations to fit more records.
 a. Assign a new leaf and transfer 50 percent of the node elements to a new
placement in the tree
b. The minimum key of the binary tree leaf and its new key address are
associated with the top-level node.
c. Divide the top-level node if it gets full of keys and addresses.
i. Similarly, insert a key in the center of the top-level node in the
hierarchy of the Tree.
d. Continue to execute the above steps until a top-level node is found that
does not need to be divided anymore.

3) Build a new top-level root node of 1 Key and 2 indicators.

Output:
The algorithm will determine the element and successfully insert it in the
required leaf node.
Order=4
Max child=4
Min child= m/2= 2
Max keys= (m-1)= 3
Min keys= (m/2)-1 = 1

Mid element (4/2 +1)=3rd (right ele.)

Firstly take 3 elements according to ascending order:
insert 17 and then 21:
Enter 31 and the 25:

Insert 19

Insert 20
Insert 28

Then 31 and 42

Example 2:
The above B+ Tree sample example is explained in the steps below:
• Firstly, we have 3 nodes, and the first 3 elements, which are 1, 4, and 6,
are added on appropriate locations in the nodes.
• The next value in the series of data is 12 that needs to be made part of
the Tree.
• To achieve this, divide the node, add 6 as a pointer element.
• Now, a right-hierarchy of a tree is created, and remaining data values are
adjusted accordingly by keeping in mind the applicable rules of equal to
or greater than values against the key-value nodes on the right.

Delete Operation
The complexity of the delete procedure in the B+ Tree surpasses that of the
insert and search functionality.
The following algorithm is applicable while deleting an element from the B+
Tree:
• Firstly, we need to locate a leaf entry in the Tree that is holding the key
and pointer. , delete the leaf entry from the Tree if the Leaf fulfills the
exact conditions of record deletion.
 • In case the leaf node only meets the satisfactory factor of being half full,
then the operation is completed; otherwise, the Leaf node has minimum
entries and cannot be deleted.
• The other linked nodes on the right and left can vacate any entries then
move them to the Leaf. If these criteria is not fulfilled, then they should
combine the leaf node and its linked node in the tree hierarchy.
• Upon merging of leaf node with its neighbors on the right or left, entries
of values in the leaf node or linked neighbor pointing to the top-level
node are deleted.

The example above illustrates the procedure to remove an element from the
B+ Tree of a specific order.
• Firstly, the exact locations of the element to be deleted are identified in
the Tree.
• Here the element to be deleted can only be accurately identified at the
leaf level and not at the index placement. Hence, the element can be
deleted without affecting the rules of deletion, which is the value of the
bare-minimum key.
 • In the above example, we have to delete 31 from the Tree.
• We need to locate the instances of 31 in Index and Leaf.
• We can see that 31 is available in both Index and Leaf node level. Hence,
we delete it from both instances.
• But, we have to fill the index pointing to 42. We will now look at the right
child under 25 and take the minimum value and place it as an index. So,
42 being the only value present, it will become the index.

Delete Operation Algorithm

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
A. If n is root, remove K
a. if root has more than one key, done
b. if root has only K
i) if any of its child nodes can lend a node
Borrow key from the child and adjust child links
ii) Otherwise merge the children nodes. It will be a new root
c. If n is an internal node, remove K
i) If n has at least ceil(m/2) keys, done!
 ii) If n has less than ceil(m/2) keys,
If a sibling can lend a key,
Borrow key from the sibling and adjust keys in n and the parent node
Adjust child links
Else
Merge n with its sibling
Adjust child links
d. If n is a leaf node, remove K
i) If n has at least ceil(M/2) elements, done!
In case the smallest key is deleted, push up the next key
ii) If n has less than ceil(m/2) elements
If the sibling can lend a key
Borrow key from a sibling and adjust keys in n and its parent node
Else
Merge n and its sibling
Adjust keys in the parent node

Output:
The Key “K” is deleted, and keys are borrowed from siblings for adjusting values
in n and its parent nodes if needed.
Example:

Delete 21:
Delete 31:

Delete 31 from both side(index and leaf both)

Then 42 would shift at index :

Delete 20:
20 ll ask to his right sibling(25,28) to borrow one key as it has 2 keys(more than
min keys) so it ll give 25 to it:
Sp 25 ll be passed through its parent node, then delete 20:
Delete 20 from root too:

Now put min value from its left side i.e 25:
Delete 10: simple to delete because have 2 keys

Delete 7: ask for borrowing 4 from its right side,it ll give you.
Delete 25:
Now delete 42:
UPDATE 17 ON ROOT NODE:
DELETE 4:
Summary
• B+ Tree is a self-balancing data structure for executing accurate and
faster searching, inserting and deleting procedures on data
• We can easily retrieve complete data or partial data because going
through the linked tree structure makes it efficient.
• The B+ tree structure grows and shrinks with an increase/decrease in the
number of stored records.
• Storage of data on the leaf nodes and subsequent branching of internal
nodes evidently shortens the tree height, which reduces the disk input
and output operations, ultimately consuming much less space on the
storage devices.
Advantages of B+ Tree File Organization
• This process becomes quite simple because all records are stored only in
leaf nodes and they follow a sequential linked list.
• Navigating the tree structure is simpler and quicker.
• The size of B+ tree is unlimited and thus it can grow in records while, its
structure may also decay.
• It is quite a balanced tree setup. In this case, no matter what insertion,
update or deletions across the tree one can do there is of cost about
performance.
Disadvantages of B+ Tree File Organization
• For the static method, B+ tree file organization is very inefficient.

B+ Tree vs. B Tree

Here, are the main differences between B+ Tree vs. B Tree
B+ Tree B Tree

Search keys can be repeated. Search keys cannot be redundant.

B+ Tree B Tree

Both leaf nodes and internal nodes can

Data is only saved on the leaf nodes.
store data

Data stored on the leaf node makes the Searching is slow due to data stored on
search more accurate and faster. Leaf and internal nodes.

Deletion is not difficult as an element is only Deletion of elements is a complicated and

removed from a leaf node. time-consuming process.

Linked leaf nodes make the search efficient

You cannot link leaf nodes.
and quick.

UNIT-5
Sorting Algorithms
A Sorting Algorithm is used to rearrange a given array
or list of elements according to a comparison operator
on the elements. The comparison operator is used to
decide the new order of elements in the respective
data structure.
For Example: The below list of characters is sorted in
increasing order of their ASCII values. That is, the
character with a lesser ASCII value will be placed first
than the character with a higher ASCII value.
Sorting refers to rearrangement of a given array or list
of elements according to a comparison operator on the
elements. The comparison operator is used to decide
the new order of elements in the respective data
structure. Sorting means reordering of all the elements
either in ascending or in descending order.
Sorting Terminology:
• In-place Sorting: An in-place sorting algorithm
uses constant space for producing the output
(modifies the given array only) or copying
elements to a temporary storage. Examples:
Selection Sort, Bubble Sort Insertion Sort and Heap
Sort.
• Internal Sorting: Internal Sorting is when all the
data is placed in the main
 memory or internal memory. In internal sorting,
the problem cannot take input beyond its size.
Example: heap sort, bubble sort, selection sort,
quick sort, shell sort, insertion sort.
• External Sorting : External Sorting is when all the
data that needs to be sorted cannot be placed in
memory at a time, the sorting is called external
sorting. External Sorting is used for the massive
amount of data. Examples: Merge sort, Tag sort,
Polyphase sort, Four tape sort, External radix sort,
etc.
• Stable sorting: When two same items appear in
the same order in sorted data as in the original
array called stable sort. Examples: Merge Sort,
Insertion Sort, Bubble Sort.
• Unstable sorting: When two same data appear in
the different order in sorted data it is called
unstable sort. Examples: Selection Sort, Quick Sort,
Heap Sort, Shell Sort.
Characteristics of Sorting Algorithms:
• Time Complexity: Time complexity, a measure of
how long it takes to run an algorithm, is used to
categorize sorting algorithms. The worst-case,
average-case, and best-case performance of a
 sorting algorithm can be used to quantify the time
complexity of the process.
• Auxiliary Space : This is the amount of extra space
(apart from input array) needed to sort. For
example, Merge Sort requires O(n) and Insertion
Sort O(1) auxiliary space
• Stability: A sorting algorithm is said to be stable if
the relative order of equal elements is preserved
after sorting. This is important in certain
applications where the original order of equal
elements must be maintained.
• In-Place Sorting: An in-place sorting algorithm is
one that does not require additional memory to
sort the data. This is important when the available
memory is limited or when the data cannot be
moved.
• Adaptivity: An adaptive sorting algorithm is one
that takes advantage of pre-existing order in the
data to improve performance. For example
insertion sort takes time proportional to number of
inversions in the input array.
Applications of Sorting Algorithms:
• Searching Algorithms: Sorting is often a crucial
step in search algorithms like binary search and
 Ternary Search. A lot of Greedy Algorithms use
sorting as a first step to apply Greedy Approach.
For example Activity Selection, Fractional
Knapsack, Weighted Job Scheduling, etc
• Data management: Sorting data makes it easier to
search, retrieve, and analyze. For example the
order by operation in SQL queries requires sorting.
• Database optimization: Sorting data in databases
improves query performance. We preprocess the
data by sorting so that efficient searching can be
applied.
• Machine learning: Sorting is used to prepare data
for training machine learning models.
• Data Analysis: Sorting helps in identifying patterns,
trends, and outliers in datasets. It plays a vital role
in statistical analysis, financial modeling, and other
data-driven fields.
• Operating Systems: Sorting algorithms are used in
operating systems for tasks like task scheduling,
memory management, and file system
organization.