分享一个红黑树的实现，请大家伙儿帮忙指出需要优化的地方

分享一个红黑树的实现，请大家帮忙指出需要优化的地方
最近研究了下红黑树的实现原理，就忍不住动手写了一个，分享给大家，也希望大家多提提意见～
rbtree.h

#ifndef __RBTREE_H__
#define __RBTREE_H__

#include &lt;stdio.h&gt;

#define P(x) x-&gt;p//父节点
#define LEFT(x) x-&gt;left//左孩子
#define RIGHT(x) x-&gt;right//右孩子
#define KEY(x) x-&gt;value//值
#define NIL(T) &(T-&gt;nil)//哨兵节点
#define COLOR(x) x-&gt;color//颜色
#define ROOT(T) (T-&gt;root)//根节点

#define PRINT_INT(x) printf("%d ", *(int*)(KEY(x)))//输出int
#define PRINT_STR(x) printf("%s ", KEY(x))//输出字符串

enum RBCOLOR{RED, BLACK, NODEF};//节点颜色
typedef struct RBNode_tag
{
RBCOLOR color;//颜色
struct RBNode_tag *left;//左孩子
struct RBNode_tag *right;//右孩子
struct RBNode_tag *p;//父节点
void* value;//值
}RBNode , *PRBNode;

typedef struct RB_TREE_TAG{
PRBNode root;//根节点
RBNode nil;//哨兵节点
PRBNode current;//
int count ;
int (*compare)(void* , void*);
void (*copy)(void*, void*);
}RB_TREE, *PRB_TREE;


void INITIALIZE_RBNODE(PRBNode x);//初始化树节点
void INITIALIZE_RBTREE(PRB_TREE T, int (*compare)(void*, void*), void (*copy)(void* , void*));//初始化树
void RBTREE_WALK(PRBNode n, PRBNode nil,void (*Print)(PRBNode p));//遍历
PRBNode RBTREE_SEARCH(PRB_TREE, void*);//查找
PRBNode TREE_MINIMUM(PRB_TREE T, PRBNode n);//最小
PRBNode TREE_MAXIMUM(PRB_TREE T, PRBNode n);//最大
PRBNode TREE_SUCCESSOR(PRB_TREE T, PRBNode n);//后继
PRBNode TREE_PREDECESSOR(PRB_TREE T,PRBNode n);//前趋 
void LEFT_ROTATE(PRB_TREE T, PRBNode x);//左旋
void RIGHT_ROTATE(PRB_TREE T, PRBNode x);//右旋
void RB_INSERT_FIXUP(PRB_TREE T ,PRBNode z);//插入修正
void RB_INSERT(PRB_TREE T , PRBNode z);//插入
void RB_DELETE_FIXUP(PRB_TREE T, PRBNode x);//删除
PRBNode RB_DELETE(PRB_TREE T, PRBNode z);//删除修正
void RBTREE_ROUND(PRBNode n, PRBNode nil, void* (*func)(PRBNode n, void* p),void* p);//遍历2

#endif[code=c]

rbtree.cpp

#include "rbtree.h"

//初始化红黑树节点
void INITIALIZE_RBNODE(PRBNode x) {  
if(x!=NULL){
x-&gt;color = BLACK;
x-&gt;left = NULL;
x-&gt;right = NULL;
x-&gt;p = NULL;
x-&gt;value = NULL;
}
}


//初始化红黑树
void INITIALIZE_RBTREE(PRB_TREE T, int (*compare)(void*, void*), void (*copy)(void* , void*)){ //
if(T != NULL){
T-&gt;root = &T-&gt;nil;
T-&gt;current = &T-&gt;nil;
T-&gt;count = 0;
T-&gt;compare = compare;
T-&gt;copy = copy;
T-&gt;nil.color = BLACK;
T-&gt;nil.left = T-&gt;nil.p = T-&gt;nil.right = &T-&gt;nil;
T-&gt;nil.value = NULL;
}
}


//遍历树
void RBTREE_WALK(PRBNode n, PRBNode nil,void (*Print)(PRBNode p))
{
if(n!=nil)
{
RBTREE_WALK(LEFT(n), nil,Print);
Print(n);
RBTREE_WALK(RIGHT(n), nil,Print);
}
}

//遍历树
void RBTREE_ROUND(PRBNode n, PRBNode nil, void* (*func)(PRBNode n, void* p),void* p)
{
if(n!=nil)
{
RBTREE_ROUND(LEFT(n), nil,func,p);
func(n,p);
RBTREE_ROUND(RIGHT(n), nil,func,p);
}
}


//查找
PRBNode RBTREE_SEARCH(PRB_TREE T, void* v)  
{

PRBNode n = T-&gt;root;
while(n!=NIL(T))
{
int val = T-&gt;compare(v,n-&gt;value);
if(val &gt;0)n = RIGHT(n);
else if(val &lt;0)n= LEFT(n);
else break;
}
return n;
}


//最小节点
PRBNode TREE_MINIMUM(PRB_TREE T, PRBNode n)
{
while(LEFT(n)!= NIL(T))
n = LEFT(n);
return n;
}



//最大节点
PRBNode TREE_MAXIMUM(PRB_TREE T, PRBNode n)
{
while(RIGHT(n) != NIL(T))
n = RIGHT(n);
return n;
}

//后继
PRBNode TREE_SUCCESSOR(PRB_TREE T, PRBNode n)
{
PRBNode y;
if(RIGHT(n) != NIL(T))
return TREE_MINIMUM(T,RIGHT(n));
y = P(n);
while(y!= NIL(T)&&RIGHT(y)==n)
{
n = y;
y = P(n);
}
return y;

}

//前趋
PRBNode TREE_PREDECESSOR(PRB_TREE T,PRBNode n)
{
PRBNode y;
if(LEFT(n) !=  NIL(T))
return TREE_MAXIMUM(T,LEFT(n));
y = n;
do{
n = y;
y = P(n);
}while(y!= NIL(T)&&LEFT(y)==n);
return y;
}


//左旋
void LEFT_ROTATE(PRB_TREE T, PRBNode x)
{
PRBNode y = RIGHT(x);
if(y == NIL(T))return; 
 
RIGHT(x) = LEFT(y);
if(LEFT(y) != NIL(T))P(LEFT(y)) = x;
P(y) = P(x);
if(P(x)==NIL(T)){
ROOT(T) = y;
}else{
if (LEFT(P(x))==x){
LEFT(P(x))=y;
}else{
RIGHT(P(x))=y;
}
}
P(x) = y;
LEFT(y) = x;

}


//右旋
void RIGHT_ROTATE(PRB_TREE T, PRBNode x)
{
PRBNode y = LEFT(x);
if(y == NIL(T))return;
LEFT(x) = RIGHT(y);
if(RIGHT(y) != NIL(T))P(RIGHT(y)) = x;
P(y) = P(x);
if(P(x)==NIL(T)){
ROOT(T) = y;
}else{
if (RIGHT(P(x))==x){
RIGHT(P(x))=y;
}else{
LEFT(P(x))=y;
}
}
P(x) = y;
RIGHT(y) = x;
}

//插入修正
void RB_INSERT_FIXUP(PRB_TREE T ,PRBNode z)
{
PRBNode y;
while(COLOR(P(z)) == RED)
{
y = (P(z)==LEFT(P(P(z))))?RIGHT(P(P(z))):LEFT(P(P(z)));
if (COLOR(y) == RED){
COLOR(P(z)) = BLACK;
COLOR(y) = BLACK;
COLOR(P(P(z))) = RED;
z = P(P(z));
continue;
}
if(P(z) == LEFT(P(P(z)))){
if(z == RIGHT(P(z))){
z = P(z);
LEFT_ROTATE(T, z);
}
COLOR(P(z)) = BLACK;
COLOR(P(P(z))) = RED;
RIGHT_ROTATE(T , P(P(z)));
}else{
if(z==LEFT(P(z))){
z= P(z);
RIGHT_ROTATE(T, z);
}
COLOR(P(z)) = BLACK;
COLOR(P(P(z))) = RED;
LEFT_ROTATE(T, P(P(z)));
}
}
COLOR(ROOT(T)) = BLACK;
}

//插入
void RB_INSERT(PRB_TREE T , PRBNode z)
{
PRBNode y = NIL(T);
PRBNode x = ROOT(T);
while(x != NIL(T)){
y = x;
x= T-&gt;compare(KEY(z), KEY(x))&lt;0?LEFT(x):RIGHT(x);
}
if(y==NIL(T)){
ROOT(T) = z;
}else{
if(T-&gt;compare(KEY(z),KEY(y)) &lt;0)LEFT(y) = z;
else RIGHT(y) = z;
}
P(z) = y;
COLOR(z) = RED;
LEFT(z) = RIGHT(z) = NIL(T);
RB_INSERT_FIXUP(T, z);
}

//删除修正
void RB_DELETE_FIXUP(PRB_TREE T, PRBNode x)
{
PRBNode w = NULL;
while(x!=ROOT(T) && COLOR(x)==BLACK)
{
if(x == LEFT(P(x))){
w = RIGHT(P(x));
if(COLOR(w) == RED){   //case 1
COLOR(w) = BLACK;
COLOR(P(x)) = RED;
LEFT_ROTATE(T,P(x));
w = RIGHT(P(x));
}
if(COLOR(RIGHT(w))==BLACK && COLOR(LEFT(w))==BLACK){ //case 2
COLOR(w) = RED;
x = P(x); 
}
if(COLOR(RIGHT(w))==BLACK && COLOR(LEFT(w))==RED){  //case 3
COLOR(w) = RED;
COLOR(LEFT(w)) = BLACK;
RIGHT_ROTATE(T,w);
}
if(COLOR(RIGHT(w)) == RED){          //case 4
COLOR(w) = COLOR(P(w));
COLOR(RIGHT(w)) = BLACK;
COLOR(P(w)) = BLACK;
LEFT_ROTATE(T,P(x));
x = ROOT(T);
break;
}
}else{
w = LEFT(P(x));
if(COLOR(w) == RED){   //case 1
COLOR(w) = BLACK;
COLOR(P(x)) = RED;
RIGHT_ROTATE(T,P(x));
w = LEFT(P(x));
}
if(COLOR(LEFT(w))==BLACK && COLOR(RIGHT(w))==BLACK){ //case 2
COLOR(w) = RED;
x = P(x); 
}
if(COLOR(LEFT(w))==BLACK && COLOR(RIGHT(w))==RED){  //case 3
COLOR(w) = RED;
COLOR(RIGHT(w)) = BLACK;
LEFT_ROTATE(T,w);
}
if(COLOR(LEFT(w)) == RED){          //case 4
COLOR(w) = COLOR(P(w));
COLOR(LEFT(w)) = BLACK;
COLOR(P(w)) = BLACK;
RIGHT_ROTATE(T,P(x));
x = ROOT(T);
break;
}
}
}
COLOR(x) = BLACK;
}

//删除
PRBNode RB_DELETE(PRB_TREE T, PRBNode z)
{
PRBNode x,y;
y =  (LEFT(z)==NIL(T)||RIGHT(z)==NIL(T))?z:TREE_SUCCESSOR(T,z);
x = LEFT(y)!=NIL(T)?LEFT(y):RIGHT(y);
P(x) = P(y);
if(P(y) == NIL(T)){
ROOT(T) = x;
}else{
if(y == LEFT(P(y))){
LEFT(P(y)) = x;
}else{
RIGHT(P(y)) = x;
}
}
if(y!=z){
T-&gt;copy(z, y);
}
if(COLOR(y) == BLACK){
RB_DELETE_FIXUP(T, x);
}
return y!=NIL(T)?y:NULL;
}

[解决办法]
有具体的实现就自己对照一下吧

分享一个红黑树的实现请大家伙儿帮忙

热点推荐