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

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

Dataset for dmi, The following DNA sequences are extracted from promoter re...

The following DNA sequences are extracted from promoter region of genes which are co-regulated by the same transcription factor (TF). The nucleotide segments capitalized in the giv

Explain insertion sort, Q. Explain the insertion sort with a proper algorit...

Q. Explain the insertion sort with a proper algorithm. What is the complication of insertion sort in the worst case?

Illustrate the operations of the symbol abstract data type, The operations ...

The operations of the Symbol ADT The operations of the Symbol ADT are the following. a==b-returns true if and only if symbols a and bare identical. a symbol bin Unico

#binary search, Ask question #Minima binary search tree is used to locate t...

Ask question #Minima binary search tree is used to locate the number 43 which of the following probe sequences are possible and which are not? explainum 100 words accepted#

Insertion of a key into a b-tree, Example: Insertion of a key 33 into a B-...

Example: Insertion of a key 33 into a B-Tree (w/split) Step 1: Search first node for key closet to 33. Key 30 was determined. Step 2: Node pointed through key 30, is se

Algo for quicksort, Easy algorithm for beginner for quicksort with explanat...

Easy algorithm for beginner for quicksort with explanation

Representation of data structure in memory, Representation of data structur...

Representation of data structure in memory is known as: Abstract data type

Array, how to define the size of array

how to define the size of array

Comp. sci algorithms, 1. develop an algorithm which reads two decimal numbe...

1. develop an algorithm which reads two decimal numbers x and y and determines and prints out wether x>y or y>x. the input values, x and y, are whole number > or equal to 0, which

What is a container taxonomy, What is A Container Taxonomy It's useful ...

What is A Container Taxonomy It's useful to place containers in a taxonomy to help understand their relationships to one another and as a basis for implementation using a class

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages