MC4101

UNIT- II HIERARCHICAL DATA STRUCTURES

BINARY TREE

TREE ADT
 A tree allows items to be organised based on some relationship
between them.
 Each node (containing a value) has a parent and it may have many
children.
 There is a special node called the root which does not have any
parent node.
 A node can have any number of children including zero.
 This tree allows deletions only from leaf nodes.

The ADTS for a general tree are the following:

1) Root(): Gets the position of the root of the general tree.

2) Parent (): Returns the position of the parent node of the specified
node p.

3) Children (): Returns the children of the specified node p.

4) IsInternal (): Returns true if the specified node p is an internal node,
otherwise false is returned.

5) IsExternal (): Returns true if the specified node p is an external node,

otherwise false is returned.

6) IsRoot (): Returns true if the specified node p is a root node

7) AddChild (): Adds a child to given parent node.

8) Removeexternal(): Removes the external node specified.

9) Replace (): Replace value stored at a position with another

value.
 MC4101

10) Swap (): Swap values stored at two nodes.

Types of Tree
✔ Binary Trees
✔ Binary Search
✔ AVL Trees
✔ B-Trees
✔ Heap Trees

BINARY TREE

 Those trees in which each and every node has maximum two branches
are known as binary trees.
 It can also be stated in other words that if the degree of every node of
the tree is maximum two then it is known as a binary tree.
 The sub-trees of a node can be differentiated with the help of right and
left sub- tree in a binary tree.
 A binary tree can be represented using a finite set of elements which is
either empty or subdivided into three disjoint subsets.
 The Root of the tree is the single element that makes up the first
subset of the tree.
 The remaining two sets are right or left subtrees of the actual trees.
 The right or left subtree of a tree may be empty.
 A typical binary tree is shown in figure. There may be maximum two
branches for a node in a binary tree.
 While determining the degree of a node of a Binary tree the following
three criteria are taken into consideration:
 MC4101

 A tree is considered to be a Binary Tree if it is either empty or every

node in it satisfies the following conditions:

1) There is no child or

2) There is just a left child or

3) There is just a right child or

4) There are both a left child and a right child.

For example, A is the root of the Binary Tree as shown in figure 2.9. The roots
of the left and right subtrees are B and C respectively. A is the father of B and
C. B and C are the left and right son of A respectively.

Binary Tree Components

There are three binary tree components. Every binary tree node has these
three components associated with it. It becomes an essential concept for
programmers to understand these three binary tree components:
 ∙ Data element

 ∙ Pointer to left subtree

 ∙ Pointer to right subtree

 MC4101

These three binary tree components represent a node. The data resides in the
middle. The left pointer points to the child node, forming the left sub-tree. The
right pointer points to the child node at its right, creating the right subtree.

Binary Tree Types

There are various binary tree types, and each of these binary tree types has
unique characteristics. Here are each of the binary tree types in detail:

1. Full Binary Tree

✔ It is a special kind of a binary tree that has either zero children or two
children.

✔ It means that all the nodes in that binary tree should either have two child
nodes of its parent node or the parent node is itself the leaf node or the
external node.

✔ In other words, a full binary tree is a unique binary tree where every node
except the external node has two children. When it holds a single child, such
a binary tree will not be a full binary tree.
✔ Here, the quantity of leaf nodes is equal to the number of internal nodes plus
one. The equation is like L=I+1, where L is the number of leaf nodes, and I is
the number of internal nodes.

Here is the structure of a full binary tree:

2. Complete Binary Tree

 MC4101

✔ A complete binary tree is another specific type of binary tree where all the tree
levels are filled entirely with nodes, except the lowest level of the tree.
✔ Also, in the last or the lowest level of this binary tree, every node should
possibly reside on the left side.
✔ Here is the structure of a complete binary tree:

3. Perfect Binary Tree

A binary tree is said to be „perfect‟ if all the internal nodes have strictly two
children, and every external or leaf node is at the same level or same depth
within a tree. A perfect binary tree having height „h‟ has 2h – 1 node. Here is the
structure of a perfect binary tree:

Binary Tree ADT

✔ The ADT for a binary tree is the same as that of a general tree except that
removal of a node and the insertion of a node are different. The ADTS for a
binary tree are the following:

1) LeftChild (): Returns the left child of the specified node, say p.

2) RightChild (): Returns the right child of the specified node, say p.

