C++ RSS C++ RSS

Binary search tree removal

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Nov 2004
Posts: 20
Reputation: skeet123 is an unknown quantity at this point 
Solved Threads: 0
skeet123 skeet123 is offline Offline
Newbie Poster

Binary search tree removal

 
0
  #1
Nov 18th, 2004
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 436
Reputation: Chainsaw is an unknown quantity at this point 
Solved Threads: 10
Chainsaw's Avatar
Chainsaw Chainsaw is offline Offline
Unprevaricator

Re: Binary search tree removal

 
0
  #2
Nov 18th, 2004
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2004
Posts: 20
Reputation: skeet123 is an unknown quantity at this point 
Solved Threads: 0
skeet123 skeet123 is offline Offline
Newbie Poster

Re: Binary search tree removal

 
0
  #3
Nov 18th, 2004
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. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 436
Reputation: Chainsaw is an unknown quantity at this point 
Solved Threads: 10
Chainsaw's Avatar
Chainsaw Chainsaw is offline Offline
Unprevaricator

Re: Binary search tree removal

 
0
  #4
Nov 19th, 2004
ok, so you need to fix those pointers at the least. Thanks for the readable code!
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2004
Posts: 20
Reputation: skeet123 is an unknown quantity at this point 
Solved Threads: 0
skeet123 skeet123 is offline Offline
Newbie Poster

Re: Binary search tree removal

 
0
  #5
Nov 19th, 2004
•
•
•
•
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 7,615
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 713
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Binary search tree removal

 
0
  #6
Nov 19th, 2004
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.
I'm here to prove you wrong.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array based binary bitmap c++ c/c++ calculator char char* class classes code coding compile console conversion count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp iamthwee ifstream input int java lib linkedlist linker linux list loop looping loops map math matrix memory multiple news node number numbertoword output pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings temperature template templates test text text-file tree unix url variable vector video visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC