Basic red-black tree insertion implementation (C++) [NOTE: Missing destructors/delete, therefore causes memory leaks]

red_black_tree_insertion.cpp

#include <iostream>
#include <string>
using namespace std;

typedef bool NodeColor;
const NodeColor RED = false;
const NodeColor BLACK = true;

inline void test(bool expression, string message) {
	cout << message << (expression ? "\tTRUE" : "\tFALSE") << '\n';
}

template<typename T>
struct RedBlackTreeNode {
	RedBlackTreeNode() { left = NULL; right = NULL; parent = NULL; color = RED; }
	RedBlackTreeNode(NodeColor c, T i) : color(c), item(i) { left = NULL; right = NULL; parent = NULL; }
	RedBlackTreeNode(NodeColor c, T i, RedBlackTreeNode* p) : color(c), item(i), parent(p) { left = NULL; right = NULL; } 
	NodeColor color;
	T item;
	RedBlackTreeNode *left, *right, *parent;
	inline RedBlackTreeNode* grandparent() {
		if(parent)
			return parent->parent;
		else
			return NULL;
	}
	inline RedBlackTreeNode* uncle() {
		RedBlackTreeNode* g = grandparent();
		if(g == NULL) {
			// If there is no grandparent, there is no uncle
			return NULL;
		} else if(this->parent == g->left) {
			return g->right;
		} else {
			return g->left;
		}
	}

};

template<typename T>
struct RedBlackTreeNodes {
	RedBlackTreeNode<T> nodes[];
	size_t number_of_nodes;
};

template<typename T>
struct RedBlackTree {
	RedBlackTree() : root(NULL) {}
	void Insert(T item);
	bool VerifyTree() const;
	bool VerifyColors(RedBlackTreeNode<T>* node) const;
	bool VerifyOrder(RedBlackTreeNode<T>* node) const;


	RedBlackTreeNode<T>* root;

};

template<typename T>
void RedBlackTree<T>::Insert(T item) {
	if (root == NULL) {
		root = new RedBlackTreeNode<T>(BLACK, item);
		return;
	} else {
		RedBlackTreeNode<T>* current_node = root;
		while(true) {
			if(item < current_node->item && current_node->left != NULL)
				current_node = current_node->left;
			else if(item >= current_node->item && current_node->right != NULL)
				current_node = current_node->right;
			else
				break;
		}
		RedBlackTreeNode<T>* new_node = new RedBlackTreeNode<T>(RED, item, current_node);
		if(item < current_node->item)
			current_node->left = new_node;
		else
			current_node->right = new_node;
		// If the parent is black then the tree is valid
		// If it's red then we need to move up the tree restoring the red-black property
		// starting with the new node (i.e. remove red-red violations)
		if(current_node->color == BLACK) {
			return;
		} else {
			current_node = new_node;
			while(current_node->parent != NULL) { // Fix up the tree
				// If the parent is black we don't need to check for violations
				// Move up one
				if(current_node->parent->color == BLACK) {
					current_node = current_node->parent;
					continue;
				}
				RedBlackTreeNode<T>* uncle = current_node->uncle();
				if(uncle != NULL && uncle->color == RED) {
					uncle->color = BLACK;
					current_node->parent->color = BLACK;
					current_node->grandparent()->color = RED;
					current_node = current_node->grandparent();
				} else { 
					// If there's a zigzag, a double rotation is necessary, otherwise, single
					/*  

					           G
						     /  \
							P    U
						     \ 
							   C
						  

					*/
					RedBlackTreeNode<T>* p = current_node->parent;
					RedBlackTreeNode<T>* g = current_node->grandparent();

					if(p == g->left) {
						if(current_node == p->right)
							LeftRotate(p);
						current_node = RightRotate(g);
						SwapColors(current_node, current_node->right);
					}
					else {
						if(current_node == p->left)
							RightRotate(p);
						current_node = LeftRotate(g);
						SwapColors(current_node, current_node->left);
					}
				}
			}
			
			root = current_node;
			root->color = BLACK;
		}
	}
}

template<typename T>
RedBlackTreeNode<T>* LeftRotate(RedBlackTreeNode<T>* top_node) {
	cout << "Left rotating...\n";
	// Using the following notation:
	// Root is the parent node of the rotation (e.g. this pointer)
	// Pivot is the node that will become the new parent
	// Based on https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Tree_rotation.html

	// Rotation side = left; opposite side = right

	RedBlackTreeNode<T> *pivot = top_node->right;
	top_node->right = pivot->left;
	pivot->left = top_node;
	
	// Fix parents (see red lines on right side of diagram)
	// New top_node/pivot
	if(top_node->parent != NULL && top_node->parent->left == top_node) {
		top_node->parent->left = pivot;
	}
	else if(top_node->parent != NULL && top_node->parent->right == top_node){
		top_node->parent->right = pivot;
	}
	pivot->parent = top_node->parent;

	// old top_node's parent is pivot
	top_node->parent = pivot;
	// opposite side of old top_node's parent is top_node
	if(top_node->right != NULL)
		top_node->right->parent = top_node;

	// return new top node
	return pivot;
}

