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

Search engines - applications of linear and binary search, Search engines e...

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

Splaying procedure, For splaying, three trees are maintained, the central, ...

For splaying, three trees are maintained, the central, left & right sub trees. At first, the central subtree is the complete tree and left and right subtrees are empty. The target

#, if two relations R and S are joined, then the non matching tuples of bot...

if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

Stacks, Q. Explain w hat are the stacks? How can we use the stacks to chec...

Q. Explain w hat are the stacks? How can we use the stacks to check whether an expression is correctly parentheses or not. For example (()) is well formed but (() or )()( is not w

Breadth first search, While BFS is applied, the vertices of the graph are d...

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

Deletion algorithm for dequeue, Deletion Algorithm for dequeue Step 1:...

Deletion Algorithm for dequeue Step 1: [check for underflow] If front = 0 and rear = 0 Output "underflow" and return Step 2: [delete element at front end] If front

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

Graphs, In this unit, we will describe a data structure called Graph. Actua...

In this unit, we will describe a data structure called Graph. Actually, graph is a general tree along no parent-child relationship. In computer science, Graphs have several applica

Sequential files, Data records are stored in some particular sequence e.g.,...

Data records are stored in some particular sequence e.g., order of arrival value of key field etc. Records of sequential file cannot be randomly accessed i.e., to access the n th

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?

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages