Logo 
Search:

Java Forum

 Ask Question   UnAnswered
Home » Forum » Java       RSS Feeds

Implement a binary search tree using Nodes

  Asked By: Don    Date: Jan 22    Category: Java    Views: 1908
  

for one of my classes i have to implement a binary search tree
using Nodes, where each node has a key value, a reference to the left
child, and a reference to the right child.

The problem i am having is implementing "remove(int key)". this
method takes a key parameter and removes the node in the tree with
that key. It's really difficult because after you find the node and
remove it, you can't have empty nodes, so you have to rearrange the
tree to make it correct.

Share: 

 

2 Answers Found

 
Answer #1    Answered By: Andrew Bryant     Answered On: Jan 22

Tree-Delete (T, x)

if x has no children case 0

then remove x

if x has one child  case 1

then make p[x] point to child

if x has two children case 2

then swap x with its successor

perform case 0 or case 1 to delete it

 
Answer #2    Answered By: Becky Baker     Answered On: Jan 22

Sounds like you need to cross link the left and right children to each
other after deleting (or maybe before),
rather than to the node  you are deleting (which is what they are linked
to before the delete).

 
Didn't find what you were looking for? Find more on Implement a binary search tree using Nodes Or get search suggestion and latest updates.




Tagged: