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

Characteristics of good algorithms, What do we mean by algorithm? What are ...

What do we mean by algorithm? What are the characteristics of a good and relevant algorithm? An algorithm is "a step-by-step procedure for finishing some task'' An algorithm c

Procedures, what is far and near procedures in system programming?

what is far and near procedures in system programming?

Algorithms and flowcharts, write an algorithm and draw a flowchart to calcu...

write an algorithm and draw a flowchart to calculate the perimeter and area of a circle

Algorithm to merge two sorted arrays with third array, Q. Write down an alg...

Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

Pre-order and post order traversal of a binary tree, The pre-order and post...

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum One node

Dgsd, Ask question #sdgsdgsdginimum 100 words accepted#

Ask question #sdgsdgsdginimum 100 words accepted#

Methods of collision resolution, Methods of Collision Resolution 1)  Co...

Methods of Collision Resolution 1)  Collision Resolution by separate chaining  2)  Collision Resolution by open addressing

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

Recurrence relation, solve the following relation by recursive method: T(n...

solve the following relation by recursive method: T(n)=2T(n^1/2)+log n

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

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