A quick and dirty BST implementation
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; }