MUTHAYAMMAL COLLEGE OF ARTS AND SCIENCE (Autonomous), RASIPURAM.

DEPARTMENT OF COMPUTER APPLICATIONS

Staff Name : [Link] [Link]., [Link]., Class : II BCA A Paper Code : 21M3UCAC06
Paper Name : Data Structures & Algorithms Unit : III

Unit III:Tree ADT – Tree Traversals – Binary Tree ADT – expression trees – application of Trees – Binary
Search Tree ADT – Threaded Binary Trees – AVL Trees – BTree – B+Tree – Heap – Applications of Heap.

[Link] ADT

Definition: Tree is a non-linear data structure which organizes data in a hierarchical structure.
A tree is a finite set of one or more nodes such that: (i) there is a specially designated node called
the root. (ii) the remaining nodes are partitioned into n >= 0 disjoint sets T1, T2, …, Tn where each of
these sets is a tree. T1, …, Tn are called the subtrees of the root.

o A tree data structure is defined as a collection of objects or entities known as nodes that are linked
together to represent or simulate hierarchy.
o A tree data structure is a non-linear data structure because it does not store in a sequential manner. It
is a hierarchical structure as elements in a Tree are arranged in multiple levels.
o In the Tree data structure, the topmost node is known as a root node. Each node contains some data,
and data can be of any type. In the above tree structure, the node contains the name of the employee,
so the type of data would be a string.
o Each node contains some data and the link or reference of other nodes that can be called children.

Basic Terminologies

Root: The first node from where the tree originates is called as a root node. In any tree, there must be
only one root node.

Edge: The connecting link between any two nodes is called as an edge. In a tree with n number of
nodes, there are exactly (n-1) number of edges.

Parent: The node which has a branch from it to any other node is called as a parent node. In other words,
the node which has one or more children is called as a parent node.
1
Child: The node which is a descendant of some node is called as a child node. All the nodes except
root node are child nodes.

Siblings: Nodes which belong to the same parent are called as siblings. In other words, nodes with the
same parent are sibling nodes.

Degree: Degree of a node is the total number of children of that node. Degree of a tree is the highest
degree of a node among all the nodes in the tree.
Internal Node: The node which has at least one child is called as an internal node. Internal nodes are
also called as non-terminal nodes. Every non-leaf node is an internal node.

Leaf Node: The node which does not have any child is called as a leaf node. Leaf nodes are also
called as external nodes or terminal nodes.
Level: In a tree, each step from top to bottom is called as level of a tree. The level count starts with 0
and increments by 1 at each level or step.

Height: Total number of edges that lies on the longest path from any leaf node to a particular node is
called as height of that node. Height of a tree is the height of root node. Height of all leaf nodes = 0

Depth: Total number of edges from root node to a particular node is called as depth of that node. Depth of
a tree is the total number of edges from root node to a leaf node in the longest path. Depth of the root node
= 0. The terms “level” and “depth” are used interchangeably.

Subtree: In a tree, each child from a node forms a subtree recursively. Every child node forms a subtree
on its parent node.

Forest: A forest is a set of disjoint trees.

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.
Descendant: The immediate successor of the given node is known as a descendant of a node.

Parent: Here, Node A is the parent of nodes B and C. Node B is the parent of nodes D, E and F. Node C
is the parent of nodes G and H. Node E is the parent of nodes I and J. Node G is the parent of node K.
Child: Here, Nodes B and C are the children of node A. Nodes D, E and F are the children of node B.
Nodes G and H are the children of node C. Nodes I and J are the children of node E. Node K is the child of
node G.

2
 Siblings: Here, Nodes B and C are siblings. Nodes D, E and F are siblings. Nodes G and H are
siblings. Nodes I and J are siblings.
Degree: Here, Degree of node A = 2. Degree of node B = 3. Degree of node C = 2. Degree of node D =
0. Degree of node E = 2. Degree of node F = 0. Degree of node G = 1. Degree of node H = 0. Degree of
node I= 0. Degree of node J = 0. Degree of node K = 0.
Internal Node: Here, nodes A, B, C, E and G are internal nodes.

