UNIT III

NON LINEAR DATA STRUCTURES – TREES

UNIT III NON LINEAR DATA STRUCTURES – TREES 9
Introduction to Tree ADT – Implementations of trees- Binary Tree ADT -tree traversals -
expression trees –– binary search tree ADT –Threaded Binary Trees- AVL Trees –Multi-way
Search Trees-B-Tree – B+ Tree- Heap-Priority Queue.
***********************************************************************************
TREE ADT
A tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—
that simulates a hierarchical tree structure, with a root value and sub trees of children with a parent
node, represented as a set of linked nodes.
A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a
root node), where each node is a data structure consisting of a value, together with a list of references to
nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
In linear data structure, data is organized in sequential order and in non-linear data structure,
data is organized in random order. Tree is a very popular data structure used in wide range of
applications. A tree data structure can be defined as follows...
Tree is a non-linear data structure which organizes data in hierarchical structure and this
is a recursive definition.
A tree data structure can also be defined as follows...
Tree data structure is a collection of data (Node) which is organized in hierarchical
structure and this is a recursive definition
In tree data structure, every individual element is called as Node. Node in a tree data structure,
stores the actual data of that particular element and link to next element in hierarchical structure.
In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of
links.
Example

Terminology
In a tree data structure, we use the following terminology...
1. Root
In a tree data structure, the first node is called as Root Node. Every tree must have root node. We can
say that root node is the origin of tree data structure. In any tree, there must be only one root node. We
never have multiple root nodes in a tree.
2. Edge
In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree with 'N'
number of nodes there will be a maximum of 'N-1' number of edges.

3. Parent
In a tree data structure, the node which is predecessor of any node is called as PARENT NODE. In
simple words, the node which has branch from it to any other node is called as parent node. Parent node
can also be defined as "The node which has child / children".

4. Child
In a tree data structure, the node which is descendant of any node is called as CHILD Node. In simple
words, the node which has a link from its parent node is called as child node. In a tree, any parent node
can have any number of child nodes. In a tree, all the nodes except root are child nodes.

5. Siblings
In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple words,
the nodes with same parent are called as Sibling nodes.
6. Leaf
In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words,
a leaf is a node with no child.
In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node
with no child. In a tree, leaf node is also called as 'Terminal' node.

7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as INTERNAL Node. In simple
words, an internal node is a node with atleast one child.

In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node is also
said to be Internal Node if the tree has more than one node. Internal nodes are also called as 'Non-
Terminal' nodes.

8. Degree
In a tree data structure, the total number of children of a node is called as DEGREE of that Node. In
simple words, the Degree of a node is total number of children it has. The highest degree of a node
among all the nodes in a tree is called as 'Degree of Tree'
9. Level
In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level 1
and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a
tree each step from top to bottom is called as a Level and the Level count starts with '0' and
incremented by one at each level (Step).

10. Height
In a tree data structure, the total number of egdes from leaf node to a particular node in the longest path
is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of the tree. In
a tree, height of all leaf nodes is '0'.

11. Depth
In a tree data structure, the total number of egdes from root node to a particular node is called as
DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the longest
path is said to be Depth of the tree. In simple words, the highest depth of any leaf node in a tree is said
to be depth of that tree. In a tree, depth of the root node is '0'.
12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to another node is called as
PATH between that two Nodes. Length of a Path is total number of nodes in that path. In below
example the path A - B - E - J has length 4.

13. Sub Tree

In a tree data structure, each child from a node forms a subtree recursively. Every child node will form
a subtree on its parent node.

IMPLEMENTATION OF TREES

A binary tree is a recursive tree data structure where each node can have 2 children at most.

A binary tree data structure is represented using two methods. Those methods are as follows...

1. Array Representation

2. Linked List Representation

Consider the following binary tree...

 1. Array Representation of Binary Tree

In array representation of a binary tree, we use one-dimensional array (1-D Array) to represent a binary tree.

Consider the above example of a binary tree and it is represented as follows.

To represent a binary tree of depth 'n' using array representation, we need one dimensional array with a
maximum size of 2n + 1.

2. Linked List Representation of Binary Tree

We use a double linked list to represent a binary tree. In a double linked list, every node consists of three fields.
First field for storing left child address, second for storing actual data and third for storing right child address.
In this linked list representation, a node has the following structure...
Tree Representations:
A tree data structure can be represented in two methods. Those methods are as follows...
1. List Representation
2. Left Child - Right Sibling Representation
Consider the following tree...

