Click here to Skip to main content
11,647,170 members (70,050 online)
Click here to Skip to main content
Add your own
alternative version

Fast Binary Tree Operations

, 22 Jan 2005 203.7K 5.1K 103
Describes main binary tree operations.
binarytree_demo.zip
BinaryTreeDemo.exe
binarytree_src.zip
BinaryTreeDemo.dsp
Sample
BinaryTreeDemo.clw
res
BinaryTreeDemo.ico
icon1.ico
icon2.ico
BinaryTreeDemo.dsw
// RBTree.h:		interface for the CRBTree template.
// Inventor Name:	Hatem Mostafa
// Created:			4/1/2005
//
//////////////////////////////////////////////////////////////////////
// Red/Black Tree is a binary trees with the following properties:
// 1- Every node is either red or black
// 2- Every leaf (nil) is black
// 3- If a node is red, then both its children are black
// 4- Every simple path from a node to a descendant leaf contains the same number of black nodes

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "BinaryTree.h"

#define RBTREENODE CRBTreeNode<KEY, DATA>
#define Red		false
#define Black	true
#define GetColor(x) ((RBTREENODE*)x)->Color
#define SetColor(x, c) ((RBTREENODE*)x)->Color = c
#define IsBlack(x) GetColor(x) == Black
#define IsRed(x) GetColor(x) == Red

template <class KEY, class DATA> class CRBTreeNode : public CBinaryTreeNode<KEY, DATA>
{
public:
	CRBTreeNode():CBinaryTreeNode<KEY, DATA>()
	{
		Color = Black;
	}
public:
	// red black flag
	bool Color;
};

template <class KEY, class ARG_KEY, class DATA, class ARG_DATA> class CRBTree : public CBinaryTree<KEY, ARG_KEY, DATA, ARG_DATA>
{
public:
	CRBTree():CBinaryTree<KEY, ARG_KEY, DATA, ARG_DATA>()
	{
		Root = Nil = NewNode();
	}
	~CRBTree()
	{
		delete Nil;
	}

public:
	//     |                       |
	//     y     RightRotate       x
	//	  / \      ---->          / \
	//   x   c	   <----         a   y
	//  / \	      LeftRotate        / \
	// a   b                       b   c
	void LeftRotate(TREENODE* x)
	{
		TREENODE* y = x->RIGHT;
		x->RIGHT = y->LEFT;
		if(y->LEFT != Nil)
			y->LEFT->Parent = x;
		y->Parent = x->Parent;
		if(x->Parent == Nil)
			Root = y;
		else
			x->Parent->Childs[x == x->Parent->RIGHT] = y;
		y->LEFT = x;
		x->Parent = y;
	}

	void RightRotate(TREENODE* y)
	{
		TREENODE* x = y->LEFT;
		y->LEFT = x->RIGHT;
		if(x->RIGHT != Nil)
			x->RIGHT->Parent = y;
		x->Parent = y->Parent;
		if(y->Parent == Nil)
			Root = x;
		else
			y->Parent->Childs[y == y->Parent->RIGHT] = x;
		x->RIGHT = y;
		y->Parent = x;
	}
	// to kep the tree balanced use RBInsert
	inline TREENODE* Insert(ARG_KEY key, int nID = -1, TREENODE* node = NULL)
	{
		node = CBinaryTree<KEY, ARG_KEY, DATA, ARG_DATA>::Insert(key, nID, node);
		if(node->Count > 1)
			return node;
		TREENODE* x = node, *y;
		SetColor(x, Red);
		while(x != Root && IsRed(x->Parent))
		{
			bool bRIGHT = x->Parent == x->Parent->Parent->LEFT;
			y = x->Parent->Parent->Childs[bRIGHT];
			if(IsRed(y))
			{
				SetColor(x->Parent, Black);
				SetColor(y, Black);
				SetColor(x->Parent->Parent, Red);
				x = x->Parent->Parent;
			}
			else
			{
				if(x == x->Parent->Childs[bRIGHT])
				{
					x = x->Parent;
					bRIGHT ? LeftRotate(x) : RightRotate(x);
				}
				SetColor(x->Parent, Black);
				SetColor(x->Parent->Parent, Red);
				bRIGHT ? RightRotate(x->Parent->Parent) : LeftRotate(x->Parent->Parent);
			}				
		}
		SetColor(Root, Black);
		return node;
	}

	void Delete(TREENODE* node)
	{	
		TREENODE *pSpliced = (node->LEFT == Nil || node->RIGHT == Nil)?node:Successor(node);
		TREENODE *pChild = pSpliced->Childs[pSpliced->LEFT == Nil];
		// connect child to spliced node parent
		pChild->Parent = pSpliced->Parent;
		// connect spliced node parent to child
		if(pSpliced->Parent == Nil)
			Root = pChild;
		else
			pSpliced->Parent->Childs[pSpliced != pSpliced->Parent->LEFT] = pChild;
		if(IsBlack(pSpliced))
			DeleteFixUp(pChild);
		// put spliced node in place of node (if required)
		if(pSpliced != node)
		{	// copy spliced node
			*node = *pSpliced;
			// delete the spliced node
			delete pSpliced;
		}
		else
			// delete the node
			delete node;
		Count--;
	}
protected:
	void DeleteFixUp(TREENODE* x)
	{
		TREENODE* w;
		while (x != Root && IsBlack(x))
		{
			bool bRIGHT = x == x->Parent->LEFT;
			w = x->Parent->Childs[bRIGHT];
			if(IsRed(w))
			{
				SetColor(w, Black);
				SetColor(x->Parent, Red);
				bRIGHT ? LeftRotate(x->Parent) : RightRotate(x->Parent);
				w = x->Parent->Childs[bRIGHT];
			}
			if(IsBlack(w->Childs[!bRIGHT]) && IsBlack(w->Childs[bRIGHT]))
			{
				SetColor(w, Red);
				x = x->Parent;
			}
			else	
			{
				if (IsBlack(w->Childs[bRIGHT]))
				{
					SetColor(w->Childs[!bRIGHT], Black);
					SetColor(w, Red);
					bRIGHT ? RightRotate(w) : LeftRotate(w);
					w = x->Parent->Childs[bRIGHT];
				}
				SetColor(w, GetColor(x->Parent));
				SetColor(x->Parent, Black);
				SetColor(w->Childs[bRIGHT], Black);
				bRIGHT ? LeftRotate(x->Parent) : RightRotate(x->Parent);
				x = Root;
			}
		}
		SetColor(x, Black);
	}
	virtual TREENODE* NewNode()
	{
		RBTREENODE *node = new RBTREENODE();
		node->Parent = node->LEFT = node->RIGHT = Nil;
		return node;
	}
};

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author


You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150804.2 | Last Updated 23 Jan 2005
Article Copyright 2004 by Hatem Mostafa
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid