«
»

A quick and dirty BST implementation

March 18, 2012, 2:55 pm

Another quick and dirty algorithm implementation in C++. This time a Binary search tree (no balancing):


#include <iostream>
#include <vector>

using namespace std;

class Node {

public:

  int value;

  Node *less;
  Node *more;
};

class BinarySearchTree {

public:

  BinarySearchTree() : root(NULL) {}

  void find_node(int value,Node **findnode,Node **parent) {

    *findnode = NULL;
    *parent   = NULL;

    if(root == NULL) {
      return;
    }

    Node *current = root;
    for(;;) {
      if(current->value == value) {*findnode = current; return;}

      if(value < current->value) {
        if(current->less != NULL) {*parent = current; current = current->less;}
        else {
          return;
        }
      } else {
        if(current->more != NULL) {*parent = current; current = current->more;}
        else {
          return;
        }
      }
    }
  }
 
  Node *getr(Node *c,Node **parent) {
    *parent = c;
    for(;c->more != NULL;) {
      *parent = c;
      c = c->more;
    }
    return c;
  }

  void remove(int value) {
  
    Node *delnode;
    Node *parent;

    find_node(value,&delnode,&parent);

    if(delnode == NULL) return;

    // leaf
    if((delnode->less == NULL) && (delnode->more == NULL)) {
      if(parent->less == delnode) {parent->less = NULL;}
      if(parent->more == delnode) {parent->more = NULL;}
      delete delnode;
      return;
    }

    // only one child
    if((delnode->less == NULL) || (delnode->more == NULL)) {
      if(delnode->less != NULL) {
        if(parent->less == delnode) {parent->less = delnode->less;}
        if(parent->more == delnode) {parent->more = delnode->less;}
        delete delnode; 
        return;
      }

      if(delnode->more != NULL) {
        if(parent->less == delnode) {parent->less = delnode->more;}
        if(parent->more == delnode) {parent->more = delnode->more;}
        delete delnode;
        return;
      }
    }

    // two children
    Node *i = getr(delnode->less,&parent);

    delnode->value = i->value;
    if(parent == i)       { delnode->less = NULL;}
    if(parent->less == i) { parent->less = NULL; }
                     else { parent->more = NULL; }
    delete i;
  }

  void insert(int value) {

    if(root == NULL) {
      Node *n = new Node();
      n->value = value;
      n->less = NULL;
      n->more = NULL;
      root = n;

      return;
    }

    Node *current = root;
    for(;;) {
      if(value < current->value) {
        if(current->less != NULL) current = current->less;
        else {
          Node *n = new Node();
          n->value = value;
          n->less = NULL;
          n->more = NULL;
          current->less = n;
          break;
        }
      } else {
        if(current->more != NULL) current = current->more;
        else {
          Node *n = new Node();
          n->value = value;
          n->less = NULL;
          n->more = NULL;
          current->more = n;
          break;
        }
      }
    }
  }

  bool exists(int value) {
    if(root == NULL) {
      return false;
    }

    Node *current = root;
    for(;;) {
      if(current->value == value) return true;

      if(value < current->value) {
        if(current->less != NULL) current = current->less;
        else {
          return false;
        }
      } else {
        if(current->more != NULL) current = current->more;
        else {
          return false;
        }
      }
    }
  }

  Node *root;
};

int main() {

  BinarySearchTree s;

  vector<int> testdata;

  for(size_t n=0;n<10;n++) { testdata.push_back(rand()%20); }

  for(size_t n=0;n<10;n++) { s.insert(testdata[n]); }

  cout << "testdata: " << endl;
  for(size_t n=0;n<10;n++) { cout << testdata[n] << endl; }

  cout << "existance check: " << endl;
  for(size_t n=0;n<10;n++) { if(s.exists(testdata[n])) cout << "existance: " << testdata[n] << " true" << endl; else cout << "existance: " << testdata[n] << " false" << endl;}
  for(size_t n=0;n<10;n++) { if(s.exists(testdata[n]+20)) cout << "existance: " << testdata[n]+20 << " true" << endl; else cout << "existance: " << testdata[n]+20 << " false" << endl;}

  cout << "remove: " << testdata[5] << endl;
  s.remove(testdata[5]);
  if(s.exists(testdata[5])) cout << testdata[5] << " still exists" << endl; else cout << testdata[5] << " no longer exists" << endl;

  cout << "remove: " << testdata[3] << endl;
  s.remove(testdata[3]);
  if(s.exists(testdata[3])) cout << testdata[3] << " still exists" << endl; else cout << testdata[3] << " no longer exists" << endl;

  cout << "remove: " << testdata[0] << endl;
  s.remove(testdata[0]);
  if(s.exists(testdata[0])) cout << testdata[0] << " still exists" << endl; else cout << testdata[0] << " no longer exists" << endl;
}
Category: Uncategorized  |  Comment (RSS)  |  Trackback

Leave a Reply