Leaf Node: Here, nodes D, I, J, F, K and H are leaf nodes.

Height: Here, Height of node A = 3. Height of node B = 2. Height of node C = 2. Height of node D =
0. Height of node E = 1. Height of node F = 0. Height of node G = 1. Height of node H = 0. Height of
node I =Height of node J = 0. Height of node K = 0.

Depth: Here, Depth of node A = 0. Depth of node B = 1. Depth of node C = 1. Depth of node D = 2.
Depth of node E = 2. Depth of node F = 2. Depth of node G = 2. Depth of node H = 2. Depth of node I
= 3. Depth of node J = 3. Depth of node K = 3.

Ancestor node: Ancestor node for H is D,B,A. J = E, B, A . G = C & A

Descendant: J is the descendant of Node E. H is the descendant of Node D(immediate successor).

[Link] 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...

3
1. List Representation
 In this representation, we use two types of nodes one for representing the node with data called 'data
node' and another for representing only references called 'reference node'.
 We start with a 'data node' from the root node in the tree. Then it is linked to an internal node through
a 'reference node' which is further linked to any other node directly.
 This process repeats for all the nodes in the tree.
The above example tree can be represented using List representation as follows...

2. Left Child - Right Sibling Representation

 In this representation, we use a 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.

4
  If that node has left a child, then left reference field stores the address of that left child node
otherwise stores NULL.
 If that node has the right sibling, then right reference field stores the address of right sibling node
otherwise stores NULL.
The above example tree can be represented using Left Child - Right Sibling representation as
follows...

1.1,[Link] of Trees
 Any connected graph with n vertices and (n-1) edges is a tree.
 The important properties of tree data structure are-
There is one and only one path between every pair of vertices in a tree.
A tree with n vertices has exactly (n-1) edges.
A graph is a tree if and only if it is minimally connected.

 Recursive data structure

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

5
Binary Tree Traversal
 Tree Traversal refers to the process of visiting each node in a tree data structure exactly one.

Various Tree Traversal Techniques

Depth First Traversal: Following Tree Traversal techniques fall under depth first traversal-

1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal

1. Preorder Traversal (Root → Left → Right)

Steps
1. Visit the root
2. Traverse the left sub tree i.e. call Preorder (left sub tree)
3. Traverse the right sub tree i.e. call Preorder (right sub
tree)
Algorithm PREORDER (ROOT)

1. ptr=ROOT
2. If (ptr ≠NULL) then
1. VISIT(ptr)
2. PREORDER(ptr LC)
3. PREORDER(ptr RC)
3. Endif
4. Stop
Applications: used to get prefix expression of an expression tree. used to create a copy of the tree

[Link] Traversal (Left → Root → Right)

Steps
1. Traverse the left sub tree i.e. call Inorder (left sub tree)
2. Visit the root
6
 3. Traverse the right sub tree i.e. call Inorder (right sub tree)

Algorithm INORDER (ROOT)

1. ptr=ROOT
2. If (ptr ≠NULL) then
[Link] (ptr LC)
[Link] (ptr)
3. INORDER (ptr RC)
3. Endif
4. Stop
Applications: used to get infix expression of an expression tree

[Link] Traversal (Left → Right → Root)

Steps
1. Traverse the left sub tree i.e. call Postorder (left sub tree)
2. Traverse the right sub tree i.e. call Postorder (right sub tree)
3. Visit the root

Algorithm PREORDER (ROOT)

1. ptr=ROOT

2. If (ptr ≠NULL) then

1. PREORDER(ptr LC)
2. PREORDER(ptr RC)
3. VISIT(ptr)
3. Endif
4. Stop

[Link] Tree A D T
A binary tree T is a finite set of nodes, such that
 T is empty (called empty binary tree), or
 T contains a specially designated node called the root of T, and the remaining nodes of T
form two disjoint binary trees T, and T 2 which are called left sub-tree and the right sub-tree
respectively.
7
  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.9MJava Try Catch
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.

Let's look at the simple example of the Full Binary tree.

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

Properties of Full Binary Tree

o The number of leaf nodes is equal to the number of internal nodes plus 1. In the above example, the
number of internal nodes is 5; therefore, the number of leaf nodes is equal to 6.
o The maximum number of nodes is the same as the number of nodes in the binary tree, i.e., 2h+1 -1.
o The minimum number of nodes in the full binary tree is 2*h-1.
o The minimum height of the full binary tree is log2(n+1) - 1.
o The maximum height of the full binary tree can be computed as:
n= 2*h - 1
n+1 = 2*h
h = n+1/2
[Link] 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. Let's create a complete binary tree.

 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.

Properties of Complete Binary Tree

o The maximum number of nodes in complete binary tree is 2h+1 - 1.

o The minimum number of nodes in complete binary tree is 2h.
o The minimum height of a complete binary tree is log2(n+1) - 1.

9
 o The maximum height of a complete binary tree is log(n).

[Link] 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.

[Link] 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.

10
  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.

5. 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.

Benefits of a Binary Tree

 The search operation in a binary tree is faster as compared to other trees

 Only two traversals are enough to provide the elements in sorted order
 It is easy to pick up the maximum and minimum elements
 Graph traversal also uses binary trees
 Converting different postfix and prefix expressions are possible using binary trees
11
[Link] Tree Representations
 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...

The above example of the binary tree represented using Linked list representation is shown

12
[Link] of Binary Tree
o At each level of i, the maximum number of nodes is 2i.
o The height of the tree is defined as the longest path from the root node to the leaf node. The tree
which is shown above has a height equal to 3. Therefore, the maximum number of nodes at height 3
is equal to (1+2+4+8) = 15. In general, the maximum number of nodes possible at height h is (2 0 +
21 + 22+….2h) = 2h+1 -1.
o The minimum number of nodes possible at height h is equal to h+1.
o If the number of nodes is minimum, then the height of the tree would be maximum. Conversely, if
the number of nodes is maximum, then the height of the tree would be minimum.

If there are 'n' number of nodes in the binary tree.

The minimum height can be computed as:

As we know that,
n = 2h+1 -1
n+1 = 2h+1
Taking log on both the sides,
log2(n+1) = log2(2h+1)
log2(n+1) = h+1
h = log2(n+1) - 1

The maximum height can be computed as:

As we know that,
n = h+1
h= n-1

APPLICATIONS OF BINARY TREE

 Binary Tree is used as the basic data structure in Microsoft Excel and spreadsheets in usual.
 Binary Tree is used to implement indexing of Segmented Database.
 Splay Tree (Binary Tree variant) is used in implemented efficient cache is hardware and software
systems.
 Binary Space Partition Trees are used in Computer Graphics, Back face Culling, Collision
13
 detection, Ray Tracing and algorithms in rendering game graphics.
 Syntax Tree (Binary Tree with nodes as operations) are used to compute arithmetic expressions
in compilers like GCC, AOCL and others.
 Binary Heap (Binary Tree variant of Heap) is used to implement Priority Queue efficiently which
in turn is used in Heap Sort Algorithm.
 Binary Search Tree is used to search elements efficiently and used as a collision handling
technique in Hash Map implementations.
 Balanced Binary Search Tree is used to represent memory to enable fast memory allocation.
 Huffman Tree (Binary Tree variant) is used internally in a Greedy Algorithm for Data
Compression known as Huffman Encoding and Decoding.
 Merkle Tree/ Hash Tree (Binary Tree variant) is used in Blockchain implementations and p2p
programs requiring signatures.
 Binary Tries (Tries with 2 child) is used to represent a routing data which vacillate efficient
traversal.
 Morse code is used to encode data and uses a Binary Tree in its representation.
 Goldreich, Goldwasser and Micali (GGM) Tree (Binary Tree variant) is used compute
pseudorandom functions using an arbitrary pseudorandom generator.
 Scapegoat tree (a self-balancing Binary Search Tree) is used in implementing Paul-Carole games
to model a faulty search process.
 Treap (radomized Binary Search Tree)

1.4. EXPRESSION TREES

o A data structure called an expression tree is used to describe expressions that take the shape of trees.
After creating an expression’s expression tree, we may execute inorder traversal to produce an infix
expression. Postfix expressions can also be produced by traversing the expression tree in postorder.
In this blog, we’ll talk about expression trees in data structures and how stacks may be used to create
an expression tree from a given expression.

What is an Expression Tree in Data Structure?

o A mathematical expression can be expressed as a binary tree using expression trees. Expression trees
are binary trees with each leaf node serving as an operand and each internal (non-leaf) node serving
as an operator.

Properties of Expression Tree in Data Structure

o The operands are always represented by the leaf nodes. These operands are always used in the
operations.
o The operator at the root of the tree is always given top priority.
o When compared to the operators at the bottom of the tree, the operator at the bottom is always given
the lowest priority.
o Because the operand is always present at a depth of the tree, it is given the highest priority of all
operators.

14
 o The expression tree can be traversed to evaluate prefix expressions, postfix expressions, and infix
expressions.
o In summary, the value present at the depth of the tree has the highest priority when compared to the
other operators located at the top of the tree. The expression tree is immutable, and once built, we
cannot change or modify it further, so to make any changes, we must completely construct the new
expression tree.
o The given expression can be evaluated using the expression tree in data structure.
o a + (b * c) + d * (e + f)

Uses of an Expression Tree in Data Structure

o The following is the primary application of these expression trees in data structure:
o It evaluates, analyses, and modifies diverse phrases. It can also be used to determine the associativity
of each operator in an expression.
As an example:
The + operator is left-associative, while the / operator is right-associative. The expression trees
helped to solve the conundrum of this associativity.
o A context-free grammar is used to create these expression trees.
o It is a key component in compiler design and is part of the semantic analysis step.
o The expression trees are mostly used to create complex expressions that can be quickly evaluated.

Construction of an Expression Tree in Data Structure

o A stack is used to build an expression tree. For each character, we cycle through the input
expressions and do the following.
o If a character is an operand, add it to the stack.
o If a character is an operator, pop both values from the stack and make both its children and push the
current node again.
o Finally, the stack’s lone element will be the root of an expression tree.

15
o Let us understand this above process using a postfix expression. The implementation of the
expression tree is described for the below expression.
o ab+c*
o Step1 : The first two symbols are operands, for which we generate a one-node tree and push a
reference to the stack.

o Step2 : Next, read a’+’ symbol to pop two pointers to the tree, form a new tree, and push a pointer to
it onto the stack.

o Step3 : In the next stage ‘c’ is read, we build a single node tree and store a pointer to it on the stack

o Step4 : Finally, we read the last symbol’ ‘, pop two tree pointers, and build a new tree with a,’‘as
root, and a pointer to the final tree remains on the stack.

16
 o Algorithm of an Expression Tree in Data Structure

Let ET be the expression tree

If ET is not null then

If [Link] is operand then
return [Link]
A = solve([Link])
B = solve([Link])
return calculate(A, B, [Link])
// calculate() function applies operator '[Link]' on A and B, and returns

1.5. APPLICATIONS OF TREES

 File Systems: The file system of a computer is often represented as a tree. Each folder or directory is a
node in the tree, and files are the leaves.
 XML Parsing: Trees are used to parse and process XML documents. An XML document can be thought
of as a tree, with elements as nodes and attributes as properties of the nodes.
 Database Indexing: Many databases use trees to index their data. The B-tree and its variations are
commonly used for this purpose.
 Compiler Design: The syntax of programming languages is often defined using a tree structure called a
parse tree. This is used by compilers to understand the structure of the code and generate machine code
from it.
 Artificial Intelligence: Decision trees are often used in artificial intelligence to make decisions based on
a series of criteria.

Real-Time Applications of Trees

 Databases use tree data structure for indexing.
 Tree data structure is used in file directory management.
 DNS uses tree data structure.
 Trees are used in several games like moves in chess.
 Decision-based algorithms in machine learning uses tree algorithms.

17
1.6. BINARY SEARCH TREE

 Binary Search Tree is a data structure used in computer science for organizing and storing data in a
sorted manner. Binary search tree follows all properties of binary tree and its left child contains
values less than the parent node and the right child contains values greater than the parent node.
This hierarchical structure allows for efficient Searching, Insertion, and Deletion operations on the data
stored in the tree.

What is Binary Search Tree?

Binary Search Tree (BST) is a special type of binary tree in which the left child of a node has a
value less than the node’s value and the right child has a value greater than the node’s value. This property is
called the BST property and it makes it possible to efficiently search, insert, and delete elements in the tree.

Properties of Binary Search Tree

 The left subtree of a node contains only nodes with keys lesser than the node’s key.
 The right subtree of a node contains only nodes with keys greater than the node’s key.
 The left and right subtree each must also be a binary search tree.
 There must be no duplicate nodes(BST may have duplicate values with different handling approaches).

Basic Operations on Binary Search Tree:

1. Searching a node in BST:
 Searching in BST means to locate a specific node in the data structure. In Binary search tree, searching a
node is easy because of its a specific order. The steps of searching a node in Binary Search tree are listed
as follows –
 First, compare the element to be searched with the root element of the tree.
 If root is matched with the target element, then return the node’s location.
 If it is not matched, then check whether the item is less than the root element, if it is smaller
than the root element, then move to the left subtree.
 If it is larger than the root element, then move to the right subtree.
 Repeat the above procedure recursively until the match is found.
 If the element is not found or not present in the tree, then return NULL.
 Now, let’s understand the searching in binary tree using an example:
 Below is given a BST and we have to search for element 6.

18
19
2. Insert a node into a BST:
 A new key is always inserted at the leaf. Start searching a key from the root till a leaf node. Once a
leaf node is found, the new node is added as a child of the leaf node.

20
3. Delete a Node of BST:
 It is used to delete a node with specific key from the BST and return the new BST.

Different scenarios for deleting the node

Node to be deleted is the leaf node :

21
Node to be deleted has one child :
We can just replace the node with the child node.

Node to be deleted has two children:

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.

Take Care of following things while deleting a node of a BST:

1. Need to figure out what will be the replacement of the node to be deleted.
2. Want minimal disruption to the existing tree structure
3. Can take the replacement node from the deleted nodes left or right subtree.
4. If taking if from the left subtree, we have to take the largest value in the left subtree.
5. If taking if from the right subtree, we have to take the smallest value in the right subtree.

Applications of BST

 Self-balancing binary search tree: Self-balancing data structures such as AVL tree and Red-black tree
are the most useful variations of BSTs. In these variations, we maintain the height as O(Log n) so that all
operations are bounded by O(Log n). TreeSet and TreeMap in Java (or set and map in C++) are library
implementations of self-balancing BSTs.
 Sorted Stream of Data: If we wish to maintain a sorted stream of data where we wish to have
operations like insert, search, delete and traversal in sorted order, BST is the most suitable data structure
for this case.

22
 Doubly Ended Priority Queues: With Self Balancing BSTs, we can extract both maximum and
minimum in O (Log n) time, so when we need a data structure with both operations supported
efficiently, we use self-balancing BSTs.

Advantages
 Fast search: Searching for a specific value in a BST has an average time complexity of O(log n), where
n is the number of nodes in the tree. This is much faster than searching for an element in an array or
linked list, which have a time complexity of O(n) in the worst case.
 In-order traversal: BSTs can be traversed in-order, which visits the left subtree, the root, and the right
subtree. This can be used to sort a dataset.

Disadvantages
 Skewed trees: If a tree becomes skewed, the time complexity of search, insertion, and deletion
operations will be O(n) instead of O(log n), which can make the tree inefficient.
 Additional time required: Self-balancing trees require additional time to maintain balance during
insertion and deletion operations.
 Efficiency: For only search, insert and / or delete operations only hashing is always preferred over BSts.
However if we need to maintain sorted data along with these operations, we use BST.

1.7. THREADED BINARY TREES

 A threaded binary tree is a type of binary tree data structure where the empty left and right child
pointers in a binary tree are replaced with threads that link nodes directly to their in-order
predecessor or successor, thereby providing a way to traverse the tree without using recursion or a
stack.
 Threaded binary trees can be useful when space is a concern, as they can eliminate the need for a
stack during traversal. However, they can be more complex to implement than standard binary trees.
 There are two types of threaded binary trees.
Single Threaded: Where a NULL right pointers is made to point to the inorder successor
(if successor exists)
Double Threaded: Where both left and right NULL pointers are made to point to inorder
predecessor and inorder successor respectively.
 The predecessor threads are useful for reverse inorder traversal and postorder traversal.
 The threads are also useful for fast accessing ancestors of a node.
Following diagram shows an example Single Threaded Binary Tree. The dotted lines represent
threads.

23
1.8. AVL TREE
 In 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.
Operations on an AVL Tree:
 Insertion
 Deletion
 Searching [It is similar to performing a search in BST]

Rotating the subtrees in an AVL Tree:

An AVL tree may rotate in one of the following four ways to keep itself balanced:

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.

Left-Rotation in AVL tree

24
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.

Left-Right Rotation:
 A left-right rotation is a combination in which first left rotation takes place after that right rotation
executes.

Right-Left Rotation:
 A right-left rotation is a combination in which first right rotation takes place after that left rotation
executes.

25
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.

1.9. BTREE

 B trees are extended binary search trees that are specialized in m-way searching, since the order of B
trees is 'm'. Order of a tree is defined as the maximum number of children a node can accommodate.
Therefore, the height of a b tree is relatively smaller than the height of AVL tree and RB tree.
 They are general form of a Binary Search Tree as it holds more than one key and two children.
 The various properties of B trees include −
 Every node in a B Tree will hold a maximum of m children and (m-1) keys, since the order of the
tree is m.
 Every node in a B tree, except root and leaf, can hold at least m/2 children
 The root node must have no less than two children.
 All the paths in a B tree must end at the same level, i.e. the leaf nodes must be at the same level.
 A B tree always maintains sorted data.

26
 B trees are also widely used in disk access, minimizing the disk access time since the height of a b
tree is low.
 Note − A disk access is the memory access to the computer disk where the information is stored and
disk access time is the time taken by the system to access the disk memory.

Basic Operations of B Trees

 The operations supported in B trees are Insertion, deletion and searching with the time complexity
of O(log n) for every operation.

 Insertion operation
1. The insertion operation for a B Tree is done similar to the Binary Search Tree but the
elements are inserted into the same node until the maximum keys are reached. The insertion
is done using the following procedure −
Step 1 − Calculate the maximum (m−1)(m−1) and, minimum (⌈m2⌉−1)(⌈m2⌉−1) number of keys a node
can hold, where m is denoted by the order of the B Tree.

Step 2 − The data is inserted into the tree using the binary search insertion and once the keys reach the
maximum number, the node is split into half and the median key becomes the internal node while the left
and right keys become its children.

27
Step 3 − All the leaf nodes must be on the same level.

 The keys, 5, 3, 21, 9, 13 are all added into the node according to the binary search property but if we
add the key 22, it will violate the maximum key property.
 Hence, the node is split in half, the median key is shifted to the parent node and the insertion is then
continued.

Another hiccup occurs during the insertion of 11, so the node is split and median is shifted to the parent.

28
 While inserting 16, even if the node is split in two parts, the parent node also overflows as it reached the
maximum keys. Hence, the parent node is split first and the median key becomes the root. Then, the leaf
node is split in half the median of leaf node is shifted to its parent.

Deletion operation
The deletion operation in a B tree is slightly different from the deletion operation of a Binary Search
Tree. The procedure to delete a node from a B tree is as follows −
Case 1 − If the key to be deleted is in a leaf node and the deletion does not violate the minimum key
property, just delete the node.

29
Case 2 − If the key to be deleted is in a leaf node but the deletion violates the minimum key property,
borrow a key from either its left sibling or right sibling. In case if both siblings have exact minimum
number of keys, merge the node in either of them.

Case 3 − If the key to be deleted is in an internal node, it is replaced by a key in either left child or right
child based on which child has more keys. But if both child nodes have minimum number of keys,
they’re merged together.

30
Case 4 − If the key to be deleted is in an internal node violating the minimum keys property, and both its
children and sibling have minimum number of keys, merge the children. Then merge its sibling with its
parent.

The final B tree after inserting all the elements is achieved.

1.10.B+ TREE

 The B+ trees are extensions of B trees designed to make the insertion, deletion and searching
operations more efficient.
 The properties of B+ trees are similar to the properties of B trees, except that the B trees can store
keys and records in all internal nodes and leaf nodes while B+ trees store records in leaf nodes and
keys in internal nodes. One profound property of the B+ tree is that all the leaf nodes are connected

31
 to each other in a single linked list format and a data pointer is available to point to the data present
in disk file. This helps fetch the records in equal numbers of disk access.
 Since the size of main memory is limited, B+ trees act as the data storage for the records that
couldn’t be stored in the main memory. For this, the internal nodes are stored in the main memory
and the leaf nodes are stored in the secondary memory storage.

Properties of B+ trees

minimum of ⌈m2⌉⌈m2⌉ children and ⌈m−12⌉⌈m−12⌉ keys, since the order of the tree is m.
 Every node in a B+ Tree, except root, will hold a maximum of m children and (m-1) keys, and a

 The root node must have no less than two children and at least one search key.
 All the paths in a B tree must end at the same level, i.e. the leaf nodes must be at the same level.
 A B+ tree always maintains sorted data.

Basic Operations of B+ Trees

 The operations supported in B+ trees are Insertion, deletion and searching with the time complexity
of O(log n) for every operation.
 They are almost similar to the B tree operations as the base idea to store data in both data structures
is same. However, the difference occurs as the data is stored only in the leaf nodes of a B+ trees,
unlike B trees.

Insertion operation

The insertion to a B+ tree starts at a leaf node.

Step 1 − Calculate the maximum and minimum number of keys to be added onto the B+ tree node.

Step 2 − Insert the elements one by one accordingly into a leaf node until it exceeds the maximum key
number.
32
Step 3 − The node is split into half where the left child consists of minimum number of keys and the
remaining keys are stored in the right child.

Step 4 − But if the internal node also exceeds the maximum key property, the node is split in half where the
left child consists of the minimum keys and remaining keys are stored in the right child. However, the
smallest number in the right child is made the parent.

Step 5 − If both the leaf node and internal node have the maximum keys, both of them are split in the similar
manner and the smallest key in the right child is added to the parent node.

33
[Link]

 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.

34
 Max Heap Construction Algorithm

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 Data Structure

Heap Data Structure is generally taught with Heapsort. Heapsort algorithm has limited uses because
Quicksort is better in practice. Nevertheless, the Heap data structure itself is enormously used.
1. Priority Queues: Heaps are commonly used to implement priority queues, where elements with higher
priority are extracted first. This is useful in many applications such as scheduling tasks, handling
interruptions, and processing events.
2. Sorting Algorithms: Heapsort, a comparison-based sorting algorithm, is implemented using the Heap
data structure. It has a time complexity of O(n log n), making it efficient for large datasets.
3. Graph algorithms: Heaps are used in graph algorithms such as Prim’s Algorithm, Dijkstra’s algorithm.,
and the A* search algorithm.
4. Lossless File Compression: Heaps are used in data compression algorithms such as Huffman coding,
which uses a priority queue implemented as a min-heap to build a Huffman tree.
5. Medical Applications: In medical applications, heaps are used to store and manage patient information
based on priority, such as vital signs, treatments, and test results.
6. Load balancing: Heaps are used in load balancing algorithms to distribute tasks or requests to servers, by
processing elements with the lowest load first.
7. Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest)
element in an array. See method 4 and 6 of this post for details.
8. Resource allocation: Heaps can be used to efficiently allocate resources in a system, such as memory
blocks or CPU time, by assigning a priority to each resource and processing requests in order of priority.

35