Algorithm to delete the specific node from binary searchtree, Data Structure & Algorithms

Assignment Help:

Q. Write down an algorithm to delete the specific node from binary search tree. Trace the algorithm to delete a node (10) from the following given tree.

1882_binary tree.png

Ans.

Algorithm for Delete ting the specific Node From the Binary Search Tree

To delete the specific node following possibilities may arise

1)      Node id a terminal node

2)      Node have only one child

3)      Node having 2 children.

DEL(INFO, LEFT, RIGT, ROOT, AVAIL, ITEM)

A binary search tree T is in the memory, and an ITEM of information is given as follows.
 This algorithm deletes the specific ITEM from the tree.

1. [to Find the locations of ITEM and its parent] Call FIND(INFO, RIGHT, ROOT, ITEM, LOC, PAR).

2. [ITEM in tree?]

if LOC=NULL, then write : ITEM not in tree, and Exit.

3. [Delete node containing ITEM.]

if RIGHT[LOC] != NULL and LEFT[LOC] !=NULL then:

Call CASEB(INFO,LEFT,RIGHT,ROOT,LOC,PAR). Else:

Call CASEA (INFO,LEFT,RIGHT,ROOT,LOC,PAR).

[End of if structure.]

4. [Return deleted node to AVAIL list.] Set LEFT[LOC]:=AVAIL and AVAIL:=LOC.

5. Exit.

CASEB(INFO,LEFT,RIGHT,ROOT,LOC,PAR)

This procedure will delete the node N at LOC location, where N has two children. The pointer PAR gives us the location of the parent of N, or else PAR=NULL indicates that N is a root node. The pointer SUC gives us the location of the inorder successor of N, and PARSUC gives us the location of the parent of the inorder successor.

1. [Find SUC and PARSUC.]

(a) Set PTR: = RIGHT[LOC] and SAVE:=LOC. (b) Repeat while LEFT[PTR] ≠  NULL:

Set SAVE:=PTR and PTR:=LEFT[PTR]. [End of loop.]

(c) Set SUC : = PTR and PARSUC:=SAVE.

2. [Delete inorder successor]

Call CASEA (INFO, LEFT, RIGHT, ROOT, SUC, PARSUC).

3. [Replace node N by its inorder successor.] (a) If PAR≠NULL, then:

If LOC = LEFT[PAR], then: Set LEFT[PAR]:=SUC.

Else:

Set RIGHT[PAR]: = SUC. [End of If structure.]

Else:

Set ROOT: = SUC. [End of If structure.]

(b) Set LEFT[SUC]:= LEFT [LOC] and

RIGHT[SUC]:=RIGHT[LOC]

4. Return.

CASEA(INFO, LEFT, RIGHT, ROOT, LOC, PAR)

This procedure deletes the node N at LOC location, where N does not contain two children. The pointer PAR gives us the location of the parent of N, or else PAR=NULL indicates that N is a root node. The pointer CHILD gives us the location of the only child of the N, or else CHILD = NULL indicates N has no children.

1. [Initializes CHILD.]

If LEFT[LOC] = NULL and RIGHT[LOC] = NULL, then: Set CHILD:=NULL.

Else if LEFT[LOC]≠NULL, then:

Set CHILD: = LEFT[LOC].

Else

Set CHILD:=RIGHT[LOC] [End of If structue.]

2. If PAR ≠  NULL, then:

If LOC = LEFT [PAR], then:

Set LEFT[PAR]:=CHILD.

Else:

Set RIGHT[PAR]:CHILD = CHILD [End of If structure.]

Else:

Set ROOT : = CHILD.

[End of If structure.]

3. Return.

Inorder traversal of the tree is

4 6 10 11 12 14 15 20

To delete 10

PAR = Parent of 10 ie 15

SUC = inorder succ of 10 ie. 11

PARSUC = Parent of inorder succ ie 12

PTR = RIGHT [LOC]

Address of 12    SAVE: = address of 10

SAVE: = address of 12

PTR = address of 11

SUC = ADDRESS OF 11

PAR SUCC:= ADDRESS OF 12

CHILD = NULL

LEFT [PARSUC] = CHILD= NULL LEFT [PAR]= ADDRESS OF 11

LEFT [SUC] = LEFT [LOC] = ADDRESS OF 6

RIGHT [SUC] = RIGHT[LOC] = ADDRESS OF 12


Related Discussions:- Algorithm to delete the specific node from binary searchtree

Merge sort, #question. merging 4 sorted files containing 50,10,25,15 record...

#question. merging 4 sorted files containing 50,10,25,15 records will take time?

Array, how to define the size of array

how to define the size of array

Find a minimum cost spanning arborescence rooted, Find a minimum cost spann...

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class. Please show your work, and also give a final diagram wh

Conversion of forest into tree, Conversion of Forest into Tree A binary...

Conversion of Forest into Tree A binary tree may be used to show an entire forest, since the next pointer in the root of a tree can be used to point to the next tree of the for

Adjacency matrix, Q. Give the adjacency matrix for the graph drawn below:  ...

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

Representation of records, Records are mapped onto a computer store by simp...

Records are mapped onto a computer store by simply juxtaposing their elements. The address of a component (field) r relative to the origin address of the record r is named the fiel

The time and space complexities of an algorihm, Relation between the time a...

Relation between the time and space complexities of an algorithm The examining of algorithm focuses on time complexity and space complexity. As compared to time analysis, the a

Efficient algorithms.., implementation of fast fourier transforms for non p...

implementation of fast fourier transforms for non power of 2

Binary search tree (bst), Q. Explain what do we understand by Binary Search...

Q. Explain what do we understand by Binary Search Tree (BST)? Make a BST for the following given sequence of the numbers. 45, 32, 90, 21, 78, 65, 87, 132, 90, 96, 41, 74, 92

A full binary tree with 2n+1 nodes, A full binary tree with 2n+1 nodes have...

A full binary tree with 2n+1 nodes have n non-leaf nodes

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd