Algorithm to delete node from binary search tree, Data Structure & Algorithms

Assignment Help:

Algorithm to Delete Node from Binary Search Tree

To delete a node following possibilities might be arise

Node id a terminal node

Node have only one child

Node having 2 children.

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

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

1. [Find the locations of ITEM and its parent]

Call FINDS (INFO, RIGHT, ROOT, ITEM, LOC, and 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)

Related Discussions:- Algorithm to delete node from binary search tree

The best average behaviour, The best average behaviour is shown by Qui...

The best average behaviour is shown by Quick Sort

#input restricted DEQUE, #why all the 4 operations i.e. insertion n del...

#why all the 4 operations i.e. insertion n deletion from rear end and front end is valid in input restricted DEQUE

SORTING ALGORIthm, the deference between insertion,selection and bubble sor...

the deference between insertion,selection and bubble sort

Determine the class invariants- ruby, Determine the class invariants- Ruby ...

Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's

Red black tree, red black tree construction for 4,5,6,7,8,9

red black tree construction for 4,5,6,7,8,9

Breadth-first search, Breadth-first search starts at a given vertex h, whic...

Breadth-first search starts at a given vertex h, which is at level 0. In the first stage, we go to all the vertices that are at the distance of one edge away. When we go there, we

Illustrate the intervals in mathematics, Illustrate the intervals in mathem...

Illustrate the intervals in mathematics Carrier set of a Range of T is the set of all sets of values v ∈ T such that for some start value s ∈ T and end value e ∈ T, either s ≤

The theta-notation, This notation bounds a function to in constant factors....

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

Define tractable and intractable problems, Define tractable and intractable...

Define tractable and intractable problems Problems that can be solved in polynomial time are known as tractable problems, problems that cannot be solved in polynomial time are

Example of single node with multiple elements, The class Element represents...

The class Element represents a single node that can be part of multiple elements on a hotplate and runs in its own thread. The constructor accepts the initial temperature and a hea

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages