tree.h

红黑树算法

// Tree.h: interface for the CTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_TREE_H__0D5851CD_98F9_4B94_A83F_673810F2C84A__INCLUDED_)
#define AFX_TREE_H__0D5851CD_98F9_4B94_A83F_673810F2C84A__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <time.h>

class CTree  
{
public:
	
	enum NODECOLOR
	{
        BLACK        = 0,
		RED          = 1
	};
	friend class CHongheiView;
	typedef struct RBTree
	{
        struct                RBTree *parent;
        struct                RBTree *left, *right;
        int                        key;
        NODECOLOR   color;
	}RBTree,*PRBTree;
	RBTree *root,*nil;
	CTree()
	{   
		nil=new RBTree;	
		nil->color=BLACK;
		nil->left=nil->right=nil->parent=NULL;
		nil->color=RED;
		nil->key=0;
		root=nil;
		this->main();
	}
	virtual ~CTree();
void Left_Rotate(RBTree *A, RBTree * root)
{        
        RBTree *B;
        B = A->right;

        A->right  = B->left;
        if (nil!= B->left)
                B->left->parent = A;
        B->parent = A->parent;
        // 这样三个判断连在一起避免了A->parent = NULL的情况 
        if (A->parent == nil)
        {
                root = B;
        }
        else
		{ 
			if(A == A->parent->left)
			{
                A->parent->left = B;
			}
			else
			{
                A->parent->right = B;
			}
		}
        B->left= A;
        A->parent = B;
}

void Right_Rotate(RBTree *A, RBTree *root)
{
        RBTree *B;
        B = A->left;
        A->left  = B->right;
        if (nil!= B->right)
                B->right->parent = A;
        B->parent = A->parent;
        // 这样三个判断连在一起避免了A->parent = NULL的情况 
        if (A->parent== nil)
        {
                root = B;
        }
        else
		{
			if (A == A->parent->right)
			{
                A->parent->right = B;
			}
			else
			{
                A->parent->left = B;
			}
		}
        
        B->right  = A;
		A->parent = B;
}
/*-----------------------------------------------------------
|        函数作用:查找int值对应的结点指针
|        输入参数:根节点root,待查找关键值int
|        返回参数:如果找到返回结点指针,否则返回NULL
-------------------------------------------------------------*/
RBTree *Find_Node(RBTree *root, int key)
{
        RBTree *x;

        // 找到int所在的node
        x = root;
        while(x!=nil)
		{
			if(key<x->key)
				x=x->left;
			else if(key>x->key)
				x=x->right;
			else
				return x;
		}
		return nil;
}

/*-----------------------------------------------------------
|        函数作用:在树中插入int值
|        输入参数:根节点root,待插入结点的关键值int
|        返回参数:根节点root
-------------------------------------------------------------*/


RBTree *RB_InsertNode(RBTree *root, int key)
{
	RBTree *x, *y;
	
	RBTree *z;
	z = new RBTree;	
	z->key = key;

	
	// 得到z的父节点
	x = root, y = nil;
	while(x!=nil)
	{
		y=x;
		if(z->key<x->key)
			x=x->left;
		else
			x=x->right;
	}
	z->parent=y;
	if(y==nil)
		root=z;
	else
	{
		if(z->key<y->key)
			y->left=z;
		else
			y->right=z;
	}
	z->color = RED;
	z->left = z->right = nil;
	return RB_InsertNode_Fixup(root, z);
}
/*-----------------------------------------------------------
|        函数作用:对插入int值之后的树进行修正
|        输入参数:根节点root,插入的结点z
|        返回参数:根节点root
-------------------------------------------------------------*/
RBTree *RB_InsertNode_Fixup(RBTree *root, RBTree *z)
{
        RBTree *y;
        while (root != z && RED == z->parent->color)        // 当z不是根同时父节点的颜色是red
        {
                if (z->parent == z->parent->parent->left)        // 父节点是祖父节点的左子树
                {
                        y = z->parent->parent->right;                        // y为z的伯父节点
                        if (nil!= y && 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(z, root);
                                }
                                z->parent->color = BLACK;                        // 改变父节点颜色是B
                                z->parent->parent->color = RED;                // 改变祖父节点颜色是R
                                Right_Rotate(z->parent->parent, root);
                        }
                }
                else                                                                                // 父节点为祖父节点的右子树
                {
                        y = z->parent->parent->left;                        // y为z的伯父节点
                        if (nil != y && RED == y->color)                // 如果y的颜色是red
                        {
                                z->parent->color = BLACK;                        // 更改父节点的颜色为B
                                y->color = BLACK;                                        // 更改伯父节点的颜色是B
                                z->parent->parent->color = RED;                // 更改祖父节点颜色是R
                                z = z->parent->parent;                                // 更改z指向祖父节点
                        }                
                        else                                                                        // y不存在或者颜色是B
                        {
                                if (z == z->parent->left)                        // 如果是父节点的左子树
                                {
                                        z = z->parent;
                                        Right_Rotate(z, root);
                                }
                                z->parent->color = BLACK;                        // 改变父节点的颜色是B
                                z->parent->parent->color = RED;                // 改变祖父节点的颜色是RED
                                Left_Rotate(z->parent->parent, root);
                        }
                }
        } 
        // 根节点的颜色始终都是B
        root->color = BLACK;
        return root;
}
RBTree *successor(RBTree *x)
{
    RBTree *y;
	if(x->right!=nil)
	{
		x=x->right;
		while(x->left!=nil)
			x=x->left;
		return x;
	}
	y=x->parent;               
	while(y!=nil&&x==y->right)
	{
		x=y;
		y=y->parent;
	}
	return y;

}
/*-----------------------------------------------------------
|        函数作用:在树中删除int值
|        输入参数:根节点root,待插入结点的关键值int
|        返回参数:根节点root
-------------------------------------------------------------*/
RBTree* RB_DeleteNode(RBTree *root, int key)
{
        RBTree *x, *y, *z;

        z = Find_Node(root, key);

        if (nil == z->left || nil== z->right)// 当z有一个空子树的时候,y = z
                y = z;
        else// 否则,y是大于z最小的结点
			y=successor(z);
		
        // x是y的子树,可能为NULL
        if (nil!= y->left)
			x = y->left;
        else
			x = y->right;
		
        // 设定x的位置取代y
        x->parent = y->parent;
        if (nil == y->parent)
			root = x;
        else 
		{
			if (y == y->parent->left)
                y->parent->left = x;
			else
				y->parent->right = x;
		}
		
        // 把y的int拷贝到z中,这样y就是待删除的结点了
        if (y != z)
        {
			z->key = y->key;
        }
		
        // 如果y的颜色值是B,那么要对树进行修正
        if (BLACK == y->color)
			RB_DeleteNode_Fixup(root, x);
		
        delete (y);

        return root;
}
/*-----------------------------------------------------------
|        函数作用:对删除int值之后的树进行修正
|        输入参数:根节点root,删除的结点的子结点x
|        返回参数:根节点root
-------------------------------------------------------------*/
RBTree *RB_DeleteNode_Fixup(RBTree *root, RBTree *x)
{
        RBTree *w;

        while (x != 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(x->parent, root);
                                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(w, root);
                                        w = x->parent->right;
                                }

                                w->color = x->parent->color;
                                x->parent->color = BLACK;
                                w->right->color  = BLACK;
                                Left_Rotate(x->parent, root);
                                x = root;
                        }
                }
                else
                {
                        w = x->parent->left;
                        if (RED == w->color)
                        {
                                w->color = BLACK;
                                x->parent->color = RED;
                                Left_Rotate(x->parent, root);
                                w = x->parent->left;
                        }
                        if (BLACK == w->left->color && BLACK == w->right->color)
                        {
                                w->color = RED;
                                x = x->parent;
                        }
                        else
                        {
                                if (BLACK == w->left->color)
                                {
                                        w->right->color = BLACK;
                                        w->color = RED;
                                        Left_Rotate(w, root);
                                        w = x->parent->left;
                                }

                                w->color = x->parent->color;
                                x->parent->color = BLACK;
                                w->left->color=BLACK;
                                Right_Rotate(x->parent, root);
                                x = root;
                        }
                }
        }

        x->color = BLACK;

        return root;
}

void Create_New_Array(int array[], int length)
{
        for (int i = 0; i < length; i++)
        {
            array[i] = rand() % 256;
			
        }
}

int main()
{
        
        int array[10];
        srand(time(NULL));
		Create_New_Array(array, 10);


        int i;
        for (i = 0; i < 10; i++)
        {
                root = RB_InsertNode(root, array[i]);
        }
		
        return 0;
}
		
};

#endif // !defined(AFX_TREE_H__0D5851CD_98F9_4B94_A83F_673810F2C84A__INCLUDED_)