几点说明：
1、网上给出的一些红黑树实现示例固定了节点类型，关键字，不适合很多应用场景
2、网上给出的一些红黑树实现不能兼容节点属于多个红黑树
3、函数、变量、类型等命名不符合一般的linux风格，但有一定的原则（公司习惯遗留下来）
4、接口尽量正交、易用、最小化，不提供没有必要支持的功能，如一棵树中的节点个数（这个由使用者自己统计）
5、添加接口：只需要设置好关键字就可以正常添加，返回值非空时，表示等值的节点已经在树中，返回值是该节点的地址
6、移除接口：需要先查找，再删除，很多情况下是通过其他的途径得到节点，然后从树中删除，所以，查找和移除是分开的
7、getNext， getPrev的第二个参数指定不在树中的暂时没有实现，有需要的自己补充实现
头文件如下：
#ifndef __YUDS_RBTREE_H__
#define __YUDS_RBTREE_H__
typedef struct tag_rb_node
{
unsigned long ulRbParentColor;
struct tag_rb_node *pstLeft, *pstRight;
}YUDS_RBTREE_NODE_S;
typedef int (*YUDS_RBTREE_CMP_FUNC)(YUDS_RBTREE_NODE_S *pstNodeInTree, YUDS_RBTREE_NODE_S *pstNode);
typedef struct tag_rb_root {
YUDS_RBTREE_NODE_S *pstRootNode;
YUDS_RBTREE_CMP_FUNC pfnCmp;
}YUDS_RBTREE_ROOT_S;
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({
const typeof( ((type *)0)->member ) *__mptr = (ptr);
(type *)( (char *)__mptr - offsetof(type,member));})
#define YUDS_RBTREE_ENTRY(ptr, type, member) container_of(ptr, type, member)
int YuDS_rbtree_add(YUDS_RBTREE_ROOT_S *pstRoot,
YUDS_RBTREE_NODE_S *pstNode,
YUDS_RBTREE_NODE_S **ppstRet);
void YuDS_rbtree_del(YUDS_RBTREE_ROOT_S *pstRoot, YUDS_RBTREE_NODE_S *pstNode);
YUDS_RBTREE_NODE_S *YuDS_rbtree_search(YUDS_RBTREE_ROOT_S *pstRoot, YUDS_RBTREE_NODE_S *pstNode);
YUDS_RBTREE_NODE_S *YuDS_rbtree_getFirst(YUDS_RBTREE_ROOT_S *pstRoot);
YUDS_RBTREE_NODE_S *YuDS_rbtree_getLast(YUDS_RBTREE_ROOT_S *pstRoot);
YUDS_RBTREE_NODE_S *YuDS_rbtree_getNext(YUDS_RBTREE_NODE_S *pstNode, int iIsNodeInTree);
YUDS_RBTREE_NODE_S *YuDS_rbtree_getPrev(YUDS_RBTREE_NODE_S *pstNode, int iIsNodeInTree);
void YuDS_rbtree_init(YUDS_RBTREE_ROOT_S *pstRoot, YUDS_RBTREE_CMP_FUNC pfnCmp);
#endif
实现文件如下：
#include <stdlib.h>
#include <assert.h>
#include "YuDS_rbtree.h"
typedef enum rbtree_color
{
RBTREE_COLOR_RED = 0,
RBTREE_COLOR_BLACK = 1
}RBTREE_COLOR_E;
#define YUDS_RBTREE_EMPTY_NODE(node) ((node)->ulRbParentColor == (unsigned long)(node))
#define YUDS_RBTREE_CLEAR_NODE(node) ((node)->ulRbParentColor = (unsigned long)(node))
#define RBTREE_NODE_COLOR(node) (((node)->ulRbParentColor) & 1)
#define RBTREE_NODE_PARENT(node) ((YUDS_RBTREE_NODE_S *)((node)->ulRbParentColor & ~1))
#define RBTREE_SET_PARENT(node, parent)
(node)->ulRbParentColor = (unsigned long)(parent) | RBTREE_NODE_COLOR(node)
#define RBTREE_SET_BLACK(node)
(node)->ulRbParentColor |= RBTREE_COLOR_BLACK
#define RBTREE_SET_PARENT_AND_COLOR(node, parent, color)
(node)->ulRbParentColor = (unsigned long)(parent) | (color)
static YUDS_RBTREE_NODE_S *rbtree_preSearch(YUDS_RBTREE_ROOT_S *pstRoot,
YUDS_RBTREE_NODE_S *pstNode,
YUDS_RBTREE_NODE_S **ppstParent,
YUDS_RBTREE_NODE_S ***pppstSave)
{
int iCmpRet = 0;
YUDS_RBTREE_NODE_S *pstNodeTmp = pstRoot->pstRootNode;
YUDS_RBTREE_NODE_S *pstParent = NULL;
YUDS_RBTREE_CMP_FUNC pfnCmp = pstRoot->pfnCmp;
while (NULL != pstNodeTmp) {
pstParent = pstNodeTmp;
iCmpRet = pfnCmp(pstNodeTmp, pstNode);
if (iCmpRet > 0)
pstNodeTmp = pstNodeTmp->pstLeft;
else if (iCmpRet < 0)
pstNodeTmp = pstNodeTmp->pstRight;
else
return pstNodeTmp;
}
if (NULL != ppstParent)
*ppstParent = pstParent;
if (NULL != pppstSave) {
if (NULL == pstParent)
*pppstSave = &pstRoot->pstRootNode;
else {
if (iCmpRet > 0)
*pppstSave = &pstParent->pstLeft;
else
*pppstSave = &pstParent->pstRight;
}
}
return NULL;
}
int YuDS_rbtree_add(YUDS_RBTREE_ROOT_S *pstRoot,
YUDS_RBTREE_NODE_S *pstNode,
YUDS_RBTREE_NODE_S **ppstRet)
{
YUDS_RBTREE_NODE_S *pstParent, **ppstSave, *pstGParentTmp, *pstNodeTmp;
pstNodeTmp = rbtree_preSearch(pstRoot, pstNode, &pstParent, &ppstSave);
if (NULL != pstNodeTmp) {
if (NULL != ppstRet) {
*ppstRet = pstNodeTmp;
}
return -1;
}
YUDS_RBTREE_CLEAR_NODE(pstNode);
pstNode->ulRbParentColor = (unsigned long)pstParent;
pstNode->pstLeft = pstNode->pstRight = NULL;
*ppstSave = pstNode;
while (1) {
if (NULL == pstParent) {
RBTREE_SET_PARENT_AND_COLOR(pstNode, NULL, RBTREE_COLOR_BLACK);
pstRoot->pstRootNode = pstNode;
break;
}
else if (RBTREE_COLOR_BLACK == RBTREE_NODE_COLOR(pstParent))
break;
pstGParentTmp = RBTREE_NODE_PARENT(pstParent);
pstNodeTmp = pstGParentTmp->pstRight;
if (pstParent != pstNodeTmp) {
if ((NULL != pstNodeTmp) && (RBTREE_COLOR_RED == RBTREE_NODE_COLOR(pstNodeTmp))) {
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstGParentTmp, RBTREE_COLOR_BLACK);
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp, pstGParentTmp, RBTREE_COLOR_BLACK);
pstNode = pstGParentTmp;
pstParent = RBTREE_NODE_PARENT(pstNode);
RBTREE_SET_PARENT_AND_COLOR(pstNode, pstParent, RBTREE_COLOR_RED);
continue;
}
else {
pstNodeTmp = pstParent->pstRight;
if (pstNode == pstNodeTmp) {
pstParent->pstRight = pstNodeTmp = pstNode->pstLeft;
pstNode->pstLeft = pstParent;
if (NULL != pstNodeTmp)
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp, pstParent, RBTREE_COLOR_BLACK);
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstNode, RBTREE_COLOR_RED);
pstParent = pstNode;
pstNodeTmp = pstNode->pstRight;
}
pstGParentTmp->pstLeft = pstNodeTmp;
pstParent->pstRight = pstGParentTmp;
if (NULL != pstNodeTmp)
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp, pstGParentTmp, RBTREE_COLOR_BLACK);
pstNodeTmp = RBTREE_NODE_PARENT(pstGParentTmp);
pstParent->ulRbParentColor = pstGParentTmp->ulRbParentColor;
RBTREE_SET_PARENT_AND_COLOR(pstGParentTmp, pstParent, RBTREE_COLOR_RED);
if (NULL == pstNodeTmp)
pstRoot->pstRootNode = pstParent;
else {
if (pstNodeTmp->pstLeft == pstGParentTmp)
pstNodeTmp->pstLeft = pstParent;
else
pstNodeTmp->pstRight = pstParent;
}
break;
}
}
else {
pstNodeTmp = pstGParentTmp->pstLeft;
if ((NULL != pstNodeTmp) && (RBTREE_COLOR_RED == RBTREE_NODE_COLOR(pstNodeTmp))) {
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstGParentTmp, RBTREE_COLOR_BLACK);
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp, pstGParentTmp, RBTREE_COLOR_BLACK);
pstNode = pstGParentTmp;
pstParent = RBTREE_NODE_PARENT(pstNode);
RBTREE_SET_PARENT_AND_COLOR(pstNode, pstParent, RBTREE_COLOR_RED);
continue;
}
else {
pstNodeTmp = pstParent->pstLeft;
if (pstNode == pstNodeTmp) {
pstParent->pstLeft = pstNodeTmp = pstNode->pstRight;
pstNode->pstRight = pstParent;
if (NULL != pstNodeTmp)
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp, pstParent, RBTREE_COLOR_BLACK);
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstNode, RBTREE_COLOR_RED);
pstParent = pstNode;
pstNodeTmp = pstNode->pstLeft;
}
pstGParentTmp->pstRight = pstNodeTmp;
pstParent->pstLeft = pstGParentTmp;
if (NULL != pstNodeTmp)
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp, pstGParentTmp, RBTREE_COLOR_BLACK);
pstNodeTmp = RBTREE_NODE_PARENT(pstGParentTmp);
pstParent->ulRbParentColor = pstGParentTmp->ulRbParentColor;
RBTREE_SET_PARENT_AND_COLOR(pstGParentTmp, pstParent, RBTREE_COLOR_RED);
if (NULL == pstNodeTmp)
pstRoot->pstRootNode = pstParent;
else {
if (pstNodeTmp->pstLeft == pstGParentTmp)
pstNodeTmp->pstLeft = pstParent;
else
pstNodeTmp->pstRight = pstParent;
}
break;
}
}
}
return 0;
}
void YuDS_rbtree_del(YUDS_RBTREE_ROOT_S *pstRoot, YUDS_RBTREE_NODE_S *pstNode)
{
YUDS_RBTREE_NODE_S *pstNodeChild = pstNode->pstRight;
YUDS_RBTREE_NODE_S *pstNodeTmp = pstNode->pstLeft;
YUDS_RBTREE_NODE_S *pstParent, *pstSuccessor, *pstNodeChild2, *pstRebalance;
YUDS_RBTREE_NODE_S *pstSibling, *pstNodeTmp1, *pstNodeTmp2; // 这几个变量专用于调整颜色
// 如果没有左孩子
if (NULL == pstNodeTmp) {
pstParent = RBTREE_NODE_PARENT(pstNode);
if (NULL == pstParent)
pstRoot->pstRootNode = pstNodeChild;
else {
if (pstNode == pstParent->pstLeft)
pstParent->pstLeft = pstNodeChild;
else
pstParent->pstRight = pstNodeChild;
}
// 如果没有右孩子
if (NULL == pstNodeChild) {
if (RBTREE_COLOR_RED == RBTREE_NODE_COLOR(pstNode))
return;
else {
if (NULL == pstParent)
return;
pstRebalance = pstParent;
goto flag_rebalance;
}
}
// 如果有右孩子, 根据性质所有叶节点等黑高知其一定是红色
else {
pstNodeChild->ulRbParentColor = pstNode->ulRbParentColor;
return;
}
}
// 没有右孩子，有左孩子. 两个孩子都没有的在上一个if那里处理完了
else if (NULL == pstNodeChild) {
pstParent = RBTREE_NODE_PARENT(pstNode);
if (NULL == pstParent)
pstRoot->pstRootNode = pstNodeTmp;
else {
if (pstNode == pstParent->pstLeft)
pstParent->pstLeft = pstNodeTmp;
else
pstParent->pstRight = pstNodeTmp;
}
pstNodeTmp->ulRbParentColor = pstNode->ulRbParentColor;
return;
}
// 两个孩子都存在
else {
pstSuccessor = pstNodeChild;
pstNodeTmp = pstNodeChild->pstLeft;
if (NULL == pstNodeTmp) {
pstParent = pstSuccessor;
pstNodeChild2 = pstSuccessor->pstRight;
}
else {
do {
pstParent = pstSuccessor;
pstSuccessor = pstNodeTmp;
pstNodeTmp = pstNodeTmp->pstLeft;
} while (NULL != pstNodeTmp);
pstParent->pstLeft = pstNodeChild2 = pstSuccessor->pstRight;
pstSuccessor->pstRight = pstNodeChild;
RBTREE_SET_PARENT(pstNodeChild, pstSuccessor);
}
pstSuccessor->pstLeft = pstNodeTmp = pstNode->pstLeft;
RBTREE_SET_PARENT(pstNodeTmp, pstSuccessor);
pstNodeTmp = RBTREE_NODE_PARENT(pstNode);
if (NULL == pstNodeTmp)
pstRoot->pstRootNode = pstSuccessor;
else {
if (pstNodeTmp->pstLeft == pstNode)
pstNodeTmp->pstLeft = pstSuccessor;
else
pstNodeTmp->pstRight = pstSuccessor;
}
if (NULL != pstNodeChild2) {
pstSuccessor->ulRbParentColor = pstNode->ulRbParentColor;
RBTREE_SET_PARENT_AND_COLOR(pstNodeChild2, pstParent, RBTREE_COLOR_BLACK);
return;
}
else {
if (RBTREE_COLOR_BLACK == RBTREE_NODE_COLOR(pstSuccessor)) {
pstSuccessor->ulRbParentColor = pstNode->ulRbParentColor;
pstRebalance = pstParent;
goto flag_rebalance;
}
else {
pstSuccessor->ulRbParentColor = pstNode->ulRbParentColor;
return;
}
}
}
flag_rebalance:
assert(NULL != pstRebalance);
pstParent = pstRebalance;
pstNode = NULL;
while (1) {
pstSibling = pstParent->pstRight;
// node为NULL或是左
if (pstNode != pstSibling) {
// 红兄弟 --> 转换成黑兄弟
if (RBTREE_COLOR_RED == RBTREE_NODE_COLOR(pstSibling)) {
pstParent->pstRight = pstNodeTmp1 = pstSibling->pstLeft;
pstSibling->pstLeft = pstParent;
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp1, pstParent, RBTREE_COLOR_BLACK);
pstNodeTmp = RBTREE_NODE_PARENT(pstParent);
pstSibling->ulRbParentColor = pstParent->ulRbParentColor;
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstSibling, RBTREE_COLOR_RED);
if (NULL == pstNodeTmp)
pstRoot->pstRootNode = pstSibling;
else {
if (pstNodeTmp->pstLeft == pstParent)
pstNodeTmp->pstLeft = pstSibling;
else
pstNodeTmp->pstRight = pstSibling;
}
pstSibling = pstNodeTmp1;
}
//******************************** 黑兄弟的情况 *************************************
pstNodeTmp1 = pstSibling->pstRight;
// 1. 右侄子为空或者黑
if ((NULL == pstNodeTmp1) || (RBTREE_COLOR_BLACK == RBTREE_NODE_COLOR(pstNodeTmp1))) {
pstNodeTmp2 = pstSibling->pstLeft;
// 左侄子为空或者黑 ---> #### 把问题上推给父亲 ###
if ((NULL == pstNodeTmp2) || (RBTREE_COLOR_BLACK == RBTREE_NODE_COLOR(pstNodeTmp2))) {
RBTREE_SET_PARENT_AND_COLOR(pstSibling, pstParent, RBTREE_COLOR_RED);
if (RBTREE_COLOR_RED == RBTREE_NODE_COLOR(pstParent))
RBTREE_SET_BLACK(pstParent);
else {
pstNode = pstParent;
pstParent = RBTREE_NODE_PARENT(pstNode);
if (NULL != pstParent)
continue;
}
break;
}
// 左侄子为红, 右侄子为黑 ---> #### 转换成右红, 还没调整完毕 ###
pstSibling->pstLeft = pstNodeTmp1 = pstNodeTmp2->pstRight;
pstNodeTmp2->pstRight = pstSibling;
pstParent->pstRight = pstNodeTmp2;
if (NULL != pstNodeTmp1)
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp1, pstSibling, RBTREE_COLOR_BLACK);
pstNodeTmp1 = pstSibling;
pstSibling = pstNodeTmp2;
}
// 2. 右侄子为红, 左红右黑调整后需要按照这里继续处理
pstParent->pstRight = pstNodeTmp2 = pstSibling->pstLeft;
pstSibling->pstLeft = pstParent;
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp1, pstSibling, RBTREE_COLOR_BLACK);
if (NULL != pstNodeTmp2)
RBTREE_SET_PARENT(pstNodeTmp2, pstParent);
pstNodeTmp = RBTREE_NODE_PARENT(pstParent);
pstSibling->ulRbParentColor = pstParent->ulRbParentColor;
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstSibling, RBTREE_COLOR_BLACK);
if (NULL == pstNodeTmp)
pstRoot->pstRootNode = pstSibling;
else {
if (pstNodeTmp->pstLeft == pstParent)
pstNodeTmp->pstLeft = pstSibling;
else
pstNodeTmp->pstRight = pstSibling;
}
break;
}
// node是右节点
else {
pstSibling = pstParent->pstLeft;
// 红兄弟 --> 转换成黑兄弟
if (RBTREE_COLOR_RED == RBTREE_NODE_COLOR(pstSibling)) {
pstParent->pstLeft = pstNodeTmp1 = pstSibling->pstRight;
pstSibling->pstRight = pstParent;
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp1, pstParent, RBTREE_COLOR_BLACK);
pstNodeTmp = RBTREE_NODE_PARENT(pstParent);
pstSibling->ulRbParentColor = pstParent->ulRbParentColor;
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstSibling, RBTREE_COLOR_RED);
if (NULL == pstNodeTmp)
pstRoot->pstRootNode = pstSibling;
else {
if (pstNodeTmp->pstLeft == pstParent)
pstNodeTmp->pstLeft = pstSibling;
else
pstNodeTmp->pstRight = pstSibling;
}
pstSibling = pstNodeTmp1;
}
//******************************** 黑兄弟的情况 *************************************
pstNodeTmp1 = pstSibling->pstLeft;
// 1. 左侄子为空或者黑
if ((NULL == pstNodeTmp1) || (RBTREE_COLOR_BLACK == RBTREE_NODE_COLOR(pstNodeTmp1))) {
pstNodeTmp2 = pstSibling->pstRight;
// 右侄子为空或者黑 ---> #### 把问题上推给父亲 ###
if ((NULL == pstNodeTmp2) || (RBTREE_COLOR_BLACK == RBTREE_NODE_COLOR(pstNodeTmp2))) {
RBTREE_SET_PARENT_AND_COLOR(pstSibling, pstParent, RBTREE_COLOR_RED);
if (RBTREE_COLOR_RED == RBTREE_NODE_COLOR(pstParent))
RBTREE_SET_BLACK(pstParent);
else {
pstNode = pstParent;
pstParent = RBTREE_NODE_PARENT(pstNode);
if (NULL != pstParent)
continue;
}
break;
}
// 右侄子为红, 左侄子为黑 ---> #### 转换成左红, 还没调整完毕 ###
pstSibling->pstRight = pstNodeTmp1 = pstNodeTmp2->pstLeft;
pstNodeTmp2->pstLeft = pstSibling;
pstParent->pstLeft = pstNodeTmp2;
if (NULL != pstNodeTmp1)
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp1, pstSibling, RBTREE_COLOR_BLACK);
pstNodeTmp1 = pstSibling;
pstSibling = pstNodeTmp2;
}
// 2. 左侄子为红, 右红左黑调整后需要按照这里继续处理
pstParent->pstLeft = pstNodeTmp2 = pstSibling->pstRight;
pstSibling->pstRight = pstParent;
RBTREE_SET_PARENT_AND_COLOR(pstNodeTmp1, pstSibling, RBTREE_COLOR_BLACK);
if (NULL != pstNodeTmp2)
RBTREE_SET_PARENT(pstNodeTmp2, pstParent);
pstNodeTmp = RBTREE_NODE_PARENT(pstParent);
pstSibling->ulRbParentColor = pstParent->ulRbParentColor;
RBTREE_SET_PARENT_AND_COLOR(pstParent, pstSibling, RBTREE_COLOR_BLACK);
if (NULL == pstNodeTmp)
pstRoot->pstRootNode = pstSibling;
else {
if (pstNodeTmp->pstLeft == pstParent)
pstNodeTmp->pstLeft = pstSibling;
else
pstNodeTmp->pstRight = pstSibling;
}
break;
}
}
}
YUDS_RBTREE_NODE_S *YuDS_rbtree_search(YUDS_RBTREE_ROOT_S *pstRoot, YUDS_RBTREE_NODE_S *pstNode)
{
int iCmpRet = 0;
YUDS_RBTREE_NODE_S *pstNodeTmp = pstRoot->pstRootNode;
YUDS_RBTREE_CMP_FUNC pfnCmp = pstRoot->pfnCmp;
while (NULL != pstNodeTmp) {
iCmpRet = pfnCmp(pstNodeTmp, pstNode);
if (iCmpRet > 0)
pstNodeTmp = pstNodeTmp->pstLeft;
else if (iCmpRet < 0)
pstNodeTmp = pstNodeTmp->pstRight;
else
return pstNodeTmp;
}
return NULL;
}
YUDS_RBTREE_NODE_S *YuDS_rbtree_getFirst(YUDS_RBTREE_ROOT_S *pstRoot)
{
YUDS_RBTREE_NODE_S *pstNode;
pstNode = pstRoot->pstRootNode;
if (NULL == pstNode)
return NULL;
while (NULL != pstNode->pstLeft)
pstNode = pstNode->pstLeft;
return pstNode;
}
YUDS_RBTREE_NODE_S *YuDS_rbtree_getLast(YUDS_RBTREE_ROOT_S *pstRoot)
{
YUDS_RBTREE_NODE_S *pstNode;
pstNode = pstRoot->pstRootNode;
if (NULL == pstNode)
return NULL;
while (NULL != pstNode->pstRight)
pstNode = pstNode->pstRight;
return pstNode;
}
YUDS_RBTREE_NODE_S *YuDS_rbtree_getNext(YUDS_RBTREE_NODE_S *pstNode, int iIsNodeInTree)
{
YUDS_RBTREE_NODE_S *pstParent;
if (0 == iIsNodeInTree) {
}
else {
if (NULL != pstNode->pstRight) {
pstNode = pstNode->pstRight;
while (NULL != pstNode->pstLeft)
pstNode = pstNode->pstLeft;
return pstNode;
}
while ((pstParent = RBTREE_NODE_PARENT(pstNode)) && pstNode == pstParent->pstRight)
pstNode = pstParent;
return pstParent;
}
}
YUDS_RBTREE_NODE_S *YuDS_rbtree_getPrev(YUDS_RBTREE_NODE_S *pstNode, int iIsNodeInTree)
{
YUDS_RBTREE_NODE_S *pstParent;
if (0 == iIsNodeInTree) {
}
else {
if (NULL != pstNode->pstLeft) {
pstNode = pstNode->pstLeft;
while (NULL != pstNode->pstRight)
pstNode = pstNode->pstRight;
return pstNode;
}
while ((pstParent = RBTREE_NODE_PARENT(pstNode)) && pstNode == pstParent->pstLeft)
pstNode = pstParent;
return pstParent;
}
}
void YuDS_rbtree_init(YUDS_RBTREE_ROOT_S *pstRoot, YUDS_RBTREE_CMP_FUNC pfnCmp)
{
pstRoot->pstRootNode = NULL;
pstRoot->pfnCmp = pfnCmp;
}
简单的测试：
#include <stdio.h>
#include <stdlib.h>
#include "YuDS_rbtree.h"
typedef struct my_node
{
YUDS_RBTREE_NODE_S stRbtreeNode;
int val;
}MY_NODE_S;
static YUDS_RBTREE_ROOT_S s_stRoot;
int cmp(YUDS_RBTREE_NODE_S *pstNodeInTree, YUDS_RBTREE_NODE_S *pstNode)
{
MY_NODE_S *pstAdd, *pstIntree;
pstIntree = YUDS_RBTREE_ENTRY(pstNodeInTree, MY_NODE_S, stRbtreeNode);
pstAdd = YUDS_RBTREE_ENTRY(pstNode, MY_NODE_S, stRbtreeNode);
return pstIntree->val - pstAdd->val;
}
static int s_array[] = {10, 4, 6, 19, 7, 8, 22, 11, 13, 5,
6, 8, 9, 88, 52,30,27, 19, 63, 69,
91, 85,76,98, 23,7, 99, 88, 2, 6};
int main()
{
int i, iRet;
int key;
MY_NODE_S *pstNode = NULL;
MY_NODE_S stNode;
YUDS_RBTREE_NODE_S *pstRet;
YuDS_rbtree_init(&s_stRoot, cmp);
printf("@@@ test add @@@
");
for (i = 0; i < 30; ++i)
{
key = s_array[i];
pstNode = malloc(sizeof(MY_NODE_S));
if (NULL == pstNode)
{
printf("malloc failed.
");
break;
}
pstNode->val = key;
iRet = YuDS_rbtree_add(&s_stRoot, &pstNode->stRbtreeNode, NULL);
if (0 != iRet)
{
printf("%d already exist.
", key);
}
}
printf("@@@ test search @@@
");
for (i = 0; i < 30; ++i)
{
key = s_array[i];
stNode.val = key;
pstRet = YuDS_rbtree_search(&s_stRoot, &stNode.stRbtreeNode);
if (NULL != pstRet)
{
pstNode = YUDS_RBTREE_ENTRY(pstRet, MY_NODE_S, stRbtreeNode);
printf("%d ", pstNode->val);
}
}
printf("
");
printf("@@@ test getFirst getNext @@@
");
for (pstRet = YuDS_rbtree_getFirst(&s_stRoot);
NULL != pstRet;
pstRet = YuDS_rbtree_getNext(pstRet, 1))
{
pstNode = YUDS_RBTREE_ENTRY(pstRet, MY_NODE_S, stRbtreeNode);
printf("%d ", pstNode->val);
}
printf("
");
printf("@@@ test getLast getPrev @@@
");
for (pstRet = YuDS_rbtree_getLast(&s_stRoot);
NULL != pstRet;
pstRet = YuDS_rbtree_getPrev(pstRet, 1))
if (NULL != pstRet)
{
pstNode = YUDS_RBTREE_ENTRY(pstRet, MY_NODE_S, stRbtreeNode);
printf("%d ", pstNode->val);
}
printf("
");
for (i = 0; i < 30; ++i)
{
stNode.val = s_array[i];
pstRet = YuDS_rbtree_search(&s_stRoot, &stNode.stRbtreeNode);
if (NULL != pstRet)
{
YuDS_rbtree_del(&s_stRoot, pstRet);
}
else
{
printf("YuDS_rbtree_search failed, val is %d.
", s_array[i]);
}
}
printf("@@@ test getFirst getNext @@@
");
for (pstRet = YuDS_rbtree_getFirst(&s_stRoot);
NULL != pstRet;
pstRet = YuDS_rbtree_getNext(pstRet, 1))
{
pstNode = YUDS_RBTREE_ENTRY(pstRet, MY_NODE_S, stRbtreeNode);
printf("%d ", pstNode->val);
}
printf("
");
return 0;
}
执行结果如下：
@@@ test add @@@
6 already exist.
8 already exist.
19 already exist.
7 already exist.
88 already exist.
6 already exist.
@@@ test search @@@
10 4 6 19 7 8 22 11 13 5 6 8 9 88 52 30 27 19 63 69 91 85 76 98 23 7 99 88 2 6
@@@ test getFirst getNext @@@
2 4 5 6 7 8 9 10 11 13 19 22 23 27 30 52 63 69 76 85 88 91 98 99
@@@ test getLast getPrev @@@
99 98 91 88 85 76 69 63 52 30 27 23 22 19 13 11 10 9 8 7 6 5 4 2
@@@ test getFirst getNext @@@
2 9 23 27 30 52 63 69 76 85 88 91 98 99