MODULE 4

Trees
 Module 4: Syllabus

Definitions and properties, representation of binary trees,

threaded binary tree, binary tree traversals, binary search tree,
AVL trees. Operations on each of the trees and their
algorithms. B Tree, B+ Tree. Heaps and Heap Sort
 Introduction
• Tree data structure is a hierarchical structure that is
used to represent and organize data in a way that is easy
to navigate and search.
• It is a collection of nodes that are connected by edges
and has a hierarchical relationship between the nodes.
• The topmost node of the tree is called the root, and the
nodes below it are called the child nodes.
• Each node can have multiple child nodes, and these child
nodes can also have their own child nodes, forming a
recursive structure
• 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.
 Tree terminologies
• The first node in a tree is called the root (A) node.
• A link connecting one node to another is called an edge.
• 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.
• The node which has a link from its parent node is called as child
node.
• The nodes with same parent are called as Sibling nodes.
• Nodes without links to other child nodes are called leaves, or leaf
nodes (I, J, K, F, G, H).
• The tree height is the maximum number of edges from the root
node to a leaf node. The height of the tree shown in the diagram is
3.
• The height of a node is the maximum number of edges between
the node and a leaf node.
• The tree size is the number of nodes in the tree.
• The depth of a tree longest path from the root to any leaf in terms
of edges.
 Properties of tree
• A parent node has links to its child nodes. Another word for a parent
node is internal node.
• A node can have zero, one, or many child nodes.
• A node can only have one parent node.
 Basic Operations Of Tree Data Structure
• Create – create a tree in the data structure.
• Insert − Inserts data in a tree.
• Search − Searches specific data in a tree to check whether it is present
or not.
• Traversal - visiting each node in a tree.
 Types of Trees

• Binary Trees: Each node has up to two children, the left child node and the right
child node. This structure is the foundation for more complex tree types like Binay
Search Trees and AVL Trees.

• Binary Search Trees (BSTs): A type of Binary Tree where for each node, the left
child node has a lower value, and the right child node has a higher value.

• AVL Trees: A type of Binary Search Tree that self-balances so that for every node,
the difference in height between the left and right subtrees is at most one. This
balance is maintained through rotations when nodes are inserted or deleted.
 Binary Tree
• A Binary Tree Data Structure is a hierarchical
data structure in which each node has at most two
children, referred to as the left child and the right
child.

• It is commonly used in computer science for

efficient storage and retrieval of data, with various
operations such as insertion, deletion, and
traversal.
 Representation of Binary Tree

Each node in a Binary Tree has three parts:

• Data
• Pointer to the left child
• Pointer to the right child
 Construction of Binary Tree
typedef struct Node
{
int data;
struct Node* left;
struct Node* right;
} Node;
 create a new node

Node* createNode(int data)