1. List Representation
In this representation, we use two types of nodes one for representing the node with data and
another for representing only references. We start with a node with data from root node in the tree.
Then it is linked to an internal node through a reference node and is linked to any other node directly.
This process repeats for all the nodes in the tree.

The above tree example can be represented using List representation as follows...

2. Left Child - Right Sibling Representation

In this representation, we use list with one type of node which consists of three fields namely Data
field, Left child reference field and Right sibling reference field. Data field stores the actual value of a
node, left reference field stores the address of the left child and right reference field stores the address
of the right sibling node. Graphical representation of that node is as follows...

In this representation, every node's data field stores the actual value of that node. If that node has left
child, then left reference field stores the address of that left child node otherwise that field stores
NULL. If that node has right sibling then right reference field stores the address of right sibling node
otherwise that field stores NULL.
The above tree example can be represented using Left Child - Right Sibling representation as follows...

TREE TRAVERSALS
There are three types of tree traversals.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
Consider the following binary tree...

1. In - Order Traversal ( leftChild - root - rightChild )

In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left
child node is visited first, then the root node is visited and later we go for visiting right child node. This
in-order traversal is applicable for every root node of all subtrees in the tree. This is performed
recursively for all nodes in the tree.

In the above example of binary tree, first we try to visit left child of root node 'A', but A's left child is a
root node for left subtree. so we try to visit its (B's) left child 'D' and again D is a root for subtree with
nodes D, I and J. So we try to visit its left child 'I' and it is the left most child. So first we visit 'I' then
go for its root node 'D' and later we visit D's right child 'J'. With this we have completed the left part
of node B. Then visit 'B' and next B's right child 'F' is visited. With this we have completed left part of
node A. Then visit root node 'A'. With this we have completed left and root parts of node A. Then we
go for right part of the node A. In right of A again there is a subtree with root C. So go for left child of
C and again it is a subtree with root G. But G does not have left part so we visit 'G' and then visit G's
right child K. With this we have completed the left part of node C. Then visit root node 'C' and next
visit C's right child 'H' which is the right most child in the tree so we stop the process.

That means here we have visited in the order of I - D - J - B - F - A - G - K - C - H using In-Order

Traversal.
In-Order Traversal for above example of binary tree is
I-D-J-B-F-A-G-K-C-H

2. Pre - Order Traversal ( root - leftChild - rightChild )

In Pre-Order traversal, the root node is visited before left child and right child nodes. In this traversal,
the root node is visited first, then its left child and later its right child. This pre-order traversal is
applicable for every root node of all subtrees in the tree.

In the above example of binary tree, first we visit root node 'A' then visit its left child 'B' which is a
root for D and F. So we visit B's left child 'D' and again D is a root for I and J. So we visit D's left child
'I' which is the left most child. So next we go for visiting D's right child 'J'. With this we have
completed root, left and right parts of node D and root, left parts of node B. Next visit B's right child
'F'. With this we have completed root and left parts of node A. So we go for A's right child 'C' which is
a root node for G and H. After visiting C, we go for its left child 'G' which is a root for node K. So next
we visit left of G, but it does not have left child so we go for G's right child 'K'. With this we have
completed node C's root and left parts. Next visit C's right child 'H' which is the right most child in the
tree. So we stop the process.
That means here we have visited in the order of A-B-D-I-J-F-C-G-K-H using Pre-Order Traversal.
Pre-Order Traversal for above example binary tree is
A-B-D-I-J-F-C-G-K-H
3. Post - Order Traversal ( leftChild - rightChild - root )
In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left child
node is visited first, then its right child and then its root node. This is recursively performed until the
right most node is visited.

Here we have visited in the order of I - J - D - F - B - K - G - H - C - A using Post-Order Traversal.

Post-Order Traversal for above example binary tree is
I-J-D-F-B-K-G-H-C-A

BINARY TREE ADT

In a normal tree, every node can have any number of children. Binary tree is a special type of
tree data structure in which every node can have a maximum of 2 children. One is known as left child
and the other is known as right child.
A tree in which every node can have a maximum of two children is called as Binary Tree.
In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2
children.
Example

There are different types of binary trees and they are...

1. Strictly Binary Tree
In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node
should have exactly two children or none. That means every internal node must have exactly two
children. A strictly Binary Tree can be defined as follows...
A binary tree in which every node has either two or zero number of children is called Strictly Binary
[Link] binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree. Strictly
binary tree data structure is used to represent mathematical expressions.

Example
2. Complete Binary Tree
In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node
should have exactly two children or none and in complete binary tree all the nodes must have exactly
two children and at every level of complete binary tree there must be 2level number of nodes. For
example at level 2 there must be 22 = 4 nodes and at level 3 there must be 23 = 8 nodes.
A binary tree in which every internal node has exactly two children and all leaf nodes are at same level
is called Complete Binary [Link] binary tree is also called as Perfect Binary Tree

3. Extended Binary Tree

A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes
wherever required.
The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended Binary
Tree.

In above figure, a normal binary tree is converted into full binary tree by adding dummy nodes (In pink
colour).

EXPRESSION TREES
Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node
corresponds to operand so for example expression tree for 3 + ((5+9)*2) would be:

Inorder traversal of expression tree produces infix version of given postfix expression (same
with preorder traversal it gives prefix expression)
Evaluating the expression represented by expression tree:
Let t be the expression tree
If t is not null then
If [Link] is operand then
Return [Link]
A = solve([Link])
B = solve([Link])
// calculate applies operator '[Link]'
// on A and B, and returns value
Return calculate(A, B, [Link])

Construction of Expression Tree:

Now For constructing expression tree we use a stack. We loop through input expression and do
following for every character.
1) If character is operand push that into stack
2) If character is operator pop two values from stack make them its child and push current node again.
At the end only element of stack will be root of expression tree.

