Unit 4

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 50

UNIT-4: NON-LINEAR DATA

STRUCTURES - TREES

Trees, tree terminology, binary trees, binary tree travels,


operations on binary trees, binary search trees and its
operations, creation of binary tree from in-order and
pre(post) order traversals, application of binary trees.
A tree is recursively defined as a set of one or more nodes where one node is designated as the
root of the tree and all the remaining nodes can be partitioned into non-empty sets each of
which is a sub-tree of the root.

Tree is a non-linear data structure which organizes


data in hierarchical structure and this is a recursive
definition.
Root node The root node R is the topmost node in the tree. If R = NULL, then it means the tree is empty

In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We can
say that the root node is the origin of the tree data structure. In any tree, there must be only one root
node. We never have multiple root nodes in a tree.
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

PARENT:

In a tree data structure, the node which is a


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

In a tree data structure, nodes which belong


to same Parent are called as SIBLINGS. In
simple words, the nodes with the same
parent are called Sibling nodes

LEAF:

In a tree data structure, the node which does not


have a child is called as LEAF Node. In simple
words, a leaf is a node with no child.
In a tree data structure, the leaf nodes are also
called as External Nodes. External node is also a
node with no child. In a tree, leaf node is also
called as 'Terminal' node.
Internal Nodes:
In a tree data structure, the node which has atleast one child
is called as INTERNAL Node. In simple words, an internal
node is a node with at least one child.
In a tree data structure, nodes other than leaf nodes are
called as Internal Nodes. The root node is also said to be
Internal Node if the tree has more than one node. Internal
nodes are also called as 'Non-Terminal' nodes.

Degree of Tree:

In a tree data structure, the total number of children of a


node is called as DEGREE of that Node. In simple words,
the Degree of a node is total number of children it has. The
highest degree of a node among all the nodes in a tree is
called as 'Degree of Tree'
LEVEL:

In a tree data structure, the root node is said to be at Level 0


and the children of root node are at Level 1 and the children
of the nodes which are at Level 1 will be at Level 2 and so
on... In simple words, in a tree each step from top to bottom is
called as a Level and the Level count starts with '0' and
incremented by one at each level (Step).

HEIGHT:

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'
DEPTH:

In a tree data structure, the total number of egdes from root


node to a particular node is called as DEPTH of that Node. In a
tree, the total number of edges from root node to a leaf node in
the longest path is said to be Depth of the tree. In simple
words, the highest depth of any leaf node in a tree is said to be
depth of that tree. In a tree, depth of the root node is '0'.

PATH:

In a tree data structure, the sequence of Nodes and Edges from


one node to another node is called as PATH between that two
Nodes. Length of a Path is total number of nodes in that
path. In below example the path A - B - E - J has length 4.
SUBTREE:

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.
Tree Representations

A tree data structure can be represented in two methods. Those methods are as follows...
1.List Representation
2.Left Child - Right Sibling Representation
Consider the following tree...
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...
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. 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...
Binary Tree Datastructure

In a normal tree, every node can have any number of children. A


binary tree is a special type of tree data structure in which every
node can have a maximum of 2 children. One is known as a
left child and the other is known as right child.
A tree in which every node can have a maximum of two
children is called Binary Tree.

In a binary tree, every node can have either 0 children or 1 child


or 2 children but not more than 2 children.
Strictly Binary Tree
In a binary tree, every node can have a maximum of two children. But in
strictly binary tree, every node should have exactly two children or none.
That means every internal node must have exactly two children. A strictly
Binary Tree can be defined as follows...

A binary tree in which every node has either two or zero number of
children is called Strictly Binary Tree
Strictly binary tree is also called
Strictly binary tree data structure is used to represent
as Full Binary Tree or Proper
mathematical expressions.
Binary Tree or 2-Tree
Complete Binary Tree- Perfect Binary Tree
In a binary tree, every node can have a maximum of two
children. But in strictly binary tree, every node should have
exactly two children or none and in complete binary tree all the
nodes must have exactly two children and at every level of
complete binary tree there must be 2 level number of nodes. For
example at level 2 there must be 2 2 = 4 nodes and at level 3
there must be 23 = 8 nodes.
A binary tree in which every internal node has exactly two
children and all leaf nodes are at same level is called
Complete Binary Tree.
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.
Binary 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...

