Delete operation on binary search tree

  • Thread starter Defennder
  • Start date
  • #1
Defennder
Homework Helper
2,591
5

Main Question or Discussion Point

The following diagram is from the section in my notes titled "Operations on Binary Search Trees". Specifically it explains via pseudocode how to implement a delete function for a BST:

http://img410.imageshack.us/img410/4225/deletetreexz0.jpg [Broken]

What I don't understand in the 2nd box is why "return T.left" is written. I thought the purpose of deleting a tree node in a BST would be to literally delete the object corresponding to the tree node. Instead the pseudocode appears to return the child node of the node to be deleted. Why is this done?
 
Last edited by a moderator:

Answers and Replies

  • #2
rcgldr
Homework Helper
8,627
501
This is not a delete function, and it doesn't include the case where an element has two children. It appears to be a sub-function that should be called by another function that isn't described.
 
Last edited:
  • #3
Defennder
Homework Helper
2,591
5
Thanks for replying, Jeff. I did a search on Google and found the following:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/

It turns out that deleting a BST node entails removing only that node itself and not its child sub-trees as I had thought it would. The child sub-trees of that node-to-be deleted would then be re-allocated in the BST. I've uploaded the portion of my notes which describe this operation in full. But it's strange that there isn't any delete keyword which I had expected, nor is there any pseudo-code which explains that deleting a node would require "re-pointing" the pointers of the parent tree-node of the node-to-be-deleted.
 

Attachments

Last edited by a moderator:

Related Threads for: Delete operation on binary search tree

Replies
5
Views
766
  • Last Post
Replies
1
Views
6K
Replies
7
Views
74K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
5
Views
7K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
1
Views
1K
Top