APPLICATIONS OF TREES
Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data
structure.
1) One reason to use trees might be because you want to store information that naturally forms a
hierarchy. For example, the file system on a computer:
File system:
/ <-- root

/ \
... home
/ \
ugrad course
/ / | \
... cs101 cs112 cs113

2) If we organize keys in form of a tree (with some ordering e.g., BST), we can search for a given key
in moderate time (quicker than Linked List and slower than arrays). Self-balancing search trees like
AVL and Red-Black trees guarantee an upper bound of O(Logn) for search.

3) We can insert/delete keys in moderate time (quicker than Arrays and slower than Unordered Linked
Lists). Self-balancing search trees like AVL and Red-Black trees guarantee an upper bound of O(Logn)
for insertion/deletion.

4) Like Linked Lists and unlike Arrays, Pointer implementation of trees don’t have an upper limit on
number of nodes as nodes are linked using pointers.
BINARY SEARCH TREE ADT
In a binary tree, every node can have maximum of two children but there is no order of nodes based on
their values. In binary tree, the elements are arranged as they arrive to the tree, from top to bottom and
left to right.
A binary tree has the following time complexities...

1. Search Operation - O(n)

2. Insertion Operation - O(1)
3. Deletion Operation - O(n)

To enhance the performance of binary tree, we use special type of binary tree known as Binary Search
Tree. Binary search tree mainly focus on the search operation in binary tree. Binary search tree can be
defined as follows...

Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree
and only larger values in its right subtree.

In a binary search tree, all the nodes in left subtree of any node contains smaller values and all the
nodes in right subtree of that contains larger values as shown in following figure...
Example
The following tree is a Binary Search Tree. In this tree, left subtree of every node contains nodes with
smaller values and right subtree of every node contains larger values.

Every Binary Search Tree is a binary tree but all the Binary Trees need not to be binary search
trees.
Operations on a Binary Search Tree
The following operations are performed on a binary earch tree...
1. Search
2. Insertion
3. Deletion

Search Operation in BST

In a binary search tree, the search operation is performed with O(log n) time complexity. The
search operation is performed as follows...

 Step 1: Read the search element from the user

 Step 2: Compare, the search element with the value of root node in the tree.
 Step 3: If both are matching, then display "Given node found!!!" and terminate the function
 Step 4: If both are not matching, then check whether search element is smaller or larger than
that node value.
 Step 5: If search element is smaller, then continue the search process in left subtree.
 Step 6: If search element is larger, then continue the search process in right subtree.
 Step 7: Repeat the same until we found exact element or we completed with a leaf node
 Step 8: If we reach to the node with search value, then display "Element is found" and
terminate the function.
 Step 9: If we reach to a leaf node and it is also not matching, then display "Element not found"
and terminate the function.

Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n) time complexity. In binary
search tree, new node is always inserted as a leaf node. The insertion operation is performed as
follows...

 Step 1: Create a newNode with given value and set its left and right to NULL.
 Step 2: Check whether tree is Empty.
 Step 3: If the tree is Empty, then set set root to newNode.
 Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or larger
than the node (here it is root node).
  Step 5: If newNode is smaller than or equal to the node, then move to its left child. If
newNode is larger than the node, then move to its right child.
 Step 6: Repeat the above step until we reach to a leaf node (e.i., reach to NULL).
 Step 7: After reaching a leaf node, then isert the newNode as left child if newNode is smaller
or equal to that leaf else insert it as right child.

Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n) time complexity. Deleting a
node from Binary search tree has follwing three cases...

 Case 1: Deleting a Leaf node (A node with no children)

 Case 2: Deleting a node with one child
 Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...

 Step 1: Find the node to be deleted using search operation

 Step 2: Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...

 Step 1: Find the node to be deleted using search operation

 Step 2: If it has only one child, then create a link between its parent and child nodes.
 Step 3: Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...

 Step 1: Find the node to be deleted using search operation

 Step 2: If it has two children, then find the largest node in its left subtree (OR) the smallest
node in its right subtree.
 Step 3: Swap both deleting node and node which found in above step.
 Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2
 Step 5: If it comes to case 1, then delete using case 1 logic.
 Step 6: If it comes to case 2, then delete using case 2 logic.
 Step 7: Repeat the same process until node is deleted from the tree.

Example
Construct a Binary Search Tree by inserting the following sequence of numbers...
10,12,5,4,20,8,7,15 and 13
Above elements are inserted into a Binary Search Tree as follows...
Linked list implementation of BST:

THREADED BINARY TREES

A binary tree is represented using array representation or linked list representation. When a
binary tree is represented using linked list representation, if any node is not having a child we use
NULL pointer in that position. In any binary tree linked list representation, there are more number of
NULL pointer than actual pointers. Generally, in any binary tree linked list representation, if there are
2N number of reference fields, then N+1 number of reference fields are filled with NULL ( N+1 are
NULL out of 2N ). This NULL pointer does not play any role except indicating there is no link (no
child).

A. J. Perlis and C. Thornton have proposed new binary tree called "Threaded Binary Tree",
which make use of NULL pointer to improve its traversal processes. In threaded binary tree, NULL
pointers are replaced by references to other nodes in the tree, called threads.

Threaded Binary Tree is also a binary tree in which all left child pointers that are NULL (in
Linked list representation) points to its in-order predecessor, and all right child pointers that are NULL
(in Linked list representation) points to its in-order successor. If there is no in-order predecessor or in-
order successor, then it point to root node.
To convert above binary tree into threaded binary tree, first find the in-order traversal of that tree...
In-order traversal of above binary tree...
H-D-I-B-E-A-F-J-C-G
When we represent above binary tree using linked list representation, nodes H, I, E, F, J and G left
child pointers are NULL. This NULL is replaced by address of its in-order predecessor, respectively (I
to D, E to B, F to A, J to F and G to C), but here the node H does not have its in-order predecessor, so it
points to the root node A. And nodes H, I, E, J and G right child pointers are NULL. This NULL
ponters are replaced by address of its in-order successor, respectively (H to D, I to B, E to A, and J to
C), but here the node G does not have its in-order successor, so it points to the root node A.

Above example binary tree become as follows after converting into threaded binary tree.

In above figure threaded are indicated with dotted links.

AVL TREES
What if the input to binary search tree comes in a sorted (ascending or descending) manner? It will then
look like this −

It is observed that BST's worst-case performance is closest to linear search algorithms, that is Ο(n). In
real-time data, we cannot predict data pattern and their frequencies. So, a need arises to balance out the
existing BST.
Named after their inventor Adelson, Velski & Landis, AVL trees are height balancing binary search
tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not
more than 1. This difference is called the Balance Factor.

Here we see that the first tree is balanced and the next two trees are not balanced −

In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so the difference
is 2. In the third tree, the right subtree of A has height 2 and the left is missing, so it is 0, and the
difference is 2 again. AVL tree permits difference (balance factor) to be only 1.
BalanceFactor = height(left-sutree) − height(right-sutree)
If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using some
rotation techniques.
AVL Rotations
To balance itself, an AVL tree may perform the following four kinds of rotations −
 Left rotation
 Right rotation
 Left-Right rotation
 Right-Left rotation

The first two rotations are single rotations and the next two rotations are double rotations. To have an
unbalanced tree, we at least need a tree of height 2. With this simple tree, let's understand them one by
one.
Left Rotation

If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we
perform a single left rotation −

In our example, node A has become unbalanced as a node is inserted in the right subtree of A's right
subtree. We perform the left rotation by making A the left-subtree of B.
Right Rotation
AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree
then needs a right rotation.

As depicted, the unbalanced node becomes the right child of its left child by performing a right
rotation.

Left-Right Rotation

Double rotations are slightly complex version of already explained versions of rotations. To understand
them better, we should take note of each action performed while rotation.

Let's first check how to perform Left-Right rotation. A left-right rotation is a combination of left
rotation followed by right rotation.
 State Action

A node has been inserted into the right subtree of the left subtree.
This makes C an unbalanced node. These scenarios cause AVL tree
to perform left-right rotation.

We first perform the left rotation on the left subtree of C. This makes
A, the left subtree of B.

Node C is still unbalanced, however now, it is because of the left-

subtree of the left-subtree.

We shall now right-rotate the tree, making B the new root node of
this subtree. C now becomes the right subtree of its own left subtree.

The tree is now balanced.

Right-Left Rotation

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed
by left rotation.
 State Action

A node has been inserted into the left subtree of the right subtree. This
makes A, an unbalanced node with balance factor 2.

First, we perform the right rotation along C node, making C the right
subtree of its own left subtree B. Now, B becomes the right subtree of A.

Node A is still unbalanced because of the right subtree of its right

subtree and requires a left rotation.

A left rotation is performed by making B the new root node of the

subtree. A becomes the left subtree of its right subtree B.

The tree is now balanced.

Operations on an AVL Tree:

The following operations are performed on an AVL tree...

1. Search
2. Insertion
3. Deletion
Search Operation in AVL Tree

In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation
is performed similar to Binary search tree search operation. We use the following steps to search an
element in AVL tree...
 Step 1: Read the search element from the user
 Step 2: Compare, the search element with the value of root node in the tree.
 Step 3: If both are matching, then display "Given node found!!!" and terminate the function
 Step 4: If both are not matching, then check whether search element is smaller or larger than
that node value.
 Step 5: If search element is smaller, then continue the search process in left subtree.
 Step 6: If search element is larger, then continue the search process in right subtree.
 Step 7: Repeat the same until we found exact element or we completed with a leaf node
 Step 8: If we reach to the node with search value, then display "Element is found" and
terminate the function.
 Step 9: If we reach to a leaf node and it is also not matching, then display "Element not found"
and terminate the function.

Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, new
node is always inserted as a leaf node. The insertion operation is performed as follows...

 Step 1: Insert the new element into the tree using Binary Search Tree insertion logic.
 Step 2: After insertion, check the Balance Factor of every node.
 Step 3: If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.
 Step 4: If the Balance Factor of any node is other than 0 or 1 or -1 then tree is said to be
imbalanced. Then perform the suitable Rotation to make it balanced. And go for next
operation.
Example: Construct an AVL Tree by inserting numbers from 1 to 8.
MULTI-WAY SEARCH TREES
• every internal node of an M-way search tree consists of pointers to M sub-trees and contains M
– 1 keys, where M > 2.
• M = 3. So a node can store a maximum of two key values and can contain pointers to three sub-
trees.

• In a binary search tree, AVL Tree, Red-Black tree etc., every node can have only one value
(key) and maximum of two children but there is another type of search tree called B-Tree in
which a node can store more than one value (key) and it can have more than two children.

B-Tree was developed in the year of 1972 by Bayer and McCreight with the name Height Balanced m-
way Search Tree. Later it was named as B-Tree

B-TREE :
In a binary search tree, AVL Tree, Red-Black tree etc., every node can have only one value
(key) and maximum of two children but there is another type of search tree called B-Tree in which a
node can store more than one value (key) and it can have more than two children. B-Tree was
developed in the year of 1972 by Bayer and McCreight with the name Height Balanced m-way
Search Tree. Later it was named as B-Tree.

B-Tree can be defined as follows...

B-Tree is a self-balanced search tree with multiple keys in every node and more than two
children for every node.

Here, number of keys in a node and number of children for a node is depend on the order of the B-
Tree. Every B-Tree has order.
B-Tree of Order m has the following properties...

 Property #1 - All the leaf nodes must be at same level.

 Property #2 - All nodes except root must have at least [m/2]-1 keys and maximum of m-1
keys.
 Property #3 - All non leaf nodes except root (i.e. all internal nodes) must have at least m/2
children.
 Property #4 - If the root node is a non leaf node, then it must have at least 2 children.
 Property #5 - A non leaf node with n-1 keys must have n number of children.
 Property #6 - All the key values within a node must be in Ascending Order.

For example, B-Tree of Order 4 contains maximum 3 key values in a node and maximum 4 children for
a node.

Example

Operations on a B-Tree
The following operations are performed on a B-Tree...
1. Search
2. Insertion
3. Deletion

Search Operation in B-Tree

In a B-Ttree, the search operation is similar to that of Binary Search Tree. In a Binary search tree, the
search process starts from the root node and every time we make a 2-way decision (we go to either left
subtree or right subtree). In B-Tree also search process starts from the root node but every time we
make n-way decision where n is the total number of children that node has. In a B-Ttree, the search
operation is performed with O(log n) time complexity. The search operation is performed as follows...

 Step 1: Read the search element from the user

 Step 2: Compare, the search element with first key value of root node in the tree.
 Step 3: If both are matching, then display "Given node found!!!" and terminate the function
 Step 4: If both are not matching, then check whether search element is smaller or larger than
that key value.
 Step 5: If search element is smaller, then continue the search process in left subtree.
 Step 6: If search element is larger, then compare with next key value in the same node and
repeate step 3, 4, 5 and 6 until we found exact match or comparision completed with last key
value in a leaf node.
  Step 7: If we completed with last key value in a leaf node, then display "Element is not found"
and terminate the function.

Insertion Operation in B-Tree

In a B-Tree, the new element must be added only at leaf node. That means, always the new keyValue is
attached to leaf node only. The insertion operation is performed as follows...

 Step 1: Check whether tree is Empty.

 Step 2: If tree is Empty, then create a new node with new key value and insert into the tree as a
root node.
 Step 3: If tree is Not Empty, then find a leaf node to which the new key value cab be added
using Binary Search Tree logic.
 Step 4: If that leaf node has an empty position, then add the new key value to that leaf node by
maintaining ascending order of key value within the node.
 Step 5: If that leaf node is already full, then split that leaf node by sending middle value to its
parent node. Repeat tha same until sending value is fixed into a node.
 Step 6: If the spilting is occuring to the root node, then the middle value becomes new root
node for the tree and the height of the tree is increased by one.

Example
Construct a B-Tree of Order 3 by inserting numbers from 1 to 10.
Deletion in B-Tree
For deletion in b tree we wish to remove from a leaf. There are three possible case for deletion in b tree.
Let k be the key to be deleted, x the node containing the key. Then the cases are:

Case-I
If the key is already in a leaf node, and removing it doesn’t cause that leaf node to have too few keys, then
simply remove the key to be deleted. key k is in node x and x is a leaf, simply delete k from x.

6 deleted
Case-II
If key k is in node x and x is an internal node, there are three cases to consider:
Case-II-a
If the child y that precedes k in node x has at least t keys (more than the minimum), then find the predecessor
key k' in the subtree rooted at y. Recursively delete k' and replace k with k' in x
Case-II-b
Symmetrically, if the child z that follows k in node x has at least t keys, find the successor k' and delete and
replace as before. Note that finding k' and deleting it can be performed in a single downward pass.

13 deleted

Case-II-c
Otherwise, if both y and z have only t−1 (minimum number) keys, merge k and all of z into y, so that both k and
the pointer to z are removed from x. y now contains 2t − 1 keys, and subsequently k is deleted.
7 deleted

Case-III
If key k is not present in an internal node x, determine the root of the appropriate subtree that must contain k.
If the root has only t − 1 keys, execute either of the following two cases to ensure that we descend to a node
containing at least t keys. Finally, recurse to the appropriate child of x.

Case-III-a
If the root has only t−1 keys but has a sibling with t keys, give the root an extra key by moving a key from x to
the root, moving a key from the roots immediate left or right sibling up into x, and moving the appropriate child
from the sibling to x.
2 deleted

Case-III-b

If the root and all of its siblings have t−1 keys, merge the root with one sibling. This involves moving a key down
from x into the new merged node to become the median key for that node.

4 deleted
B+ TREE:
A B+ tree is an N-ary tree with a variable but often large number of children per node. A B+ tree
consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more
children.

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and
to which an additional level is added at the bottom with linked leaves.

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage
context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have
very high fanout (number of pointers to child nodes in a node, typically on the order of 100 or more),
which reduces the number of I/O operations required to find an element in the tree.

A simple B+ tree example linking the keys 1–7 to data values d1-d7. The linked list (red) allows rapid

in-order traversal. This particular tree's branching factor is =4.

A B+-tree maintains the following invariants:

 Every node has one more references than it has keys.

 All leaves are at the same distance from the root.
 For every non-leaf node N with k being the number of keys in N: all keys in the first child's
subtree are less than N's first key; and all keys in the ith child's subtree (2 ≤ i ≤ k) are between
the (i − 1)th key of n and the ith key of n.
 The root has at least two children.
 Every non-leaf, non-root node has at least floor(d / 2) children.
 Each leaf contains at least floor(d / 2) keys.
 Every key from the table appears in a leaf, in left-to-right sorted order.

Insertion algorithm

Descend to the leaf where the key fits.

1. If the node has an empty space, insert the key/reference pair into the node.
2. If the node is already full, split it into two nodes, distributing the keys evenly between the two
nodes. If the node is a leaf, take a copy of the minimum value in the second of these two nodes
and repeat this insertion algorithm to insert it into the parent node. If the node is a non-leaf,
exclude the middle value during the split and repeat this insertion algorithm to insert this
excluded value into the parent node.
Initial:

Insert 20:

Insert 13:

Insert 15:

Insert 10:

Insert 11:

Insert 12:
Deletion algorithm

Descend to the leaf where the key exists.

1. Remove the required key and associated reference from the node.
2. If the node still has enough keys and references to satisfy the invariants, stop.
3. If the node has too few keys to satisfy the invariants, but its next oldest or next youngest sibling
at the same level has more than necessary, distribute the keys between this node and the
neighbor. Repair the keys in the level above to represent that these nodes now have a different
―split point‖ between them; this involves simply changing a key in the levels above, without
deletion or insertion.
4. If the node has too few keys to satisfy the invariant, and the next oldest or next youngest sibling
is at the minimum for the invariant, then merge the node with its sibling; if the node is a non-
leaf, we will need to incorporate the ―split key‖ from the parent into our merging. In either case,
we will need to repeat the removal algorithm on the parent node to remove the ―split key‖ that
previously separated these merged nodes — unless the parent is the root and we are removing
the final key from the root, in which case the merged node becomes the new root (and the tree
has become one level shorter than before).

Initial:

Delete 13:

Delete 15:
Delete 1:

HEAP
Heap is a special case of balanced binary tree data structure where the root-node key is compared with
its children and arranged accordingly. If α has child node β then −

key(α) ≥ key(β)

As the value of parent is greater than that of child, this property generates Max Heap. Based on this
criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Max Heap Construction Algorithm

We shall use the same example to demonstrate how a Max Heap is created. The procedure to create
Min Heap is similar but we go for min values instead of max values.
We are going to derive an algorithm for max heap by inserting one element at a time. At any point of
time, heap must maintain its property. While insertion, we also assume that we are inserting a node in
an already heapified tree.

Step 1 − Create a new node at the end of heap.

Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that
of the child node.

Max Heap Deletion Algorithm

Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at
the root to remove the Maximum (or minimum) value.

Step 1 − Remove root node.

Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

APPLICATIONS OF HEAP
The heap data structure has many applications.
 Heapsort: One of the best sorting methods being in-place and with no quadratic worst-case
scenarios.
Example:
In the diagram below,initially there is an unsorted array having 6 elements. We begin by building max-
heap.

After building max-heap, the elements in the array Arr will be:
Processing:

Step 1: 8 is swapped with 5.

Step 2: 8 is disconnected from heap as 8 is in correct position now.
Step 3: Max-heap is created and 7 is swapped with 3.
Step 4: 7 is disconnected from heap.
Step 5: Max heap is created and 5 is swapped with 1.
Step 6: 5 is disconnected from heap.
Step 7: Max heap is created and 4 is swapped with 3.
Step 8: 4 is disconnected from heap.
Step 9: Max heap is created and 3 is swapped with 1.
Step 10: 3 is disconnected.
  Selection algorithms: A heap allows access to the min or max element in constant time, and
other selections (such as median or kth-element) can be done in sub-linear time on data that is in
a heap.
DELETE MIN
DELETEMAX

 Graph algorithms: By using heaps as internal traversal data structures, run time will be
reduced by polynomial order. Examples of such problems are Prim's minimal-spanning-tree
algorithm and Dijkstra's shortest-path algorithm.

 Priority Queue: A priority queue is an abstract concept like "a list" or "a map"; just as a list can
be implemented with a linked list or an array, a priority queue can be implemented with a heap
or a variety of other methods.

Priority Queue is similar to queue where we insert an element from the back and remove an element
from front, but with a difference that the logical order of elements in the priority queue depends on the
priority of the elements. The element with highest priority will be moved to the front of the queue and
one with lowest priority will move to the back of the queue. Thus it is possible that when you enqueue
an element at the back in the queue, it can move to front because of its highest priority.