Array Representation of Binary Tree

To represent a binary tree of depth 'n' using array representation, we need one dimensional array with a
maximum size of 2n + 1.
Linked List Representation of Binary Tree
Draw the binary tree having the following Draw the memory representation of the binary
memory representation: tree given below.
Given the memory representation of a tree that stores the names of family members, construct the corresponding
tree from the given data.
Sequential representation of binary trees:
• Sequential representation of trees is done using single or one-dimensional
arrays. Though it is the simplest technique for memory representation, it is
inefficient as it requires a lot of memory space.
• A sequential binary tree follows the following rules:
• A one-dimensional array, called TREE, is used to store the elements of
tree.
• The root of the tree will be stored in the first location. That is, TREE[1]
will store the data of the root element.
• The children of a node stored in location K will be stored in locations (2 ×
K) and (2 × K+1).
• The maximum size of the array TREE is given as (2^h –1), where h is the
height of the tree.
• An empty tree or sub-tree is specified using NULL. If TREE[1] = NULL,
then the tree is empty.
Creating a binary tree from a general tree:

The rules for converting a general tree to a binary tree are given below. Note that a general tree is converted
into a binary tree and not a binary search tree.
Rule 1: Root of the binary tree = Root of the general tree
Rule 2: Left child of a node = Leftmost child of the node in the binary tree in the general tree
Rule 3: Right child of a node in the binary tree = Right sibling of the node in the general tree
Now let us build the binary tree.
Step 1: Node A is the root of the general tree, so it will also be the root of the binary tree.
Step 2: Left child of node A is the leftmost child of node A in the general tree and right child of node A
is the right sibling of the node A in the general tree. Since node A has no right sibling in the general
tree, it has no right child in the binary tree.
Step 3: Now process node B. Left child of B is E and its right child is C (right sibling in general tree).
Step 4: Now process node C. Left child of C is F (leftmost child) and its right child is D (right sibling
in general tree).
Step 5: Now process node D. Left child of D is I (leftmost child). There will be no right child of D
because it has no right sibling in the general tree.
Step 6: Now process node I. There will be no left child of I in the binary tree because I has no left
child in the general tree. However, I has a right sibling J, so it will be added as the right child of I.
Step 7: Now process node J. Left child of J is K (leftmost child).
There will be no right child of J because it has no right sibling in the general tree
Step 8: Now process all the unprocessed nodes (E, F, G, H, K) in the same

fashion, so the resultant binary tree can be given as follows .


TRAVERSING A BINARY TREE :
• Traversing a binary tree is the process of visiting each node in the tree exactly once in a systematic way.
• Unlike linear data structures in which the elements are traversed sequentially, tree is a non-linear data structure
in which the elements can be traversed in many different ways.
• There are different algorithms for tree traversals. These algorithms differ in the order in which the nodes are
visited.
Pre-order Traversal
To traverse a non-empty binary tree in pre-order, the following operations are performed recursively at each
node.
• The algorithm works by:
1. Visiting the root node,
2. Traversing the left sub-tree, and finally
3. Traversing the right sub-tree
• Consider the tree as shown in Fig. The pre-order traversal of the tree is given as A, B, C.
Root node first, the left sub-tree next, and then the right sub-tree.
• Pre-order traversal is also called as depth-first traversal. In this algorithm, the left sub-
tree is always traversed before the right sub-tree.
• The word ‘pre’ in the pre-order specifies that the root node is accessed prior to any other
nodes in the left and right sub-trees.
• Pre-order algorithm is also known as the NLR traversal algorithm (Node-Left-Right).
• Pre-order traversal algorithms are used to extract a prefix notation from an expression
+–ab*cd
tree.

%–+ab*cd/^ef–gh
• ^+/ab*cd/%fg–hi
TRAVERSAL ORDER: A, B, D, G, H, L, E, C, F, I, J, and K TRAVERSAL
ORDER: A, B, D, C, E, F, G, H, and I
• In-order Traversal:
• To traverse a non-empty binary tree in in-order, the following operations are performed recursively at each
node. The algorithm works by:
• Traversing the left sub-tree,
• Visiting the root node, and finally
• Traversing the right sub-tree.
• Consider the tree shown in Fig. The in-order traversal of the tree is given as B, A, and C. Left sub-tree first,
the root node next, and then the right sub-tree.
• In-order traversal is also called as symmetric traversal. In this algorithm, the left sub-tree is always traversed
before the root node and the right sub-tree.
• The word ‘in’ in the in-order specifies that the root node is accessed in between the left and the right sub-
trees. In-order algorithm is also known as the LNR traversal algorithm (Left-Node-Right).
• In-order traversal algorithm is usually used to display the elements of a binary search tree.
TRAVERSAL ORDER: G, D, H, L, B, E, A, C, I, F, K, and J
TRAVERSAL ORDER: B, D, A, E, H, G, I, F, and C
Post-order Traversal
To traverse a non-empty binary tree in post-order, the following operations are performed recursively at each node.
The algorithm works by:
1. Traversing the left sub-tree,
2. Traversing the right sub-tree, and finally
3. Visiting the root node.
Consider the tree shown in Fig. The post-order traversal of the tree is given as B, C, and A. Left sub-tree first, the
right sub-tree next, and finally the root node.
In this algorithm, the left sub-tree is always traversed before the right sub-tree and the root node. The word ‘post’
in the post-order specifies that the root node is accessed after the left and the right sub-trees.
Post-order algorithm is also known as the LRN traversal algorithm (Left-Right-Node).
Post-order traversals are used to extract postfix notation from an expression tree.
TRAVERSAL ORDER: G, L, H, D, E, B, I, K, J, F, C, and A
TRAVERSAL ORDER: D, B, H, I, G, F, E, C, and A
Constructing a Binary Tree from Traversal Results:
We can construct a binary tree if we are given at least two traversal results. The first traversal must be the in-order
traversal and the second can be either pre-order or post-order traversal.
The in-order traversal result will be used to determine the left and the right child nodes, and the pre-order/post-
order can be used to determine the root node.
For example, consider the traversal results given below:
In–order Traversal: D B E A F C G
Pre–order Traversal: A B D E C F G
Follow the steps given below to construct the tree:
Step 1 Use the pre-order sequence to determine the root node of the tree. The first element would be the root node.
Step 2 Elements on the left side of the root node in the in-order traversal sequence form the left sub-tree of the root
node. Similarly, elements on the right side of the root node in the in-order traversal sequence form the right sub-
tree of the root node.
Step 3 Recursively select each element from pre-order traversal sequence and create its left and right sub-trees
from the in-order traversal sequence.
Look at Fig. which constructs the tree from its traversal results.

Now consider the in-order traversal and post-order traversal sequences of a given binary tree. Before constructing
the binary tree, remember that in post-order traversal the root node is the last node. Rest of the steps will be the
same as mentioned above Fig.
In–order Traversal: D B H E I A F J C G
Post order Traversal: D H I E B J F G C A
In–order Traversal: D B H E I A F J C G
Post order Traversal: D H I E B J F G C A
APPLICATIONS OF TREES :
• Trees are used to store simple as well as complex data. Here simple means an integer value, character value
and complex data means a structure or a record.
• Trees are often used for implementing other types of data structures like hash tables, sets, and maps.
• A self-balancing tree, Red-black tree is used in kernel scheduling, to preempt massively multi-processor
computer operating system use.
• Another variation of tree, B-trees are prominently used to store tree structures on disc. They are used to index
a large number of records.
• B-trees are also used for secondary indexes in databases, where the index facilitates a select operation to
answer some range criteria.
• Trees are an important data structure used for compiler construction.
• Trees are also used in database design.
• Trees are used in file system directories.
• Trees are also widely used for information storage and retrieval in symbol tables
BINARY SEARCH TREE
a binary search tree is a binary tree with the following properties:
• The left sub-tree of a node N contains values that are less than N’s
value.
• The right sub-tree of a node N contains values that are greater than N’s
value.
• Both the left and the right binary trees also satisfy these properties and,
thus, are binary search trees.

