rbtree.c

红黑树和二叉查找树数据结构的实现以及二者的性能比较的C语言实现代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "rbTree.h"

static int rbCount;

enum NODECOLOR
{
    BLACK = 0 ,
    RED = 1
};

struct rbTreeNode
{
    rbTreeNode parent;
    rbTreeNode left;
    rbTreeNode right;
    rbKEY rbkey;
    NODECOLOR color;
	int size;
};

struct rbTree
{
	rbTreeNode root;
	rbTreeNode nil;
};

 // all leafs are sentinels  
#define SENTINEL &sentinel   
static struct rbTreeNode sentinel = { 0, SENTINEL, SENTINEL, 0, BLACK, 0};



rbTree RB_NewTree()
{
	rbTree T;
    if (NULL == (T = (rbTree)malloc(sizeof(*T))))
    {
        printf("Memory alloc error\n");
        return NULL;
    }
    T->root = SENTINEL;
	T->nil = SENTINEL;
	return T;

}



void Left_Rotate(rbTree T, rbTreeNode x)
{ 
    rbTreeNode y;
    y = x->right;
    if (T->nil == y)
        return;
    x->right = y->left;
    if (T->nil != y->left)
        y->left->parent = x;
	if (T->nil !=y)
		y->parent = x->parent;
    if (x->parent == T->nil)
    {
        T->root = y;
    }
    else if (x == x->parent->left)
    {
        x->parent->left = y;
    }
    else
    {
        x->parent->right = y;
    }
    y->left = x;
	if (x != T->nil)
		x->parent = y;
	y->size = x->size;
	x->size = (x->left->size) + (x->right->size) +1;
}



void Right_Rotate(rbTree T, rbTreeNode x)
{
	rbTreeNode y;
    y = x->left;
	if (T->nil == y)
        return;
	x->left = y->right;
    if (T->nil != y->right)
        y->right->parent = x;
	if (T->nil != y)
		y->parent = x->parent;
	if (x->parent == T->nil)
    {
        T->root = y;
    }
    else if (x == x->parent->left)
    {
        x->parent->left = y;
    }
    else
    {
        x->parent->right = y;
    }
	if (x != T->nil)
		x->parent = y;
    y->right = x;
	y->size = x->size;
	x->size = (x->left->size) + (x->right->size) +1;
}


rbTreeNode RB_Search(rbTreeNode x, rbKEY rbkey)
{
    if (x == SENTINEL || rbkey == x->rbkey)
		return x;
	if (rbkey < x->rbkey)
		return RB_Search(x->left, rbkey);
	else
		return RB_Search(x->right, rbkey);
}


rbTreeNode RB_Search_Iterative(rbTreeNode x, rbKEY rbkey)
{
	while (x != SENTINEL && rbkey != x->rbkey)
	{
		if (rbkey < x->rbkey)
			x = x->left;
		else
			x = x->right;
	}
	return x;
}


rbTreeNode RB_SearchInTree(rbTree T, rbKEY key)
{
	rbTreeNode n;
    n = RB_Search(T->root, key);
	if (T->nil != n)
		return n;
	else
		return NULL;
}
rbTreeNode RB_Search_IterativeInTree(rbTree T, rbKEY key)
{
	rbTreeNode n;
    n = RB_Search_Iterative(T->root, key);
	if (T->nil != n)
		return n;
	else
		return NULL;
}


rbTreeNode RB_Minimum(rbTreeNode x)
{
	while (x->left != SENTINEL)
		x = x->left;
	return x;
}
rbTreeNode RB_Maximum(rbTreeNode x)
{
	while (x->right != SENTINEL)
		x = x->right;
	return x;
}
rbTreeNode RB_Successor(rbTreeNode x)
{
	rbTreeNode y;
	if (x->right != SENTINEL)
		return RB_Minimum(x->right);
	y = x->parent;
	while (y !=SENTINEL && x == y->right)
	{
		x = y;
		y = y->parent;
	}
	return y;
}


rbTreeNode RB_Predecessor(rbTreeNode x)
{
	rbTreeNode y;
	if (x->left != SENTINEL)
		return RB_Maximum(x->left);
	y = x->parent;
	while (y != SENTINEL && x == y->left)
	{
		x = y;
		y = y->parent;
	}
	return y;
}



