Chameli Devi Group of Institutions

Department of Computer Science and Engineering

Subject Notes
CS 303- Data Structure
UNIT-III
Syllabus

Tree: Definitions -Height, Depth, Order, Degree. Binary Search Tree -Operations, Traversal/Search.
AVL Tree, Heap, Applications and Comparison of Various Types of Tree. Introduction to Forest,
Multi-Way Tree, B Tree, B+ Tree, B* Tree and Red-Black Tree.

Tree: Definitions

Tree is a non-linear data structure in which data is organized in random order. A tree data structure
can be defined as follows: -
Tree is a non-linear data structure which organizes data in hierarchical structure.
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

Figure 3.1 Tree

In a tree data structure, we use the following terminology: -

1. Root Node
In a tree data structure, the first node is called as 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 cannot have multiple root
nodes in a tree.
 Figure 3.2 Root Node
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.

Figure 3.3 Edge

3. Parent Node
In a tree data structure, the node which is predecessor of any node is called as Parent node. Parent
node can also be defined as "The node which has child / children".

Figure 3.4 Parent Node

4. Child Node
In a tree data structure, the node which is descendant of any node is called as Childnode. In a tree,
any parent node can have any number of child nodes. In a tree, all the nodes except root are child
nodes.
 Figure 3.5 Child Node
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.

Figure 3.6 Siblings

6. Leaf Node
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.

Figure 3.7 Leaf Node

7. Internal Nodes
In a tree data structure, the node which has at least one child is called as Internal node. In a tree data
structure, nodes other than leaf nodes are called as Internal Nodes. Internal nodes are also called as
'Non-Terminal' nodes.
 Figure 3.8 Internal Nodes
8. Degree
In a tree data structure, the total number of children of a node is called as Degree of that node. The
highest degree of a node among all the nodes in a tree is called as 'Degree of Tree'.

Figure 3.9 Degree

9. Level of Tree
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).

Figure 3.10 Level of Tree

10. Height of Tree
In a tree data structure, the total number of edges 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'.

Figure 3.11 Height of Tree

11. Depth of Tree
In a tree data structure, the total number of edges 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 a tree, depth of the root node is '0'.

Figure 3.12 Depth of Tree

12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to another node is called
as Path between those 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.

Figure 3.13 Path

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.

Figure 3.14 Sub Tree

Binary Search Tree Operations
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. To enhance the performance of binary tree, we use special type of binary
tree known as Binary Search Tree.
Binary search tree mainly focuses 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.
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.

Figure 3.15 Binary Search Tree

Operations on Binary Search Tree

The following operations are performed on a binary search tree:-
1) 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.

2) 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 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.
Step 7: After reaching a leaf node, then insert the newNode as left child if newNode is smaller or
equal to that leaf else insert it as right child.

3) 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 following three cases:-
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 is found using step 2.
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.

Binary Search Tree – Traversal

There are three types of binary search tree traversal.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
Example-
Consider the following binary search tree-

Figure 3.16 Example of Binary Search 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.
The In - Order Traversal of the above-mentioned tree is10, 20, 30, 100, 150, 200, 300.

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

In Pre-Order traversal, the root node is visited before left child and right child node. 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.
The Pre - Order Traversal of the above-mentioned tree is100,20,10,30,200,150 ,300.

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.
The Post - Order Traversal of the above-mentioned tree is 10, 30, 20, 150, 300 ,200 ,100.

AVL Tree
AVL tree is a self-balanced binary search tree. That means, an AVL tree is also a binary search tree but
it is a balanced tree. A binary tree is said to be balanced, if the difference between the height of left
subtree and right subtree of every node in the tree is either -1, 0 or +1. In other words, a binary tree
is said to be balanced if for every node, height of its children differs by at most one. In an AVL tree,
every node maintains an extra information known as balance factor.
The balance factor of a node is calculated either height of left subtree - height of right subtree.

There are four rotations and they are classified into two types.

Figure 3.17 Rotation AVL Tree

The following operations are performed on an AVL tree:-
1. Search Operation in AVL Tree
In an AVL tree, the search operation is performed with O(log n) time complexity. The search
operation in the AVL tree is similar to the search operation in a Binary search tree. 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 matched, then display "Given node is found!!!" and terminate the function
Step 4 - If both are not matched, 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 find the exact element or until the search element is compared
with the leaf node.
Step 8 - If we reach to the node having the value equal to the search value, then display "Element is
found" and terminate the function.
Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then
display "Element is not found" and terminate the function.

2. Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a
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 that tree is said to be
imbalanced. In this case, perform suitable Rotation to make it balanced and go for next operation.

3. Deletion Operation in AVL Tree

The deletion operation in AVL Tree is similar to deletion operation in BST. But after every deletion
operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion
go for next operation otherwise perform suitable rotation to make the tree balanced.

Heap
A heap is a complete binary tree and the complete binary tree is a binary tree in which all the levels
except the last level, i.e., leaf node should be completely filled and all the nodes should be left-
justified.

Figure 3.18 Heap

There are two types of the heap:
 Min Heap
 Max Heap
Min Heap: The value of the parent node should be less than or equal to either of its children.
Or
In other words, the min-heap can be defined as, for every node i, the value of node i is greater than
or equal to its parent value except the root node.

Figure 3.19 Min Heap

Max Heap: The value of the parent node is greater than or equal to its children.
Or
In other words, the max heap can be defined as for every node i, the value of node i is less than or
equal to its parent value except the root node.

Figure 3.20 Max Heap

Heap application

 Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nlogn).
 Priority Queue: It uses binary heap to efficient implement operations insert(), delete(),
extract_max(), update() in O(logn) time.
 Graph Algorithms: Some of the Graph Algorithms also use heaps to reduce its time complexity like
