944,043 Members | Top Members by Rank

Software Development > C++ > Binary search tree removal
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 19698
  • C++ RSS
Permalink
Nov 18th, 2004
0

Binary search tree removal

Expand Post »
I am having trouble coming up with code for removing a node in a binary search tree. This is what I have so far:

C++ Syntax (Toggle Plain Text)
  1.     void remove(int n)
  2.     {
  3.          node *current=root;
  4.          node *gptr;
  5.         while(current != NULL){
  6.             if(n<current->key){
  7.                 gptr=current;
  8.                 current=current->left;
  9.             }else if(n>current->key){
  10.                 gptr=current;
  11.                 current=current->right;
  12.             }else if(n==current->key){
  13.                 if(gptr->right->key==n){
  14.                 cout<<"1st ==key = "<<gptr->key<<endl;
  15.                 cout<<"1st ==current = "<<current->key<<endl;
  16.                 delete current;
  17.                 gptr->right=NULL;
  18.                 }else if(gptr->left->key==n){
  19.                 cout<<"1st ==key = "<<gptr->key<<endl;
  20.                 cout<<"1st ==current = "<<current->key<<endl;
  21.                 delete current;
  22.                 gptr->left=NULL;
  23.                 }
  24.  
  25.             }
  26.         }
  27.  
  28.     }

The problem I am having is lets say for example I enter
10 8 12 11 15
If I remove the 15 it works fine. When I go back and try to remove the 11 after I remove the fifteen it gives me a segmentation fault. Any help would be appreciated.
Similar Threads
Reputation Points: 10
Solved Threads: 0
Unverified User
skeet123 is offline Offline
20 posts
since Nov 2004
Permalink
Nov 18th, 2004
0

Re: Binary search tree removal

Because gptr->right or gptr->left could be NULL, so when you dereference it, you'll crash.

Do your nodes have a parent node or only left and right child nodes?

You could say if (gptr->right == current) gptr->right = NULL, and that way you don't have to check the key value, just the node pointer.
Reputation Points: 36
Solved Threads: 11
Posting Pro in Training
Chainsaw is offline Offline
436 posts
since Jun 2004
Permalink
Nov 18th, 2004
0

Re: Binary search tree removal

I have a root node.Here is the entire code:

C++ Syntax (Toggle Plain Text)
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. class node
  8. {
  9.   public:
  10.     int key;
  11.     string value;
  12.     node *left;
  13.     node *right;
  14.  
  15.     node(int k, string v)
  16.     {
  17.         key = k;
  18.         value = v;
  19.         left = NULL;
  20.         right = NULL;
  21.     }
  22. };
  23. class bst
  24. {
  25.   private:
  26.     node *root;
  27.  
  28.   public:
  29.    bst()
  30.    {
  31.        root = NULL;
  32.    }
  33.  
  34.     void put(int key, string value)
  35.     {
  36.         node *newp = new node(key,value);
  37.         if(root != NULL)
  38.             put(key, value, root);
  39.         else
  40.         {
  41.             root=newp;
  42.         }
  43.  
  44.     }
  45.     void put(int key, string value, node *tmp)
  46.     {
  47.  node *newp = new node(key,value);
  48.         if(key<tmp->key)
  49.         {
  50.             if(tmp->left != NULL)
  51.                 put(key,value,tmp->left);
  52.             else
  53.             {
  54.                 tmp->left=newp;
  55.             }
  56.         }
  57.         else if(key>tmp->key)
  58.         {
  59.             if(tmp->right != NULL)
  60.                 put(key,value,tmp->right);
  61.             else
  62.             {
  63.                 tmp->right=newp;
  64.             }
  65.         }
  66.  
  67.     }
  68.     string non_recursive_get(int n)
  69.   {
  70.         node *gptr=root;
  71.         while(gptr != NULL){
  72.             if(n<gptr->key){
  73.                 gptr=gptr->left;
  74.             }else if(n>gptr->key){
  75.                 gptr=gptr->right;
  76.             }else if(n==gptr->key){
  77.                 return gptr->value;
  78.             }else{
  79.                 return "no node";
  80.             }
  81.         }
  82.  
  83.     }
  84.     string recursive_get(int n)
  85.     {
  86.         recursive_get(n,root);
  87.         return recursive_get(n,root);
  88.     }
  89.     string recursive_get(int n, node *tmp)
  90.  
  91.     {
  92.         if(tmp!=NULL){
  93.  
  94.             if(n==tmp->key){
  95.                 return tmp->value;
  96.             }
  97.             else if(n<tmp->key){
  98.                 return recursive_get(n,tmp->left);
  99.             }else if(n>tmp->key){
  100.                 return recursive_get(n, tmp->right);
  101.             }
  102.         }else if(tmp==NULL){
  103.             cout<<"NO NODES IN TREE"<<endl;
  104.         }
  105.  
  106.     }
  107.     void remove(int n)
  108.     {
  109.          node *current=root;
  110.          node *gptr;
  111.         while(current != NULL){
  112.             if(n<current->key){
  113.                 gptr=current;
  114.                 current=current->left;
  115.             }else if(n>current->key){
  116.                 gptr=current;
  117.                 current=current->right;
  118.             }else if(n==current->key){
  119.                 if(gptr->right->key==n){
  120.                 cout<<"1st ==key = "<<gptr->key<<endl;
  121.                 cout<<"1st ==current = "<<current->key<<endl;
  122.                 delete current;
  123.                 gptr->right=NULL;
  124.                 }else if(gptr->left->key==n){
  125.                 cout<<"1st ==key = "<<gptr->key<<endl;
  126.                 cout<<"1st ==current = "<<current->key<<endl;
  127.                 delete current;
  128.                 gptr->left=NULL;
  129.                 }
  130.  
  131.             }
  132.         }
  133.  
  134.     }
  135. };
  136.  
  137. int main(void)
  138. {
  139.     bst mybst;
  140.     string cmd;
  141.     int k;
  142.     string v;
  143.  
  144.     while (true) {
  145.         cin >> cmd >> k >> v;
  146.  
  147.         cout << "MAIN: cmd= " << cmd << ", key= " << k << ", v= " << v << endl;
  148.  
  149.         if (cmd == "put") {
  150.             mybst.put(k, v);
  151.         }else if (cmd == "dump") {     // traverse tree in ascending order
  152.             mybst.dump();
  153.         }else if (cmd == "dump_rev") { // traverse tree in descending order
  154.             mybst.dump_rev();
  155.         } else if (cmd == "get") {
  156.             cout << "MAIN: get returns: " << mybst.non_recursive_get(k) << endl;
  157.         } else if (cmd == "rget") {
  158.      cout << "MAIN: rget returns: " << mybst.recursive_get(k) << endl;
  159.         } else if (cmd == "rem") {
  160.             mybst.remove(k);
  161.         } else if (cmd == "quit") {
  162.             exit(0);
  163.         }
  164.     }
  165. }
Reputation Points: 10
Solved Threads: 0
Unverified User
skeet123 is offline Offline
20 posts
since Nov 2004
Permalink
Nov 19th, 2004
0

Re: Binary search tree removal

ok, so you need to fix those pointers at the least. Thanks for the readable code!
Reputation Points: 36
Solved Threads: 11
Posting Pro in Training
Chainsaw is offline Offline
436 posts
since Jun 2004
Permalink
Nov 19th, 2004
0

Re: Binary search tree removal

Quote originally posted by Chainsaw ...
ok, so you need to fix those pointers at the least. Thanks for the readable code!

Thanks for the reply I finally got it to work. Now th problem I am having is tring to remove a node with two children. Any suggestions.
Reputation Points: 10
Solved Threads: 0
Unverified User
skeet123 is offline Offline
20 posts
since Nov 2004
Permalink
Nov 19th, 2004
0

Re: Binary search tree removal

To remove a node with two children you need to find the inorder successor or predecessor to replace it with, then reduce to the case of removing the successor or predecessor. A fairly thorough tutorial on binary search trees can be found here.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: Help: Outputting Up and down arrows in C++
Next Thread in C++ Forum Timeline: Problems With Loops...





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC