//////////////////////////////////////////////////////////////////////////////
// bintree.h
// Author: Seree Rakwong
// Date: 10-NOV-10
// Purpose: Binary search tree
#define bintree_h
namespace mstd {
template<class K, class T>
class binarytree {
public:
class binarytree_node {
K key_;
T value_;
binarytree_node *parent_;
binarytree_node *left_;
binarytree_node *right_;
unsigned long left_height_;
unsigned long right_height_;
public:
unsigned long left_height() const { return left_height_; }
unsigned long right_height() const { return right_height_; }
K key() const { return key_; };
K& key() { return key_; };
T value() const { return value_; };
T& value() { return value_; };
binarytree_node *left() const { return left_; }
binarytree_node *&left() { return left_; }
binarytree_node *right() const { return right_; }
binarytree_node *&right() { return right_; }
binarytree_node *parent() const { return parent_; }
binarytree_node *&parent() { return parent_; }
public:
binarytree_node(const K& key, const T& value)
: key_(key),
value_(value),
parent_(0),
left_(0),
right_(0),
left_height_(0),
right_height_(0)
{}
}; // binarytree_node
private:
binarytree_node *root_;
public:
binarytree()
: root_(0)
{}
virtual ~binarytree()
{}
public:
binarytree_node *root() const { return root_; }
// if parent is nil, then add at root
// no need to use recursion method
binarytree_node *add(const K& key, const T& value) {
binarytree_node *node = new binarytree_node(key, value);
if(!node) return 0;
if(!root_) {
root_ = node;
}
else {
binarytree_node *current = root_;
binarytree_node *parent = 0;
while(current) {
parent = current;
if(key > current->key()) {
current = current->right();
}
else {
current = current->left();
}
} // while current
//current = node;
node->parent() = parent;
if(key > parent->key())
parent->right() = node;
else
parent->left() = node;
} // root is not null
return node;
}
// find a node
binarytree_node *find(const K& key, binarytree_node *start = 0) {
binarytree_node *current = (start ? start : root_);
while(current && current->key() != key) {
if(current->key() < key) {
// go to the left child
current = current->left();
}
else if(current->key() > key) {
// go to the right child
current = current->right();
}
}
return current;
}
// remove a node
//TREE-DELETE(T,z)
void remove(binarytree_node *node) {
if(!node) return;
// if left[z] = NIL .OR. right[z] = NIL
// then y <= z
// else y <= TREE-SUCCESSOR(z)
binarytree_node *success = 0;
if(!node->left() || !node->right()) {
success = node;
}
else {
success = successor(node);
}
// if left[y] != NIL
// then x <= left[y]
// else x <= right[y]
binarytree_node *subtree = 0;
if(success->left()) {
subtree = success->left();
}
else {
subtree = success->right();
}
// if x != NIL
// then p[x] <= p[y]
if(subtree)
subtree->parent() = success->parent();
// if p[y] = NIL
// then root[T] <= x
// else
// if y = left[p[y]]
// then left[p[y]] <= x
// else right[p[y]] <= x
if(!success->parent()) {
root_ = subtree;
}
else {
if(success == success->parent()->left()) {
success->parent()->left() = subtree;
}
else {
success->parent()->right() = subtree;
}
}
if(success != node) {
// copy key and value here
node->key() = success->key();
node->value() = success->value();
}
// remove the successor
delete success;
success = 0;
}
// find min
//TREE-MINIMUM(x)
binarytree_node *find_min(binarytree_node *start) {
//while left[x] != NIL do
// x <= left[x]
//return x
binarytree_node *min = start;
if(!min) return 0;
while(min->left())
min = min->left();
return min;
}
// find max
// TREE-MAXIMUM(x)
binarytree_node *find_max(binarytree_node *start) {
binarytree_node *max = start;
if(!max) return 0;
//while right[x] != NIL do
// x <= right[x]
//return x
while(max->right())
max = max->right();
return max;
}
// successor
//TREE-SUCCESSOR(x)
binarytree_node *successor(binarytree_node *at) {
if(!at) return 0;
//if right[x] != NIL
// then return TREE-MINIMUM(right[x])
// else y <= p[x]
// while y != NILL .AND. x != right[y] do
// x <= y
// y <= p[y]
// return y
if(at->right()) {
return find_min(at->right());
}
else {
binarytree_node *success = at->parent();
while(success && at != success->right()) {
at = success;
success = success->parent();
}
return success;
}
return 0;
}
//INORDER-TREE-WALK(x)
void inorder(binarytree_node *node, int height, void (*travelsal_callback)(const K&, const T&, int)) {
if(node) {
inorder(node->left(), height+1, travelsal_callback);
travelsal_callback(node->key(), node->value(), height);
inorder(node->right(), height+1, travelsal_callback);
}
}
//PREORDER-TREE-WALK(x)
void preorder(binarytree_node *node, int height, void (*travelsal_callback)(const K&, const T&, int)) {
if(node) {
travelsal_callback(node->key(), node->value(), height);
preorder(node->left(), height+1, travelsal_callback);
preorder(node->right(), height+1, travelsal_callback);
}
}
//POSTORDER-TREE-WALK(x)
void postorder(binarytree_node *node, int height, void (*travelsal_callback)(const K&, const T&, int)) {
if(node) {
postorder(node->left(), height+1, travelsal_callback);
postorder(node->right(), height+1, travelsal_callback);
travelsal_callback(node->key(), node->value(), height);
}
}
}; // binarytree
}; // namespace mstd
#endif // bintree_h
////////////////////////////////////////////////////////////////////////
// test.cpp
// Author: Seree Rakwong
// Date: 10-NOV-10
// Purpose: Binary search tree
#include <iostream>
using namespace mstd;
using namespace std;
void walk(const int& key, const int& value, int height) {
for(int i=0; i<height; i++) cout << " ";
cout << " [" << key << "]" << endl;
}
int main() {
binarytree<int, int> tree;
tree.add(100, 100);
tree.add(50, 50);
tree.add(150, 150);
tree.add(25, 25);
tree.add(75, 75);
tree.add(130, 130);
tree.add(180, 180);
cout << "in-order travelsal..." << endl;
tree.inorder(tree.root(), 0, walk);
binarytree<int, int>::binarytree_node *node = tree.find(75);
if(node) cout << "found 75" << endl;
else cout << "not found 75" << endl;
tree.add(500, 500);
tree.add(300, 300);
tree.add(140, 140);
cout << "in-order travelsal..." << endl;
tree.inorder(tree.root(), 0, walk);
cout << "root = " << tree.root()->value() << endl;
node = tree.find_min(tree.root());
cout << "min = " << node->value() << endl;
node = tree.find_max(tree.root());
cout << "max = " << node->value() << endl;
node = tree.find(100);
tree.remove(node);
cout << "new root = " << tree.root()->value() << endl;
cout << "in-order travelsal..." << endl;
tree.inorder(tree.root(), 0, walk);
return 0;
}
