CODEWITHSUNDEEP
c++binary-search-tree
WriteBackCMO
WriteBackCMO

Reputation: 619

delete a node in BST

I am trying to implement the deletion of BST. The algorithm i am using is:

  1. if the search matches one node

1.1. if there is left child node, swap the value of this node and its left child node. And call the function of the left node again.

1.2. else if there is no left node but there is right node, swap the value of the node and the right node. call the function of the right node.

1.3. if there is no left nor right node, delete this node.

the below is the class definition.

class node{
  public:
  int value;
  node *left;
  node *right;
  node(){value=0; left=0; right =0;}
  node(int value){this -> value = value; left=0;right=0;}
  void print();
};

class tree{
  public:
  node *root;
  tree(){
    root = 0;
  }
  ~tree(){}
  void remove(node *, int);
  //tree(int value){root = &node(value);}
  void insert(int);
  void printSorted(node *);
  void printAll(node *);
};

print() function to print out i am ..., my left child is ..., my right child is ...

void node::print(){
  if(this == 0) return;
  cout<<"i am "<<value<<endl;
  if(left !=0){
    cout<<"i have left, left is "<<left -> value<<endl;
  }
  if(right !=0){
    cout<<"i have right, right is "<<right -> value <<endl;
  }
}

printAll() function, traverse from the root and print in order.

void tree::printAll(node *nodeP){
  if(nodeP == 0) return;
  else{
    node *iter = nodeP;
    if(iter -> left !=0){
      printAll(iter->left);
    }
    iter->print();
    cout<<endl;
    if(iter -> right !=0){
        printAll(iter -> right);
    }
  }
}

This is the remove function.

void tree::remove(node* origin, int toDel){
  if(origin == 0) return;
  node *orig_origin = origin;
  int tmp;
  if(origin -> value == toDel){
    if((origin -> left == 0) && (origin -> right == 0)){
      delete origin;
      origin =0;
    }
    else if((origin -> left != 0) && (origin -> right == 0)){
      tmp = origin -> value;
      origin -> value = origin -> left -> value;
      origin -> left -> value = tmp;
      remove(origin -> left, toDel);
    }
    else if((origin -> left == 0) && (origin -> right != 0)){
      tmp = origin -> value;
      origin -> value = origin -> right -> value;
      origin -> right -> value = tmp;
      remove(origin -> right, toDel);
    }
    else{ 
      tmp = origin -> value;
      origin -> value = origin -> left -> value;
      origin -> left -> value = tmp;
      remove(origin -> left, toDel);
    }
  }
  else{
    if(origin -> value > toDel) remove(origin -> left, toDel);
    else remove(origin -> right, toDel);
  }
  origin = orig_origin;
}

I input 7 4 10 1 6 5 after calling delete, 1 is in original 4's position. But there is left child of 0. So somehow i failed to delete the original 1 node.

sc-xterm-24:~/scratch/code/cpp_primer> ./a.out 
7 4 10 1 6 5 
i am 0

i am 1
i have left, left is 0
i have right, right is 6

i am 5

i am 6
i have left, left is 5

i am 7
i have left, left is 1
i have right, right is 10

i am 10

Upvotes: 0

Views: 740

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

When you've found the value in the tree, the handling of the last case (where there is both a left and right branch) is wrong. You can't swap the origin->value and origin->left->value since that breaks the ordering the tree requires. Since the original origin->value is greater than all values stored in the left subtree, the new origin->left->value will be greater than all the values stored in the origin->left->right subtree. Since the value in a node should be less then everything stored in the right tree, future searches along that branch can fail or find the wrong node.

Upvotes: 0

Related Questions