rbTree RB_Insert(rbTree T, rbKEY rbkey)
{
	rbTreeNode x, y;
    rbTreeNode z;
    x = T->root, y = T->nil;
    /*while (T->nil != x)
    {
		if (rbkey == x->rbkey)
		{
			printf("The rbkey %d is already in the tree!\n",rbkey);
			return T;
		}
        y = x;
		x = (rbkey<x->rbkey) ? 
			x->left : x->right;
	}*/
	while (T->nil != x)
	{
		x->size = x->size+1; 
		y = x;
		if (rbkey <x->rbkey)
			x = x->left;
		else
			x = x->right;
		
	}

    // 把z放到合适的位置
	if (NULL == (z = (rbTreeNode)malloc(sizeof(*z))))
    {
        printf("Memory alloc error\n");
        return T;
    }
	z->parent = y;
    z->left = T->nil;
    z->right = T->nil;
    z->color = RED;
    z->rbkey = rbkey;
	z->size = 1;

    if (T->nil == y)
    {
        T->root = z;
    }
    else
    {
        if (z->rbkey < y->rbkey)
            y->left = z;
        else
            y->right = z;
    }
	// 对红黑树进行修正并返回
    return RB_Insert_Fixup(T, z);
}


rbTree RB_Insert_Fixup(rbTree T, rbTreeNode z)
{
    rbTreeNode y;
    while (T->root != z && RED == z->parent->color) // 当z不是根同时父节点的颜色是red
	{
        if (z->parent == z->parent->parent->left) // 父节点是祖父节点的左子树
		{
            y = z->parent->parent->right; // y为z的伯父节点
			if (RED == y->color) // 伯父节点存在且颜色是red
			{
				z->parent->color = BLACK; // 更改z的父节点颜色是B
				y->color = BLACK; // 更改z的伯父节点颜色是B
				z->parent->parent->color = RED; // 更改z的祖父节点颜色是B
				z = z->parent->parent; // 更新z为它的祖父节点
			}
            else // 无伯父节点或者伯父节点颜色是b
			{
				if (z == z->parent->right) // 如果新节点是父节点的右子树
				{
					z = z->parent;
                    Left_Rotate(T, z);
                }
				z->parent->color = BLACK; // 改变父节点颜色是B
				z->parent->parent->color = RED; // 改变祖父节点颜色是R
				Right_Rotate(T, z->parent->parent);
			}
		}
		else // 父节点为祖父节点的右子树
		{
            y = z->parent->parent->left; // y为z的伯父节点
			if (RED == y->color) // 伯父节点存在且颜色是red
			{
				z->parent->color = BLACK; // 更改z的父节点颜色是B
				y->color = BLACK; // 更改z的伯父节点颜色是B
				z->parent->parent->color = RED; // 更改z的祖父节点颜色是B
				z = z->parent->parent; // 更新z为它的祖父节点
			}
            else // 无伯父节点或者伯父节点颜色是b
			{
				if (z == z->parent->left) // 如果新节点是父节点的右子树
				{
					z = z->parent;
                    Right_Rotate(T, z);
                }
				z->parent->color = BLACK; // 改变父节点颜色是B
				z->parent->parent->color = RED; // 改变祖父节点颜色是R
				Left_Rotate(T, z->parent->parent);
			}
		}
	} // while(RED == z->parent->color)

	// 根节点的颜色始终都是B
	T->root->color = BLACK;
	return T;
}


rbTree RB_Delete(rbTree T, rbKEY rbkey)
{
	rbTreeNode x, y, z,t;
	z = RB_Search_Iterative(T->root, rbkey);
    if (SENTINEL == z)
	{
		printf("NO this rbkey in the tree!\n");
		return T;
	}
	// 当z有一个空子树的时候,y == z
	if (T->nil == z->left || T->nil == z->right)
		y = z;
	// 否则,y是大于z最小的结点
    else
	{
		y = RB_Successor(z);
    } 
	// x is y's only child
	if (T->nil != y->left)
        x = y->left;
    else
        x = y->right;
	
	t = y->parent;
	while (T->nil != t)
	{
		t->size--;
		t = t->parent;
	}
	// 设定x的位置取代y
    x->parent = y->parent;
    if (T->nil == y->parent)
        T->root = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x; // 把y的rbkey拷贝到z中
	if (y != z)
    {
        z->rbkey = y->rbkey;
    } 
	
	// 如果y的颜色值是B,那么要对树进行修正
	if (BLACK == y->color)
    RB_Delete_Fixup(T, x);
	free(y);
	return T;
}


rbTree RB_Delete_Fixup(rbTree T, rbTreeNode x)
{
	rbTreeNode w;
	while (x != T->root && BLACK == x->color)
	{
		if (x == x->parent->left) // 如果x是左子树
		{
			w = x->parent->right; // w是x的兄弟结点
			if (RED == w->color) // 如果w的颜色是红色 
			{
                w->color = BLACK;
                x->parent->color = RED;
                Left_Rotate(T, x->parent);
                w = x->parent->right;
            }
            if (BLACK == w->left->color && BLACK == w->right->color)
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                if (BLACK == w->right->color)
                {
                    w->left->color = BLACK;
                    w->color = RED;
                    Right_Rotate(T, w);
                    w = x->parent->right;
                }
				w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                Left_Rotate(T, x->parent);
                x = T->root;
			}
		}
		else
		{
			w = x->parent->left; // w是x的兄弟结点
			if (RED == w->color) // 如果w的颜色是红色 
			{
                w->color = BLACK;
                x->parent->color = RED;
                Right_Rotate(T, x->parent);
                w = x->parent->left;
            }
            if (BLACK == w->right->color && BLACK == w->left->color)
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                if (BLACK == w->left->color)
                {
                    w->right->color = BLACK;
                    w->color = RED;
                    Left_Rotate(T, w);
                    w = x->parent->left;
                }
				w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                Right_Rotate(T, x->parent);
                x = T->root;
			}
		}
    }
	x->color = BLACK;
	return T;
}


