Page 237 - DCAP407_DATA_STRUCTURE

Data Structure

(a) SEARCH_SEQ (2*i, KEY) //Search in left sub-tree
2. Else //Left sub-tree is exhausted and KEY not found
(a) If(2*i + 1 ≤ SIZE)then //If right sub-tree is not exhausted
1. SEARCH_SEQ (2*i + 1, KEY) //Search in right sub-tree

(b) Else //KEY is found neither in left or right sub-tree
1. Return(0) //Return NULL address for unsuccessful search
(c) EndIf
EndIf
3. Else
(d) Return(i) //Return address where KEY is found
4. Stop
12.5.2 Deletion

Deletion operation is used to delete a node from a non-empty binary tree. To delete a node in the binary
tree, it is important to visit the parent node of the node to be deleted. Deletion operation can be done on
a sequential representation as well as linked representation of binary tree. Let us discuss the deletion
operation on sequential representation of binary tree.
In the deletion operation, the parent node of the deleting node must be traversed initially.

The algorithm for deletion operation is as follows:
Input – ITEM is the data of a node with which the node is identified for deletion.
Output – Binary tree containing a node without data as ITEM.
Data structure – Array A is for storing binary tree. SIZE indicates size of array A.
Steps
1. Flag = FALSE //Start from root node
2. L = SEARCH_SEQ (1, KEY) //Start searching from starting
3. If (A[2 * L] = NULL) and (A[2 * L +1]=NULL) //Test for leaf node

(a) flag = TRUE // If leaf node is present, then delete it
(b) A[L] = NULL
4. Else
(a) Print “The node containing ITEM is not a leaf node”
5. EndIf
6. If (flag = FALSE)

(a) Print “NODE does not exist :No deletion”
7. EndIf
8. Stop
12.5.3 Searching
Searching operation is a part of insertion and deletion operation. It is a basic step to be performed
before inserting or deleting a node in the binary tree. In the insertion operation, the location for the new
node to be inserted must be identified whereas, in the deletion operation, searching of the parent node
of the deleting node is required. The algorithm of searching operation for inserting a node has been
explained in the section 12.5.1.

230 LOVELY PROFESSIONAL UNIVERSITY