State whether the binary trees in Fig. are binary search trees or not.
Create a binary search tree using the following data elements:
45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81
OPERATIONS ON BINARY SEARCH TREES
Searching for a Node in a Binary Search Tree
• The search function is used to find whether a given value is present in the tree or not. The searching process
begins at the root node.
• The function first checks if the binary search tree is empty. If it is empty, then the value we are searching for
is not present in the tree. So, the search algorithm terminates by displaying an appropriate message.
• However, if there are nodes in the tree, then the search function checks to see if the key value of the current
node is equal to the value to be searched.
• If not, it checks if the value to be searched for is less than the value of the current node, in which case it
should be recursively called on the left child node.
• In case the value is greater than the value of the current node, it should be recursively called on the right
child node.
Searching a node with value 12 in the given binary search tree

Searching a node with value 67 in the given binary search tree


The procedure to find the node with value 40
is shown in Fig.. The search would terminate
after reaching node 39 as it does not have any
right child

Searching a node with the value 40 in the given binary search


In Step 1, we check if the value stored at the
tree
current node of TREE is equal to VAL or if the
Algorithm to search for a given value in a binary search tree
current node is NULL, then we return the current
node of TREE. Otherwise, if the value stored at
the current node is less than VAL, then the
algorithm is recursively called on its right sub-
tree, else the algorithm is called on its left sub-
tree.
Search Operation in BST
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 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.
Insertion Operation
• The initial code for the insert function is similar to the search function. This is because we first find the
correct position where the insertion has to be done and then add the node at that position.
• The insertion function changes the structure of the tree. Therefore, when the insert function is called
recursively, the function should return the new tree pointer.
• In Step 1 of the algorithm, the insert function checks if the current node of TREE is NULL. If it is NULL,
the algorithm simply adds the node, else it looks at the current node’s value and then recurs down the left or
right sub-tree.
• If the current node’s value is less than that of the new node, then the right sub-tree is traversed, else the left
sub-tree is traversed. The insert function continues moving down the levels of a binary tree until it reaches
a leaf node.
• The new node is added by following the rules of the binary search trees. That is, if the new node’s value is
greater than that of the parent node, the new node is inserted in the right sub-tree, else it is inserted in the
left sub-tree.
• The insert function requires time proportional to the height of the tree in the worst case
Inserting nodes with values 12 and 55 in the given binary
search tree
Insertion Operation
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 the 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 steps until we reach to the leaf node (i.e., reaches to NULL).
•Step 7 - After reaching the leaf node, insert the newNode as left child if the newNode is smaller or equal to that
leaf node or else insert it as right child.
Deletion Operation in BST
Deleting a node from Binary search tree includes following three cases...
•Case 1: Deleting a Leaf node (A node with no children)
•Case 2: Deleting a node with one child
•Case 3: Deleting a node with two children
Case 1: Deleting a leaf node
We use the following steps to delete a leaf node from BST...
•Step 1 - Find the node to be deleted using search operation
•Step 2 - Delete the node using free function (If it is a leaf) and terminate the function.
Case 2: Deleting a node with one child
We use the following steps to delete a node with one child from BST...
•Step 1 - Find the node to be deleted using search operation
•Step 2 - If it has only one child then create a link between its parent node and child node.
•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 in the above step.
•Step 4 - Then check whether deleting node came to case 1 or case 2 or else goto step 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 the node is deleted from the tree.
Deleting node 78 from the given binary search tree

Deleting node 54 from the given binary search tree


Deleting node 56 from the given binary search tree

Deleting node 56 from the given binary search tree


• In Step 1 of the algorithm, first check if TREE=NULL,
because if it is true, then the node to be deleted is not present
in the tree. However, if it is false, then check if the value to
be deleted is less than the current node’s data.
• In case the value is less, we call the algorithm recursively on
the node’s left sub-tree, otherwise the algorithm is called
recursively on the node’s right sub-tree.
• Note that if we have found the node whose value is equal to
VAL, then we check which case of deletion it is. If the node
to be deleted has both left and right children, then we find
the in-order predecessor of the node by calling
findLargestNode(TREE -> LEFT) and replace the current
node’s value with that of its in-order predecessor.
• Then, we call Delete(TREE -> LEFT, TEMP -> DATA) to
delete the initial node of the in-order predecessor. Thus, we
reduce the case 3 of deletion into either case 1 or case 2 of
deletion. If the node to be deleted does not have any child,
then we simply set the node to NULL.
• Last but not the least, if the node to be deleted has either a
left or a right child but not both, then the current node is
replaced by its child node and the initial child node is deleted
from the tree.

You might also like