3) ExpandExternal (): Takes a parent node and makes it internal by giving it

two child nodes.

Operations on Binary Tree

 MC4101

✔ One of the most common operations performed on tree structure is that of

traversal.

✔Traversal is a procedure by which each node in the tree is processed exactly

one in the systematic manner.
o Insertion

o Traversing

o Deletion

o Copy

Binary search tree [BST]

 Binary Search tree can be defined as a class of binary trees, in which

the nodes are arranged in a specific order. This is also called ordered
binary tree.

 In a binary search tree, the value of all the nodes in the left sub-tree is
 MC4101

less than the value of the root.

 Similarly, value of all the nodes in the right sub-tree is greater than or
equal to the value of the root.
 This rule will be recursively applied to all the left and right sub
tree of the root.

As the constraint applied on the BST, we can see that the root node 30
doesn't contain any value greater than or equal to 30 in its left sub-tree and
it also doesn't contain any value less than 30 in its right sub-tree.

Q. Create the binary search tree using the following data elements.

43, 10, 79, 90, 12, 54, 11, 9, 50

1. Insert 43 into the tree as the root of the tree.

2. Read the next element, if it is lesser than the root node element, insert
it as the root of the left sub-tree.

3. Otherwise, insert it as the root of the right of the right sub-tree. The
process of creating BST by using the given elements, is shown in the
image below.
 MC4101

Advantages of using binary search tree

1. Searching become very efficient in a binary search tree since, we get a

hint at each step, about which sub-tree contains the desired element.

2. The binary search tree is considered as efficient data structure in

compare to arrays and linked lists. In searching process, it removes
half sub-tree at every step. Searching for an element in a binary
search tree takes O(log2n) time. In worst case, the time it takes to
search an element is 0(n).

3. It also speed up the insertion and deletion operations as compare to

that in array and linked list.
 MC4101

Operations on Binary Search Tree

There are many operations which can be performed on a binary search tree.
SN Operation Description

1 Searching in BST Finding the location of some specific element

in a binary search tree.

2 Insertion in BST Adding a new element to the binary search

tree at the appropriate location so that the
property of BST do not violate.

3 Deletion in BST Deleting some specific node from a binary

search tree. However, there can be various
cases in deletion depending upon the
number of children, the node have.

Searching

Searching means finding or locating some specific element or node within

a data structure. However, searching for some specific node in binary
search tree is pretty easy due to the fact that, element in BST are stored in a
particular order.

1. Compare the element with the root of the tree.

2. If the item is matched then return the location of the node.
3. Otherwise check if item is less than the element present on root, if so
then move to the left sub-tree.

4. If not, then move to the right sub-tree.

5. Repeat this procedure recursively until match found.

6. If element is not found then return NULL.

MC4101
 MC4101

Insertion

✔ Insert function is used to add a new element in a binary search tree at

appropriate location. Insert function is to be designed in such a way
that, it must node violate the property of binary search tree at each
value.

1. Allocate the memory for tree.

2. Set the data part to the value and set the left and right pointer of tree,
point to NULL.

3. If the item to be inserted, will be the first element of the tree, then the
left and right of this node will point to NULL.

4. Else, check if the item is less than the root element of the tree, if this is
true, then recursively perform this operation with the left of the root.

5. If this is false, then perform this operation recursively with the right
sub-tree of the root.
 MC4101

STEP3 STEP4

Deletion

 Delete function is used to delete the specified node from a binary

search tree. However, we must delete a node from a binary search
tree in such a way, that the property of binary search tree doesn't
violate.
 There are three situations of deleting a node from
binary search tree.

The node to be deleted is a leaf node

 It is the simplest case, in this case, replace the leaf node with the
NULL and simple free the allocated space.
 In the following image, we are deleting the node 85, since the node is
a leaf node, therefore the node will be replaced with NULL and
allocated space will be freed.
 MC4101

The node to be deleted has only one child.

✔ In this case, replace the node with its child and delete the child node,
which now contains the value which is to be deleted.
✔ Simply replace it with the NULL and free the allocated space.

✔ In the following image, the node 12 is to be deleted. It has only one

child. The node will be replaced with its child node and the replaced
node 12 (which is now leaf node) will simply be deleted.
 MC4101

The node to be deleted has two children.

 It is a bit complexed case compare to other two cases. However, the
node which is to be deleted, is replaced with its in-order successor
or predecessor recursively until the node value (to be deleted) is
placed on the leaf of the tree. After the procedure, replace the node
with NULL and free the allocated space.

 In the following image, the node 50 is to be deleted which is the root

node of the tree. The in-order traversal of the tree given below.

6, 25, 30, 50, 52, 60, 70, 75.

replace 50 with its in-order successor 52. Now, 50 will be moved to the
leaf of the tree, which will simply be deleted.
MC4101
 MC4101

Basis for
Binary Tree Binary Search Tree
Comparison

A Binary Tree is a non-linear

A Binary Search Tree is an
data structure in which a node
organized binary tree with a
can have 0, 1 or 2 nodes.
Definition structured organization of nodes.
Individually, each node consists
Each subtree must also be of that
of a left pointer, right pointer
particular structure.
and data element.

The values of left subtree of a

There is no required
particular node should be lesser
Structure organization structure of the
than that node and the right
nodes in the tree.
subtree values should be greater.

As these are sorted binary trees,

The operations that can be
Operations they are used for fast and efficient
performed are deletion,
Performed binary search, insertion and
insertion and traversal
deletion.

There are several types. Most

The most popular ones are AVL
common ones are the Complete
Types Trees, Splay Trees, Tango Trees, T-
Binary Tree, Full Binary Tree,
Trees.
Extended Binary Tree
MC4101
MC4101
 MC4101

RED BLACK TREES

Properties of Red Black Tree

 Property #1: Red - Black Tree must be a Binary Search Tree.

 Property #2: The ROOT node must be colored BLACK.
 Property #3: The children of Red colored node must be colored BLACK.
(There should not be two consecutive RED nodes).
 Property #4: In all the paths of the tree, there should be same number of
BLACK colored nodes.
 Property #5: Every new node must be inserted with RED color.
 Property #6: Every leaf (e.i. NULL node) must be colored BLACK.
 MC4101

 Every Red Black Tree is a binary search tree but every Binary Search
Tree need not be Red Black tree.

Applications:
1. Most of the self-balancing BST library functions like map and set in
C++ (OR TreeSet and TreeMap in Java) use Red-Black Tree.
2. It is used to implement CPU Scheduling Linux. Completely Fair
Scheduler uses it.
3. Besides they are used in the K-mean clustering algorithm for
reducing time complexity.
4. Moreover, MySQL also uses the Red-Black tree for indexes on
tables.

Why Red-Black Trees?

 Most of the BST operations (e.g., search, max, min, insert, delete..
etc) take O(h) time where h is the height of the BST.
 The cost of these operations may become O(n) for a skewed
Binary tree.
 MC4101

 If we make sure that the height of the tree remains O(log n) after
every insertion and deletion, then we can guarantee an upper
bound of O(log n) for all these operations.
 The height of a Red-Black tree is always O(log n) where n is the
number of nodes in the tree.

A Red Black Tree is a category of the self-balancing binary search tree. It was created in
1972 by Rudolf Bayer who termed them "symmetric binary B-trees."

Sr. No. Algorithm Time Complexity

1. Search O(log n)

2. Insert O(log n)

3. Delete O(log n)

“n” is the total number of elements in the red-black tree.

Advantages of Red Black Tree

1. Red black tree are useful when we need insertion and deletion relatively
frequent.
2. Red-black trees are self-balancing so these operations are guaranteed
to be O(logn).
3. They have relatively low constants in a wide variety of scenarios.
 MC4101

EXAMPLE
 MC4101

Insertion into RED BLACK Tree

In a Red-Black Tree, every new node must be inserted with the color RED. The
insertion operation in Red Black Tree is similar to insertion operation in Binary
Search Tree. But it is inserted with a color property. After every insertion
operation, we need to check all the properties of Red-Black Tree. If all the
properties are satisfied then we go to next operation otherwise we perform the
following operation to make it Red Black Tree.

 1. Recolor
 2. Rotation
 3. Rotation followed by Recolor

The insertion operation in Red Black tree is performed using the following
steps...

 Step 1 - Check whether tree is Empty.

 Step 2 - If tree is Empty then insert the newNode as Root node with
color Black and exit from the operation.
 Step 3 - If tree is not Empty then insert the newNode as leaf node with
color Red.
 Step 4 - If the parent of newNode is Black then exit from the operation.
 Step 5 - If the parent of newNode is Red then check the color of
parentnode's sibling of newNode.
 Step 6 - If it is colored Black or NULL then make suitable Rotation and
Recolor it.
 Step 7 - If it is colored Red then perform Recolor. Repeat the same until
tree becomes Red Black Tree.
 MC4101





MC4101
 MC4101

INSERT 40
MC4101
 MC4101

DELETION INTO RED BLACK TREE

First, search for an element to be deleted

1. If the element to be deleted is in a node with only left child, swap this
node with one containing the largest element in the left subtree. (This
node has no right child).
2. If the element to be deleted is in a node with only right child, swap this
node with the one containing the smallest element in the right subtree
(This node has no left child).
3. If the element to be deleted is in a node with both a left child and a right
child, then swap in any of the above two ways. While swapping, swap
only the keys but not the colors.
4. The item to be deleted is now having only a left child or only a right
child. Replace this node with its sole child. This may violate red
constraints or black constraint. Violation of red constraints can be
easily fixed.
5. If the deleted node is black, the black constraint is violated. The
elimination of a black node y causes any path that contained y to have
one fewer black node.
6. Two cases arise:
 MC4101

o The replacing node is red, in which case we merely color it black

to make up for the loss of one black node.
o The replacing node is black.

EXAMPLE:

Now show the red-black trees that result from the successful deletion of the
keys in the order 8, 12, 19,31,38,41.

Solution:
 MC4101

Delete 38

Delete 41

No Tree.

B-Trees: Definition of B - trees – Basic operations on B-Trees –

Deleting a key from a B-Tree-
B Tree

 B Tree is a specialized m-way tree that can be widely used for disk
access.
 MC4101

 A B-Tree of order m can have at maximum of m-1 keys and m pointers to

its subtree.
 One of the main reason of using B tree is its capability to
store large number of keys in a single node and large key
values by keeping the height of the tree relatively small. It is
also known as a height-balanced m-way tree.

A B tree of order m contains all the properties of an M way tree. In addition, it

contains the following properties.

1. Every node in a B-Tree contains at most m children.

2. Every node in a B-Tree except the root node and the leaf node contain at
least m/2 children.

3. The root nodes must have at least 2 nodes.

4. All leaf nodes must be at the same level.

 It is not necessary that, all the nodes contain the same

number of children but, each node must have m/2 number
of nodes. A B tree of order 4 is shown in the following
image.
 n Handling in Java - Ja
Next
Stay

While performing some operations on B Tree, any property of B Tree may

violate such as number of minimum children a node can have. To maintain the
properties of B Tree, the tree may split or join.

Basic operations on B-Trees

Searching :

 Searching in B Trees is similar to that in Binary search tree.

 For example, if we search for an item 49 in the following B Tree. The
process will something like following :
 MC4101

1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left
sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.

4. match found, return.

Searching in a B tree depends upon the height of the tree. The search
algorithm takes O(log n) time to search any element in a B tree.

Inserting

Insertions are done at the leaf node level. The following algorithm needs to be
followed in order to insert an item into B Tree.

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

Example:

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

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

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore
split the node from the median i.e. 8 and push it up to its parent node shown
as follows.
 MC4101

Deletion

Deletion is also performed at the leaf nodes. The node which is to be deleted
can either be a leaf node or an internal node. Following algorithm needs to be
followed in order to delete a node from a B tree.

1. Locate the leaf node.

2. If there are more than m/2 keys in the leaf node then delete the desired
key from the node.
3. If the leaf node doesn't contain m/2 keys then complete the keys by
taking the element from eight or left sibling.
o If the left sibling contains more than m/2 elements then push its
largest element up to its parent and move the intervening element
down to the node where the key is deleted.
o If the right sibling contains more than m/2 elements then push its
smallest element up to the parent and move intervening element
down to the node where the key is deleted.
4. If neither of the sibling contain more than m/2 elements then create a
new leaf node by joining two leaf nodes and the intervening element of
the parent node.
5. If parent is left with less than m/2 nodes then, apply the above process
on the parent too.

If the the node which is to be deleted is an internal node, then replace the node
with its in-order successor or predecessor. Since, successor or predecessor
will always be on the leaf node hence, the process will be similar as the node
is being deleted from the leaf node.

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

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