Example:
Let’s say we have an array of 5 elements : {4, 8, 1, 7, 3} and we have to insert all the elements in the
max-priority queue.

First as the priority queue is empty, so 4 will be inserted initially.

Now when 8 will be inserted it will moved to front as 8 is greater than 4.
While inserting 1, as it is the current minimum element in the priority queue, it will remain in the back
of priority queue.
Now 7 will be inserted between 8 and 4 as 7 is smaller than 8.

Now 3 will be inserted before 1 as it is the 2nd minimum element in the priority queue. All the steps are
represented in the diagram below:
We can think of many ways to implement the priority queue.

 K-way merge: A heap data structure is useful to merge many already-sorted input streams into
a single sorted output stream. Examples of the need for merging include external sorting and
streaming results from distributed data such as a log structured merge tree. The inner loop is
obtaining the min element, replacing with the next element for the corresponding input stream,
then doing a sift-down heap operation. (Alternatively the replace function.) (Using extract-max
and insert functions of a priority queue are much less efficient.)

 Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or
largest) element in an array.

PRIORITY QUEUE:-

In normal queue data structure, insertion is performed at the end of the queue and deletion is
performed based on the FIFO principle. This queue implementation may not be suitable for all
situations.

 In normal queue data structure, insertion is performed at the end of the queue and deletion is
performed based on the FIFO principle. This queue implementation may not be suitable for all
situations.
 A Priority Queue – a different kind of queue.
 Similar to a regular queue:
o insert in rear,
o remove from front.
 Items in priority queue are ordered by some key
 Item with the lowest key / highest key is always at the front from where they are removed.
  Each element has a "priority" associated with it.
 In a priority queue, an element with high priority is served before an element with low priority.
 If two elements have the same priority, they are served according to their order in the queue.

The general rules of processing the elements of a priority queue are

– An element with higher priority is processed before an element with a lower priority.
– Two elements with the same priority are processed on a first-come-first-served (FCFS)
basis.
• A priority queue can be implemented with a linked list or an array, a priority queue can be
implemented with a heap or a variety of other methods such as an unordered array.
Operations:
A priority queue must at least support the following operations:
• is_empty: check whether the queue has no elements.
• insert_with_priority: add an element to the queue with an associated priority.
• pull_highest_priority_element: remove the element from the queue that has the highest priority,
and return it.
Consider a networking application where server has to respond for requests from multiple
clients using queue data structure. Assume four requests arrived to the queue in the order of R1 requires
20 units of time, R2 requires 2 units of time, R3 requires 10 units of time and R4 requires 5 units of
time. Queue is as follows...

Now, check waiting time for each request to be complete.

1. R1 : 20 units of time
2. R2 : 22 units of time (R2 must wait till R1 complete - 20 units and R2 itself requeres 2
units. Total 22 units)
3. R3 : 32 units of time (R3 must wait till R2 complete - 22 units and R3 itself requeres 10
units. Total 32 units)
4. R4 : 37 units of time (R4 must wait till R3 complete - 35 units and R4 itself requeres 5
units. Total 37 units)
Here, average waiting time for all requests (R1, R2, R3 and R4) is (20+22+32+37)/4 ≈ 27 units of
time.
Operat Routine Example with Representation
ion
Creatio struct node
n {
int priority;
int data;
struct node *next;
}*front = NULL;
Enqueue void insert(int element, int priority)

struct node *newnode,*temp;

newnode = (struct node *)malloc(sizeof(struct node));

newnode->data = element;

newnode->priority = priority;

if( front == NULL || priority < front->priority )

newnode->next = front;

front = newnode;

else

temp = front;

while( temp->next != NULL && temp->next->priority <=

priority )

temp=temp->next;

newnode->next = temp->next;

temp->next = newnode;

Dequeu void del()

e {
struct node *temp;
 if(front == NULL)
{
printf("\n\nQueue Underflow\n");
}
else
{
temp = front;
printf("\n\nDeleted data is %d\n",temp->data);
front = temp->next;
free(temp);
}
}

Display void display()

{
struct node *temp;
temp = front;
if(front == NULL)
{
printf("\n\nQueue is empty\n");
}
else
{
printf("Priority\tData\n\n");
while(temp!= NULL)
{
printf("%d \t\t%d\n\n",temp->priority,temp->data);
temp=temp->next;
}
}
}
**********************************************************