Dijkstra’s Algorithm and Minimum Spanning Tree.
 K-way merge: A heap data structure is useful to merge many already-sorted input streams into a
single sorted output stream.
 Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest)
element in an array.

Comparison of various types of tree

There are different types of binary trees and they are as follows:-
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. 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
Tree
Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree.

Figure 3.21 Strictly Binary Tree

2. Complete Binary Tree
In a binary tree, every node can have a maximum of two children. But in complete binary tree all the
nodes must have exactly two children and at every level of complete binary tree there must be 2
level numbers of 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 Tree.
Complete binary tree is also called as Perfect Binary Tree.

Figure 3.22 Complete 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.

Figure 3.23 Extended Binary Tree

Introduction to Forest
Forest is a collection of disjoint trees. In other words, we can also say that forest is a collection of an
acyclic graph which is not connected. Here is a pictorial representation of a forest.

Figure 3.24 Forest

Here you can see that there is no connected tree in the example. A single tree and empty graph is
also an example of forest data structure.
Uses of Forest Data Structure
 Big Data and Web Scrapers
Websites are organized in the form of a tree data structure where the main page forms the root
node and the subsequent hyperlinks from that page represents the rest of the tree. When Web
scrapers scrap multiple such websites, they represent it in the form of a forest of several trees.
 Operating System Storage
If you are working on a Windows-based operating system, you would be able to see various disks in
the system such as C drive (C:\), D drive (D:\). You can think of each drive as different trees and the
collection of all storage as the forest.

Introduction to Multi-way Tree

A multiway tree is a tree that can have more than two children.
A multiway tree of order m (or an **m-way tree) is the one in which a tree can have m children.
An m-way search tree is a m-way tree in which:
 Each node has m children and m-1 key fields
 The keys in each node are in ascending order.
 The keys in the first i children are smaller than the j-th key
 The keys in the last m-i children are larger than the j-th key
 In a binary search tree, m=2. So, it has one value and two sub trees.
M-way search trees give the same advantages to m-way trees that binary search trees gave to binary
trees - they provide fast information retrieval and update.
However, they also have the same problems that binary search trees had - they can become
unbalanced, which means that the construction of the tree becomes of vital importance.
In m-way search tree, each sub-tree is also a m-way search tree and follows the same rules.
An extension of a multiway search tree of order m is a B-tree of order m.
This type of tree will be used when the data to be accessed/stored is located on secondary storage
devices because they allow for large amounts of data to be stored in a node.

Figure 3.25 Multiway Tree

Introduction to B Tree
B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can
have at most m-1 keys and m children. One of the main reasons of using B tree is its capability to
store large number of keys in a single node and large key values by keeping the height of the tree
relatively small.
A B tree of order m contains all the properties of an M way tree. In addition, it contains the following
properties.
 Every node in a B-Tree contains at most m children.
 Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
 The root nodes must have at least 2 nodes.
 All leaf nodes must be at the same level.
 It is not necessary that, all the nodes contain the same number of children but, each node must
have m/2 number of nodes.

Construct a B-Tree of Order 5 by inserting following numbers.

1,12,8,2,25,6,14,28,17,7,52,16,48,68,3,26,29,53,55,45,67.

1) insert 1

2) insert 12

3) insert 8,2 and 25

4) insert 6,14,28,17

5) insert 7,52,16,48,68,3,26,29,53,55,45.
Introduction to B+ tree
A B+ tree is a data structure often used in the implementation of database indexes. Each node of the
tree contains an ordered list of keys and pointers to lower level nodes in the tree. These pointers can
be thought of as being between each of the keys. To search for or insert an element into the tree, one
loads up the root node, finds the adjacent keys that the searched-for value is between and follows
the corresponding pointer to the next node in the tree. Recursing eventually leads to the desired
value or the conclusion that the value is not present.
B+ trees use some clever balancing techniques to make sure that all of the leaves are always on the
same level of the tree, that each node is always at least half full (rounded) of keys, and (therefore)
that the height of the tree is always at most ceiling(log(k)) of base ceiling(n/2) where k is the number
of values in the tree and n is the maximum number of pointers ( maximum number of nodes + 1) in
each block
Properties of B+ Tree
 The root node points to at least two nodes.
 All non-root nodes are at least half full.
 For a tree of order m, all internal nodes have m-1 keys and m pointers.
 B+ Tree grows upwards.
 B+ Tree is balanced.
 Sibling pointers allow sequential searching.

Figure 3.26 B+ Tree

Introduction to B* tree

B* tree of order m is a search tree that is either empty or that satisfies three properties:
 The root node has minimum two and maximum 2 floor ((2m-2)/3) +1 children.
 Other internal nodes have the minimum floor ((2m-1)/3) and maximum m children.
 All external nodes are on the same level.

The advantage of using B* trees over B-trees is a unique feature called the ‘two-to-three’ split. By
this, the minimum number of keys in each node is not half the maximum number, but two-thirds of it,
making data far more compact. However, the disadvantage of this is a complex deletion operation.

Introduction to Red-Black tree

Red - Black Tree is another variant of Binary Search Tree in which every node is colored either red or
black. We can define a Red Black Tree as follows: -Red Black Tree is a Binary Search Tree in which
every node is colored either red or black.
In a Red Black Tree the color of a node is decided based on the Red Black Tree properties.
Properties of Red Black Tree
1. Red - Black Tree must be a Binary Search Tree.
2. The Root node must be colored black.
3. The children of Red colored node must be colored black. (There should not be two consecutive Red
nodes).
4. In all the paths of the tree there must be same number of black colored nodes.
5. Every new node must insert with red color.
6. Every leaf (i.e. NULL node) must be colored black

Figure 3.27 Red Black Tree