{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Inserting a node in a binary tree
Search for a node in the binary tree
 Types of Binary Trees
• A balanced Binary Tree has at most 1 in
difference between its left and right
subtree heights, for each node in the tree.
• A complete Binary Tree has all levels full
of nodes, except the last level, which is
can also be full, or filled from left to
right. The properties of a complete Binary
Tree means it is also balanced.
• A full Binary Tree is a kind of tree where
each node has either 0 or 2 child nodes.
• A perfect Binary Tree has all leaf nodes
on the same level, which means that all
levels are full of nodes, and all internal
nodes have two child nodes. The
properties of a perfect Binary Tree means
it is also full, balanced, and complete.
 Tree Traversal
There are three common ways to traverse a tree:

• Inorder: Traverse the left subtree (in order), visit the root and the
traverse the right subtree (in order).

• Preorder: Visit the root, traverse the left subtree (preorder) and
then traverse the right subtree (preorder).

• Postorder: Traverse the left subtree (postorder), traverse the right

subtree (postorder) and then visit the root.
 Inorder Traversal
• Inorder traversal visits the node in the order:
Left -> Root -> Right

Algorithm
• Traverse the left subtree, i.e., call Inorder(left->subtree)
• Visit the root.
• Traverse the right subtree, i.e., call Inorder(right->subtree)
Contd…

void inorderTraversal(struct Node* root)

{
if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
 Preorder Traversal
• Preorder traversal visits the node in the order:
Root -> Left -> Right.

Algorithm
• Visit the root.
• Traverse the left subtree, i.e., call Preorder(left->subtree)
• Traverse the right subtree, i.e., call Preorder(right->subtree)
Contd..
void preorderTraversal(struct Node* root)
{
if (root == NULL)
return;
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
 Postorder Traversal
• Postorder traversal visits the node in the order
Left -> Right -> Root

Algorithm
• Traverse the left subtree, i.e., call Postorder(left->subtree)
• Traverse the right subtree, i.e., call Postorder(right->subtree)
• Visit the root
 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.
 Example of binary search tree

binary search tree Not a binary search tree

 Threaded Binary Tree
• 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.
 AVL Tree
• The AVL tree is named after its inventors, Georgy
Adelson-Velsky and Landis, who published it in their 1962
paper “An algorithm for the organization of information”.
• 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.
• Perform rotation in AVL tree only in case if
Balance Factor is other than -1, 0, and 1.

Balance Factor (k) = height (left(k)) - height (right(k))

 AVL Rotations

• An AVL tree may rotate in one of the following four ways

to keep itself balanced.
➢Left rotation
➢Right rotation
➢Left right rotation
➢Right left rotation
Left rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation
Q: Construct an AVL tree having the following elements
H, I, J, B, A, E, C, F, D, G, K, L
1. Insert H, I, J The resultant balance tree is:
2. Insert B, A
The resultant balance tree is:
3. Insert E 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 4a) We first perform LL rotation on node E
The resultant tree after LL rotation is:

4b) We then perform RR rotation on node B

The resultant balanced tree after RR rotation
5. Insert G 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
6. Insert K
The resultant balanced tree after RR rotation is:
7. Insert L
Construct an AVL tree having the following elements : AVL Tree Example 2

• Let the initial tree be

Initial tree for insertion

 Inserting a node in AVL tree

New node

Go to the appropriate leaf node to insert

a newNode
Finding the location to insert newNode
Inserting the new node
Balancing the tree with rotation
Balancing the tree with rotation
• The final tree is

Final balanced tree

 Algorithm to Delete a node
• A node is always deleted as a leaf node. After deleting a node, the
balance factors of the nodes get changed. In order to rebalance the
balance factor, suitable rotations are performed.
a.There are three cases for deleting a
node:If nodeToBeDeleted is the leaf node (ie. does not
have any child), then remove nodeToBeDeleted.
b.If nodeToBeDeleted has one child, then substitute the
contents of nodeToBeDeleted with that of the child.
Remove the child.
c.If nodeToBeDeleted has two children, find the inorder
successor w of nodeToBeDeleted (ie. node with a
minimum value of key in the right subtree).
 Finding the successor

Substitute the node to be

deleted

Substitute the contents

of nodeToBeDeleted with that of w
• Remove the leaf node w
• Update balanceFactor of the nodes

Update bf
Rebalance the tree if the balance factor of any of the nodes is not equal to
-1, 0 or 1.

Right-rotate for balancing the

tree
Avl tree final
Applications of AVL Tree:

1.It is used to index huge records in a database and also to

efficiently search in that.
2.For all types of in-memory collections, including sets and
dictionaries, AVL Trees are used.
3.Database applications, where insertions and deletions are less
common but frequent data lookups are necessary
4.Software that needs optimized search.
5.It is applied in corporate areas and storyline games.
Advantages of AVL Tree:

1.AVL trees can self-balance themselves.

2.It is surely not skewed.
3.Better searching time complexity compared to other trees like
binary tree.
4.Height cannot exceed log(N), where, N is the total number of
nodes in the tree.
Disadvantages of AVL Tree:
1.It is difficult to implement.
2.It has high constant factors for some of the operations.
3.Due to its rather strict balance, AVL trees provide complicated
insertion and removal operations as more rotations are
performed.
4.Take more processing for balancing.
 B-tree
• A B-tree (Balanced Tree) is a self-balancing tree data structure that is commonly used for
organizing and storing large amounts of data in systems that read and write large blocks of
data (such as databases and file systems).
• The B-tree is highly capable of storing systems that write large blocks of data. The B-tree
simplifies the binary search tree by allowing nodes with more than two children.
• It is also known as a height-balanced m-way tree.
There are some conditions that must be hold by the B-Tree:
• All the leaf nodes of the B-tree must be at the same level.

• Above the leaf nodes of the B-tree, there should be no empty sub-trees.

• B- tree’s height should lie as low as possible.

The goal in designing a B-tree is to minimize its
height, as this directly impacts the efficiency of
the tree's operations.
By balancing the number of keys in each node
and maintaining a high branching factor, the B-
tree remains efficient even with large datasets.
B-Tree Operations (Time complexity)
S No Algorithm Complexity

1 Search 0 (log n)

2 Insert 0 (log n)

3 Delete 0 (log n)
B-Tree Operations
1. Searching
• Similar to binary search trees, B trees also allow for searching. A binary tree
search is similar to a B-Tree search. The algorithm uses recursion and is
comparable. The search is optimized at each level, so it is in a different
branch if the key value isn’t in the parent’s range.
Insertion into a B-tree
 Deletion into a B-tree
Deletion in a B-Tree involves removing a key from the appropriate position
while maintaining the tree's properties. This may require borrowing a key from a
sibling or merging nodes to maintain the minimum degree property.
• Time Complexity: O(log m​ n), which simplifies to O(log n) for large
datasets
 B+ Tree
B+ tree is a type of multi-way search tree that
maintains sorted data and allows for
efficient insertion, deletion, and search operations.

Structure of a B+ Tree
• Root Node: The topmost node of the tree, which can be either a leaf or an internal
node. Initially, the root is both a leaf and an internal node, but as the tree grows, it can
become an internal node only, pointing to other nodes.
• Internal Nodes: Internal nodes act as a roadmap to locate data within the leaf nodes.
These nodes do not store actual data records; instead, they maintain keys and pointers
that guide searches to the appropriate child nodes or leaf nodes.
• Leaf Nodes: All actual data records are stored in the leaf nodes, located at the bottom
level of the tree. The leaf nodes are linked together to form a linked list, facilitating
efficient range queries and sequential data access.
Properties of B+ trees

• Every node in a B+ Tree, except root, will

hold a maximum of m children and (m-1)
keys, and a minimum of ⌈m2⌉⌈m2⌉ children
and ⌈m−12⌉⌈m−12⌉ keys, since the order of
the tree is m.
• 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.
• Operations on B+ Tree in Data Structure
You can execute two operations on a B+ tree in a data structure:
• Insertion operation
• Deletion operation

• Insertion Operation on B+ Tree in Data Structure

Applications
• Database indexing: For fast lookups, insertions, deletions, and range
queries in large datasets.
• File systems: Managing files and directories, allowing fast access to file
metadata.
• Operating systems: Managing memory and disk blocks for efficient virtual
memory handling.
• Key-value stores: Handling large datasets in NoSQL systems with fast
retrieval and updates.
• Distributed systems: Efficient indexing and data retrieval across distributed
storage and databases.
• Data warehousing: Managing large datasets for analytical queries.
Heap Sort
• Heap data structure is a complete binary tree that satisfies the heap
property.
• Heap Sort is an efficient sorting technique based on the heap data
structure.
• The concept of heap sort is to eliminate the elements one by one
from the heap part of the list, and then insert them into the sorted
part of the list.
• HeapSort is theoretically the best algorithm in terms of both time
and space. Can be used in real time systems or embedded systems
where we cannot afford to have worst case time and/or space.
• Max Heap: In a max heap, the key at the root must be the largest among
all keys present in the binary heap. The same property must be recursively
true for all subtrees.
• Min Heap: In a min heap, the key at the root must be the smallest among
all keys present in the binary heap.

Heapify Method

• The heapify method of a binary tree is to convert the tree into a heap data
structure. This method uses recursion approach to heapify all the nodes of
the binary tree.
Applications

• Heap is used while implementing a priority queue.

• Dijkstra's Algorithm
• Heap Sort
Heap Sort Algorithm
Working of Heap sort Algorithm
Heapsort has a running time of O(nlogn).
Pros
• Time-efficient with time complexity of O(nlogn)O(nlogn)
• Less memory usage
• Consistent performance: it performs equally well in best-, average-,
and worst-case scenarios
Cons
• Unstable sort
• External sorting not possible with heapsort