void RB_Print_Node(rbTreeNode node)
{
	if (node == SENTINEL)
		printf("Nil");
	else 
	{
		printf("%d",node->rbkey);
		if (node->color == BLACK)
			printf("B");
		else 
			printf("R");
	}
}


void RB_Free_Node(rbTreeNode node)
{
	free (node);
}


void RB_Pre_Visit(rbTreeNode node, rbProcess process)
{
	if (node != SENTINEL)
	{
		process(node);
		RB_Pre_Visit(node->left, process);
		RB_Pre_Visit(node->right, process);
	}
}


void RB_In_Visit(rbTreeNode node, rbProcess process)
{
	if (node != SENTINEL)
	{
		RB_In_Visit(node->left, process);
		process(node);
		RB_In_Visit(node->right, process);
	}
}


void RB_Post_Visit(rbTreeNode node, rbProcess process)
{
	if (node != SENTINEL)
	{
		RB_Post_Visit(node->left, process);
		RB_Post_Visit(node->right, process);
		process(node);
	}
}


void RB_Pre_Disply(rbTreeNode node, rbProcess process)
{
	int i;
	if (node == SENTINEL)
	{
		for (i=0;i<rbCount; i++)
			printf("  ");
		process(node);
	}
	else
	{
		for (i=0;i<rbCount; i++)
			printf("  ");
		printf("(");
		process(node);
		printf(" :\n");
		rbCount = rbCount+2;
		RB_Pre_Disply(node->left, process);
		printf(",\n");
		RB_Pre_Disply(node->right, process);
		printf("\n");
		rbCount = rbCount-2;
		for (i=0;i<rbCount; i++)
			printf("  ");
		printf(")");
		
	}

}


void RB_Displiy_Tree(rbTree T, rbVisit visit)
{
	rbTreeNode node;
	node = T->root;
	if (visit == RB_Pre_Disply)
		rbCount = 0;
	visit(node, RB_Print_Node);
	printf("\n");
}


void RB_Delete_Tree(rbTree T, rbVisit visit)
{
	rbTreeNode node;
	node = T->root;
	visit(node, RB_Free_Node);
	printf("\n");
}


int  Bh_Node(rbTreeNode node)
{
	if (node == SENTINEL)
		return 0;
	if (node->left->color == BLACK)
		return Bh_Node(node->left) + 1;
	else 
		return Bh_Node(node->left);
}


int  Bh_Tree(rbTree T)
{
	return Bh_Node(T->root);
}


rbTree RB_NewTree_Rand(int a[], int n)
{
	int i;
	rbTree T;
	T = RB_NewTree();
	for(i = 0; i < n; i++)
		RB_Insert(T, a[i]);
	return T;
}


void newRandArray(int a[], int nMinNum, int nCount)
{
	int i,address=0;
	int *inttemp; 
	inttemp = (int*)malloc(sizeof(int)*(nCount));
	for (i = 0; i < nCount; i++)//   初始化临时数组   
		inttemp[i] = i+nMinNum;
	srand((unsigned)time(NULL));//设置随机数产生种子
	for(i =nCount-1; i>0; i--)
	{
		address= (rand()| rand())% (i+1);//   产生随机下标   
		a[i]=inttemp[address];//   保存到第j个单元中
		if (address != i)
			inttemp[address] = inttemp[i];
		
		//for(k = address; k < i; k++)//   把取到值的单元的后面元素往前移动一个   
        //inttemp[k]=inttemp[k+1];
	}
	a[0]=inttemp[0];
	//for ( i = 0; i<nCount; i++)
		//free(inttemp+i);
}



int  RB_OS_Key_Rank(rbTreeNode node, rbKEY k)
{
	if ((node->rbkey) == k)
		return (node->left)->size + 1;
	else
		if ((node->rbkey) > k)
			return RB_OS_Key_Rank(node->left, k);
		else
			return (node->left)->size + 1 + RB_OS_Key_Rank(node->right, k);
}



int  OS_Key_Rank(rbTree T, rbKEY k)
{
	return RB_OS_Key_Rank(T->root, k);
}