C++ Generic Binary Search Tree

binary-search-tree.cpp

#include <iostream>
#include <new>
#include <cassert>

#define NUMBER 9

template <typename T> class Node {
public:

	Node<T> *parent, *left, *right;
	T data;

	Node() : parent(NULL), left(NULL), right(NULL) {
		parent = NULL;
		left = NULL;
		right = NULL;
	}

	Node(T data) : data(data),  parent(NULL), left(NULL), right(NULL) {
	}

	Node(T data, Node<T> *parent, Node<T> *left, Node<T> *right) :
		data(data), parent(parent), left(left), right(right) {

	}

 	static void walk(const Node<T> *tree);
 	static Node<T> *find(Node<T> *tree, T value);
 	static Node<T> *minimum(Node<T> *tree);
 	static Node<T> *maximum(Node<T> *tree);
 	static Node<T> *successor(Node<T> *tree);

	// Always returns the root of the tree, whether it had to be modified
	// or not
 	static Node<T> *insertNode(Node<T> *tree, Node<T> *node);
 	static Node<T> *deleteNode(Node<T> *tree, Node<T> *node);

private:
 	static Node<T> *transplant(Node<T> *tree, Node<T> *u, Node<T> *v);
};

template<typename T> std::ostream &operator<<(std::ostream &output, Node<T> node);

int main() {
	Node<int> list[NUMBER] = {
		45, 50, 1, 9, 44, 56, 98, 43, 32
	};

	// construct a tree
	Node<int> *root = NULL;

	// We will just use the first tree as the root
	for (int i = 0; i < NUMBER; ++i) {
		root = Node<int>::insertNode(root, (list + i));
	}

	Node<int>::walk(root);

	std::cout << *Node<int>::find(root, 43);
	std::cout << "Minimum: " << *Node<int>::minimum(root);
	std::cout << "Maximum: " << *Node<int>::maximum(root);

	Node<int> *nine = Node<int>::find(root, 9);
	std::cout << "9: " << *nine;
	std::cout << "Successor: " << *Node<int>::successor(nine);

	Node<int> *fortyFour = Node<int>::find(root, 44);
	std::cout << "44: " << *nine;
	std::cout << "Successor: " << *Node<int>::successor(fortyFour);

	root = Node<int>::deleteNode(root, root);
	Node<int>::walk(root);

	return 0;
}

template <typename T> void Node<T>::walk(const Node<T> *tree) {
	if (tree == NULL) return;

	walk(tree -> left);
	std::cout << tree -> data << "\n";
	walk(tree -> right);
}

template <typename T> Node<T> *Node<T>::insertNode(Node<T> *tree, Node<T> *node) {
	if (!tree) {
		tree = node;
		node -> parent = NULL;
	} else {
		Node<T> *parent, *search = tree;
		bool left = false;
		while (search != NULL) {
			parent = search;
			if (node -> data <= search -> data) {
				search = search -> left;
				left = true;
			} else {
				search = search -> right;
				left = false;
			}
		}
		node -> parent = parent;
		if (left) parent -> left = node;
		else parent -> right = node;
	}

	return tree;
}

template <typename T> Node<T> *Node<T>::find(Node<T> *tree, T value) {
	if (!tree || tree -> data == value) return tree;
	if (value < tree -> data) return find(tree -> left, value);
	else return find(tree -> right, value);
}

template <typename T> Node<T> *Node<T>::minimum(Node<T> *tree) {
	if (!tree) return NULL;

	while (tree -> left) {
		tree = tree -> left;
	}

	return tree;
}

template <typename T> Node<T> *Node<T>::maximum(Node<T> *tree) {
	if (!tree) return NULL;

	while (tree -> right) {
		tree = tree -> right;
	}

	return tree;
}

template <typename T> Node<T> *Node<T>::successor(Node<T> *node) {
	if (!node) return NULL;

	if (node -> right) {
		return minimum(node -> right);
	} else {
		// We need to traverse upwards in the tree to find a node where
		// the node is the left child of a parent
		// parent is the successor

		Node<T> *parent = node -> parent;
		while(parent && node != parent -> left) {
			node = parent;
			parent = node -> parent;
		}

		return parent;
	}

}

// make node U's paarent have node v has its child
template <typename T> Node<T> *Node<T>::transplant(Node<T> *tree, Node<T> *u, Node<T> *v) {
	if (!u -> parent) tree = v;
	else if (u -> parent -> left == u) {
		u -> left = v;
	} else if (u -> parent -> right == u) {
		u -> right = v;
	}
	if (v) v -> parent = u -> parent;
	return tree;
}

template <typename T> Node<T> *Node<T>::deleteNode(Node<T> *tree, Node<T> *node) {
	if (!node -> left) {
		tree = transplant(tree, node, node -> right);
	} else if (!node -> right) {
		tree = transplant(tree, node, node -> left);
	} else {
		// Has two children -- successor must be on the right
		Node <int> *successor = minimum(node -> right);
		assert(successor -> left == NULL);
		if (successor != node -> right) {
			tree = transplant(tree, successor, successor -> right);
			successor -> right = node -> right;
			successor -> right -> parent = successor;
		}

		tree = transplant(tree, node, successor);
		successor -> left = node -> left;
		successor -> left -> parent = successor;
	}
	return tree;
}

template<typename T> std::ostream &operator<<(std::ostream &output, Node<T> node) {
	output << "Value: " << node.data;
	if (node.parent) output << " Parent: " << node.parent -> data;
	if (node.left) output << " Left: " << node.left -> data;
	if (node.right) output << " Right: " << node.right -> data;
	output << "\n";
	return output;
}

Nice