Now, 57 is the only element which is left in the node, the minimum number of
elements that must be present in a B tree of order 5, is 2. it is less than that,
the elements in its left and right sub-tree are also not sufficient therefore,
merge it with the left sibling and intervening element of parent i.e. 49.

The final B tree is shown as follows.

 MC4101

Application of B tree

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

Heap implementation :

 Heap is a special type of data structure where the root node or parent
node is compared with its left and right children and arranged according
to the order.
 Suppose, x is a root node and y is the child node, property key(x)<=
key(y) will generate min-heap, and that relation is referred to as "Heap
Property".

 Based on the order of the parent and child nodes, Heap can be
classified in two forms, i.e., Min heap and Max heap.

Min heap

Min heap is a special type of heap data structure that is a complete binary tree
in itself . Min heap has the following properties:

1. Root node value is always smaller in comparison to the other nodes of

the heap.
2. Each internal node has a key value that is always smaller or equal to its
children.

insertNode()

We can perform insertion in the Min heap by adding a new key at the end of
the tree. If the value of the inserted key is smaller than its parent node, we
have to traverse the key upwards for fulfilling the heap property. The insertion
process takes O(log n) time.

extractMin()

It is one of the most important operations which we perform to remove the

minimum value node, i.e., the root node of the heap. After removing the root
node, we have to make sure that heap property should be maintained. The
 MC4101

extractMin() operation takes O(Logn) time to remove the minimum element

from the heap.

getMin()

The getMin() operation is used to get the root node of the heap, i.e., minimum
element in O(1) time.

Example:

Max heap

Max heap is another special type of heap data structure that is also a complete
binary tree in itself in Java. Max heap has the following properties:

1. Root node value is always greater in comparison to the other nodes of

the heap.
2. Each internal node has a key value that is always greater or equal to its
children.

We can perform the following three operations in Max heap:

insertNode()

We can perform insertion in the Max heap by adding a new key at the end of
the tree. If the value of the inserted key is greater than its parent node, we have
to traverse the key upwards for fulfilling the heap property. The insertion
process takes O(log n) time.
 MC4101

extractMax()

It is one of the most important operations which we perform to remove the

maximum value node, i.e., the root node of the heap. After removing the root
node, we have to make sure that heap property should be maintained. The
extractMax() operation takes O(Log n) time to remove the maximum element
from the heap.

getMax()

The getMax() operation is used to get the root node of the heap, i.e., maximum
element in O(1) time.

Example:

Disjoint set data structure

 The disjoint set data structure is also known as union-find data

structure and merge-find set.
 It is a data structure that contains a collection of disjoint or non-
overlapping sets.
 The disjoint set means that when the set is partitioned into the disjoint
subsets.
 The various operations can be performed on the disjoint subsets. In this
case, we can add new sets, we can merge the sets, and we can also find
the representative member of a set. It also allows to find out whether the
two elements are in the same set or not efficiently.
 MC4101

 The disjoint set can be defined as the subsets where there is no

common element between the two sets. Let's understand the disjoint
sets through an example.

s1 = {1, 2, 3, 4}

s2 = {5, 6, 7, 8}

 We have two subsets named s1 and s2. The s1 subset contains the
elements 1, 2, 3, 4, while s2 contains the elements 5, 6, 7, 8.
 Since there is no common element between these two sets, we will not
get anything if we consider the intersection between these two sets.
This is also known as a disjoint set where no elements are common.
 Now the question arises how we can perform the operations on them.
We can perform only two operations, i.e., find and union.

In the case of find operation, we have to check that the element is present in
which set. There are two sets named s1 and s2 shown below:

Suppose we want to perform the union operation on these two sets. First, we
have to check whether the elements on which we are performing the union
operation belong to different or same sets. If they belong to the different sets,
then we can perform the union operation; otherwise, not. For example, we
want to perform the union operation between 4 and 8. Since 4 and 8 belong to
different sets, so we apply the union operation. Once the union operation is
performed, the edge will be added between the 4 and 8 shown as below:

When the union operation is applied, the set would be represented as:
 MC4101

s1Us2 = {1, 2, 3, 4, 5, 6, 7, 8}

Suppose we add one more edge between 1 and 5. Now the final set can be
represented as:

s3 = {1, 2, 3, 4, 5, 6, 7, 8}

If we consider any element from the above set, then all the elements belong to
the same set; it means that the cycle exists in a graph.

How can we detect a cycle in a graph?

We will understand this concept through an example. Consider the below

example to detect a cycle with the help of using disjoint sets.

U = {1, 2, 3, 4, 5, 6, 7, 8}

Each vertex is labelled with some weight. There is a universal set with 8
vertices. We will consider each edge one by one and form the sets.

First, we consider vertices 1 and 2. Both belong to the universal set; we

perform the union operation between elements 1 and 2. We will add the
 MC4101

elements 1 and 2 in a set s1 and remove these two elements from the universal
set shown below:

s1 = {1, 2}

The vertices that we consider now are 3 and 4. Both the vertices belong to the
universal set; we perform the union operation between elements 3 and 4. We
will form the set s3 having elements 3 and 4 and remove the elements from the
universal set shown as below:

s2 = {3, 4}

The vertices that we consider now are 5 and 6. Both the vertices belong to the
universal set, so we perform the union operation between elements 5 and 6.
We will form the set s3 having elements 5 and 6 and will remove these
elements from the universal set shown as below:

s3 = {5, 6}

The vertices that we consider now are 7 and 8. Both the vertices belong to the
universal set, so we perform the union operation between elements 7 and 8.
We will form the set s4 having elements 7 and 8 and will remove these
elements from the universal set shown as below:

s4 = {7, 8}

The next edge that we take is (2, 4). The vertex 2 is in set 1, and vertex 4 is in
set 2, so both the vertices are in different sets. When we apply the union
operation, then it will form the new set shown as below:

s5 = {1, 2, 3, 4}

The next edge that we consider is (2, 5). The vertex 2 is in set 5, and the vertex
5 is in set s3, so both the vertices are in different sets. When we apply the
union operation, then it will form the new set shown as below:

s6 = {1, 2, 3, 4, 5, 6}

Now, two sets are left which are given below:

s4 = {7, 8}

s6 = {1, 2, 3, 4, 5, 6}

The next edge is (1, 3). Since both the vertices, i.e.,1 and 3 belong to the same
set, so it forms a cycle. We will not consider this vertex.

The next edge is (6, 8). Since both vertices 6 and 8 belong to the different
vertices s4 and s6, we will perform the union operation. The union operation
will form the new set shown as below:
 MC4101

s7 = {1, 2, 3, 4, 5, 6, 7, 8}

The last edge is left, which is (5, 7). Since both the vertices belong to the same
set named s7, a cycle is formed.

How can we represent the sets graphically?

We have a universal set which is given below:

U = {1, 2, 3, 4, 5, 6, 7, 8}

We will consider each edge one by one to represent graphically.

First, we consider the vertices 1 and 2, i.e., (1, 2) and represent them through
graphically shown as below:

In the above figure, vertex 1 is the parent of vertex 2.

Now we consider the vertices 3 and 4, i.e., (3, 4) and represent them
graphically shown as below:

In the above figure, vertex 3 is the parent of vertex 4.

Consider the vertices 5 and 6, i.e., (5, 6) and represent them graphically shown
as below:

In the above figure, vertex 5 is the parent of vertex 6.

 MC4101

Now, we consider the vertices 7 and 8, i.e., (7, 8) and represent them through
graphically shown as below:

In the above figure, vertex 7 is the parent of vertex 8.

Now we consider the edge (2, 4). Since 2 and 4 belong to different sets, so we
need to perform the union operation. In the above case, we observe that 1 is
the parent of vertex 2 whereas vertex 3 is the parent of vertex 4. When we
perform the union operation on the two sets, i.e., s1 and s2, then 1 vertex
would be the parent of vertex 3 shown as below:

The next edge is (2, 5) having weight 6. Since 2 and 5 are in two different sets
so we will perform the union operation. We make vertex 5 as a child of the
vertex 1 shown as below:

We have chosen vertex 5 as a child of vertex 1 because the vertex of the graph
having parent 1 is more than the graph having parent 5.
 MC4101

The next edge is (1, 3) having weight 7. Both vertices 1 and 3 are in the same
set, so there is no need to perform any union operation. Since both the
vertices belong to the same set; therefore, there is a cycle. We have detected a
cycle, so we will consider the edges further.

How can we detect a cycle with the help of an array?

Consider the below graph:

The above graph contains the 8 vertices. So, we represent all these 8 vertices
in a single array. Here, indices represent the 8 vertices. Each index contains a -
1 value. The -1 value means the vertex is the parent of itself.

Now we will see that how we can represent the sets in an array.

First, we consider the edge (1, 2). When we find 1 in an array, we observe that
1 is the parent of itself. Similarly, vertex 2 is the parent of itself, so we make
vertex 2 as the child of vertex 1. We add 1 at the index 2 as 2 is the child of 1.
We add -2 at the index 1 where '-' sign that the vertex 1 is the parent of itself
and 2 represents the number of vertices in a set.
 MC4101

The next edge is (3, 4). When we find 3 and 4 in array; we observe that both the
vertices are parent of itself. We make vertex 4 as the child of the vertex 3 so we
add 3 at the index 4 in an array. We add -2 at the index 3 shown as below:

The next edge is (5, 6). When we find 5 and 6 in an array; we observe that both
the vertices are parent of itself. We make 6 as the child of the vertex 5 so we
add 5 at the index 6 in an array. We add -2 at the index 5 shown as below:
 MC4101

The next edge is (7, 8). Since both the vertices are parent of itself, so we make
vertex 8 as the child of the vertex 7. We add 7 at the index 8 and -2 at the index
7 in an array shown as below:

The next edge is (2, 4). The parent of the vertex 2 is 1 and the parent of the
vertex is 3. Since both the vertices have different parent, so we make the
vertex 3 as the child of vertex 1. We add 1 at the index 3. We add -4 at the index
1 as it contains 4 vertices.

Graphically, it can be represented as

 MC4101

The next edge is ( 2,5 ). When we find vertex 2 in an array, we observe that 1 is
the parent of the vertex 2 and the vertex 1 is the parent of itself.

When we find 5 in an array, we find -2 value which means vertex 5 is the parent
of itself.

Now we have to decide whether the vertex 1 or vertex 5 would become a

parent.

Since the weight of vertex 1, i.e., -4 is greater than the vertex of 5, i.e., -2, so
when we apply the union operation then the vertex 5 would become a child of
the vertex 1 shown as below:

In an array, 1 would be added at the index 5 as the vertex 1 is now becomes a

parent of vertex 5. We add -6 at the index 1 as two more nodes are added to
the node 1.

The next edge is (1,3). When we find vertex 1 in an array, we observe that 1 is
the parent of itself. When we find 3 in an array, we observe that 1 is the parent
of vertex 3. Therefore, the parent of both the vertices are same; so, we can say
that there is a formation of cycle if we include the edge (1,3).

The next edge is (6,8). When we find vertex 6 in an array, we observe that
vertex 5 is the parent of vertex 6 and vertex 1 is the parent of vertex 5. When
we find 8 in an array, we observe that vertex 7 is the parent of the vertex 8 and
7 is the parent of itself. Since the weight of vertex 1, i.e., -6 is greater than the
vertex 7, i.e., -2, so we make the vertex 7 as the child of the vertex and can be
represented graphically as shown as below:
 MC4101

We add 1 at the index 7 because 7 becomes a child of the vertex 1. We add -8

at the index 1 as the weight of the graph now becomes 8.

The last edge to be included is (5, 7). When we find vertex 5 in an array, we
observe that vertex 1 is the parent of the vertex 5. Similarly, when we find
vertex 7 in an array, we observe that vertex 1 is the parent of vertex 7.
Therefore, we can say that the parent of both the vertices is same, i.e., 1. It
means that the inclusion (5,7) edge would form a cycle.

till now, we have learnt the weighted union where we perform the union
operation according to the weights of the vertices. The higher weighted vertex
becomes a parent and the lower weighted vertex becomes a child. The
disadvantage of using this approach is that some nodes take more time to
reach its parent. For example, in the above graph, if we want to find the parent
of vertex 6, vertex 5 is the parent of vertex 6 so we move to the vertex 5 and
vertex 1 is the parent of the vertex 5. To overcome such problem, we use the
concept 'collapsing find'.

How collapsing find technique works?

Consider the above example. Once we know the parent of the vertex 6 which is
1 then we directly add the vertex 6 to the vertex 1. We will also update the
array. In an array, add 1 at the index 6 because the parent of 6 is now 1. The
 MC4101

process of directly linking a node to the direct parent of a set is known as a

collapsing find. Similarly, we can link the nodes 8 and 4 to the node 1.