template<typename T>
RedBlackTreeNode<T>* RightRotate(RedBlackTreeNode<T>* top_node) {
	cout << "Right rotating...\n";
	// Same as above but with swapped sides
	
	RedBlackTreeNode<T> *pivot = top_node->left;
	top_node->left = pivot->right;
	pivot->right = top_node;
	
	
	if(top_node->parent != NULL && top_node->parent->left == top_node) {
		top_node->parent->left = pivot;
	}
	else if(top_node->parent != NULL && top_node->parent->right == top_node){
		top_node->parent->right = pivot;
	}
	pivot->parent = top_node->parent;
	top_node->parent = pivot;
	if(top_node->left != NULL)
		top_node->left->parent = top_node;
	
	// return new top node
	return pivot;

}

template<typename T>
inline void SwapColors(RedBlackTreeNode<T>* a, RedBlackTreeNode<T>* b) {
	cout << "Swapping colours.\n";
	NodeColor temp = a->color;
	a->color = b->color;
	b->color = temp;
}

template<typename T>
bool RedBlackTree<T>::VerifyTree() const {
	// If tree has no root, then return as valid
	if(!root)
		return true;

	// If root is red, it's invalid
	if(root->color == RED)
		return false;

	// Every red node has two black child nodes (or NULL)
	if(VerifyColors(root) == false)
		return false;

	// Verify that the nodes are in-order correctly by number
	if(VerifyOrder(root) == false)
		return false;

	return true;
}

template<typename T>
bool RedBlackTree<T>::VerifyColors(RedBlackTreeNode<T>* node) const {
	// Base case
	if(!node)
		return true;

	// Make sure if the node is red, there are no red child nodes
	if(node->color == RED
		&& (
		(node->left && node->left->color == RED) // If left is red 
		|| (node->right && node->right->color == RED) // Or if right is red
		)) {
			return false;

	}		

	return VerifyColors(node->left) && VerifyColors(node->right);
}

template<typename T>
bool RedBlackTree<T>::VerifyOrder(RedBlackTreeNode<T>* node) const {
	// Base case
	if(!node)
		return true;

	if(node->left && node->left->item >= node->item) {
		return false;
	}

	if(node->right && node->right->item < node->item) {
		return false;
	}

	return VerifyOrder(node->left) && VerifyOrder(node->right);
}



int main() {
	RedBlackTree<int> rbt;
	rbt.Insert(15);
	test(rbt.root->item == 15 && rbt.root->color == BLACK, "Root node is 15 and black in colour.");
	rbt.Insert(45);
	test(rbt.root->right->item == 45 && rbt.root->right->color == RED, "45 in correct position and colour.");
	rbt.Insert(29);
	test(rbt.root->left->item == 15 && rbt.root->left->color == RED, "15 in correct position and colour.");
	test(rbt.root->right->item == 45 && rbt.root->right->color == RED, "45 in correct position and colour.");
	test(rbt.root->item == 29 && rbt.root->color == BLACK, "29 in correct position and colour.");
	rbt.Insert(10);
	test(rbt.root->left->item == 15 && rbt.root->left->color == BLACK, "15 in correct position and colour.");
	test(rbt.root->right->item == 45 && rbt.root->right->color == BLACK, "45 in correct position and colour.");
	test(rbt.root->item == 29 && rbt.root->color == BLACK, "29 in correct position and colour.");
	test(rbt.root->left->left->item == 10 && rbt.root->left->left->color == RED, "10 in correct position and colour.");
	rbt.Insert(5);
	test(rbt.root->left->right->item == 15 && rbt.root->left->right->color == RED, "15 in correct position and colour.");
	test(rbt.root->right->item == 45 && rbt.root->right->color == BLACK, "45 in correct position and colour.");
	test(rbt.root->item == 29 && rbt.root->color == BLACK, "29 in correct position and colour.");
	test(rbt.root->left->item == 10 && rbt.root->left->color == BLACK, "10 in correct position and colour.");
	test(rbt.root->left->left->item == 5 && rbt.root->left->left->color == RED, "15 in correct position and colour.");
	
	if(rbt.VerifyTree()) {
		cout << "Red black tree satisifies properties.\n";
	} else {
		cout << "Red black tree is broken!!!\n";
	}

	rbt.Insert(3);
	rbt.Insert(81);
	rbt.Insert(61);
	rbt.Insert(41);

	if(rbt.VerifyTree()) {
		cout << "Red black tree satisifies properties.\n";
	} else {
		cout << "Red black tree is broken!!!\n";
	}

	return 0;
}