Deletion of a node from a binary search tree, Data Structure & Algorithms

Assignment Help:

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered.

If the node to be deleted contains no sons, then it might be deleted without further adjustment to the tree.
If the node to be deleted contains only one subtree, then its only son may be moved up to take its space.
The node p to be deleted contain two subtrees, then its inorder successor s have to take its place. The inorder successor could not contain left subtree. Hence, right son of s can be moved up to gain the place of s.

Example: Assume the following cases wherein node 5 have to be deleted.

1. The node to be deleted has no children.

2390_Deletion of a node from a Binary Search Tree.png

3. The node to be deleted contains two children. This case is complicated. The order of the binary tree has to be kept intact.

Related Discussions:- Deletion of a node from a binary search tree

Explain the concept of colouring, Colouring The use of colours in CAD/C...

Colouring The use of colours in CAD/CAM has two main objectives : facilitate creating geometry and display images. Colours can be used in geometric construction. In this case,

What do you understand by structured programming, What do you understand by...

What do you understand by structured programming Structured Programming This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Tree, application of threaded binary treee

application of threaded binary treee

Basic concept of the primitive data structures, Q. Explain the basic concep...

Q. Explain the basic concept of the primitive data structures. Ans. The concept of P r i m i t i ve Data

FOLDING METHOD, 12345 SOLVE BY USING FOLDING METHOD

12345 SOLVE BY USING FOLDING METHOD

Order of efficiency - linear search, Linear search employee an exhaustive m...

Linear search employee an exhaustive method of verified each element in the array against a key value. Whereas a match is found, the search halts. Will sorting the array before uti

Give example of assertion and abstract data type, Give example of assertion...

Give example of assertion and abstract data type For illustration, consider Natural ADT whose carrier set is the set of non-negative integers and whose operations are the usual

Representation of a polynomial with a singly linked list, List areutilized ...

List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4 - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Graph, Multilist Representation of graph

Multilist Representation of graph

Non-recursive implementation of binary tree traversals, As we have seen, as...

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages