红黑树实现源码(C++)
程序员文章站
2022-05-29 23:45:41
...
本文展示红黑树的源码,源码是作者由linux内核代码封装成C++类,然后再次封装成API函数的方式。
RBTree.h和RBTree.cpp是用c++类的方式实现了红黑树的封装,RbtAPI.h、RbtAPI.cpp实现了二次封装,更方便开发人员直接使用。
1、RBTree.h
#ifndef RBTREE_H
#define RBTREE_H
#include "RbtAPI.h"
#define RB_RED 0
#define RB_BLACK 1
typedef struct rb_node
{
rb_node* pParent;
rb_node* rchild;
rb_node* lchild;
void* pKey; // 键值
HANDLE hValue; // 用户数据
unsigned char nColor;
}RBTNODE;
typedef RBTNODE* LPRBTNODE;
class CRBTree
{
public:
LPRBTNODE m_pRoot;
size_t m_nCount;
ONRBTCOMPARE m_fpOnCompare;
public:
CRBTree();
~CRBTree();
void Constructor();
void Destructor();
public:
bool AvlAddKey(void* pKey, HANDLE hValue, LPRBTNODE& pNewNode);
bool AvlRemoveKey(void* pKey, HANDLE& hValue, void*& pPosKey);// 根据主键删除一个节点
LPRBTNODE AvlGetKeyPosition(void* pKey);
void AvlRemovePosition(LPRBTNODE node);
public:
void RemoveNode(struct rb_node *node);
static LPRBTNODE GetMinNode(LPRBTNODE tree);
static LPRBTNODE GetMaxNode(LPRBTNODE tree);
public:
void __rb_rotate_left(struct rb_node *node);
void __rb_rotate_right(struct rb_node *node);
void rb_insert_color(struct rb_node *node);
void __rb_erase_color(struct rb_node *node, struct rb_node *parent);
public:
LPRBTNODE AvlGetHeadPosition();
static LPRBTNODE AvlGetNextPosition(LPRBTNODE pNode);
static LPRBTNODE AvlGetPrevPosition(LPRBTNODE pNode);
LPRBTNODE AvlGetTailPosition();
// 查询第一个满足以下条件的节点
LPRBTNODE AvlGetFirstPosGEKey(void* pKey); // 节点值 >= pKey
LPRBTNODE AvlGetFirstPosGTKey(void* pKey); // 节点值 > pKey
LPRBTNODE AvlGetFirstPosSEKey(void* pKey); // 节点值 <= pKey
LPRBTNODE AvlGetFirstPosSTKey(void* pKey); // 节点值 < pKey
// 获取节点总数
size_t AvlGetCount();
// 清除所有节点
void AvlRemoveAll(ONRBTDELETE OnDelete = NULL, void* pInputPara = NULL);
bool AvlRemoveHead(HANDLE& hValue, void*& pPosKey);
bool AvlRemoveTail(HANDLE& hValue, void*& pPosKey);
LPRBTNODE GetRoot(){return m_pRoot;};
private:
static LPRBTNODE GetNodeGEKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeGEKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeGEKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
// >
static LPRBTNODE GetNodeGTKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeGTKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeGTKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
// <=
static LPRBTNODE GetNodeSEKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeSEKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeSEKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
// <
static LPRBTNODE GetNodeSTKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeSTKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static LPRBTNODE GetNodeSTKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp);
static void RemoveAll(LPRBTNODE pRoot, ONRBTDELETE OnDelete = NULL, void* pInputPara = NULL);
};
#define rb_parent(r) (r->pParent)
#define rb_color(r) (r->nColor)
#define rb_is_red(r) (!(r->nColor))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r) do { r->nColor = RB_RED; } while (0)
#define rb_set_black(r) do { r->nColor = RB_BLACK; } while (0)
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
rb->pParent = p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
rb->nColor = color;
}
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link)
{
node->pParent = parent;
node->lchild = node->rchild = NULL;
*rb_link = node;
}
static LPRBTNODE NewRbtNode();
static void DeleteRbtNode(LPRBTNODE pNode);
CRBTree* NewRBTree();
void DeleteRBTree(CRBTree* pTree);
#endif
2、RBTree.cpp
#include "StdAfx.h"
#include "RBTree.h"
#include <string.h>
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include "MemAPI.h"
CRBTree :: CRBTree()
{
Constructor();
}
CRBTree :: ~CRBTree()
{
}
void CRBTree :: Constructor()
{
m_pRoot = NULL;
m_nCount = 0;
m_fpOnCompare = NULL;
}
void CRBTree :: Destructor()
{
}
size_t CRBTree :: AvlGetCount()
{
return m_nCount;
}
bool CRBTree :: AvlRemoveHead(HANDLE& hValue, void*& pPosKey)
{
LPRBTNODE pNode;
pNode = GetMinNode(m_pRoot);
if(pNode == NULL)
{
pPosKey = NULL;
hValue = NULL;
return false;
}
pPosKey = pNode->pKey;
hValue = pNode->hValue;
AvlRemovePosition(pNode);
return true;
}
bool CRBTree :: AvlRemoveTail(HANDLE& hValue, void*& pPosKey)
{
LPRBTNODE pNode;
pNode = GetMaxNode(m_pRoot);
if(pNode == NULL)
{
hValue = NULL;
pPosKey = NULL;
return false;
}
pPosKey = pNode->pKey;
hValue = pNode->hValue;
AvlRemovePosition(pNode);
return true;
}
void CRBTree :: AvlRemoveAll(ONRBTDELETE OnDelete, void* pInputPara)
{
RemoveAll(m_pRoot, OnDelete, pInputPara);
m_pRoot = NULL;
m_nCount = 0;
}
//二叉树的消毁操作
//消毁函数,用来消毁二叉树中的各个结点
void CRBTree :: RemoveAll(LPRBTNODE pRoot, ONRBTDELETE OnDelete, void* pInputPara)
{
if(pRoot != NULL)
{
RemoveAll(pRoot->lchild, OnDelete, pInputPara);
RemoveAll(pRoot->rchild, OnDelete, pInputPara);
if(OnDelete != NULL)
{
OnDelete(pRoot, pInputPara);
}
DeleteRbtNode(pRoot);
}
}
void CRBTree :: __rb_rotate_left(struct rb_node *node)
{
struct rb_node *right = node->rchild;
struct rb_node *parent = rb_parent(node);
if ((node->rchild = right->lchild))
rb_set_parent(right->lchild, node);
right->lchild = node;
rb_set_parent(right, parent);
if (parent)
{
if (node == parent->lchild)
parent->lchild = right;
else
parent->rchild = right;
}
else
m_pRoot = right;
rb_set_parent(node, right);
}
void CRBTree :: __rb_rotate_right(struct rb_node *node)
{
struct rb_node *left = node->lchild;
struct rb_node *parent = rb_parent(node);
if ((node->lchild = left->rchild))
rb_set_parent(left->rchild, node);
left->rchild = node;
rb_set_parent(left, parent);
if (parent)
{
if (node == parent->rchild)
parent->rchild = left;
else
parent->lchild = left;
}
else
m_pRoot = left;
rb_set_parent(node, left);
}
void CRBTree :: rb_insert_color(struct rb_node *node)
{
struct rb_node *parent, *gparent;
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
gparent = rb_parent(parent);
if (parent == gparent->lchild)
{
{
register struct rb_node *uncle = gparent->rchild;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rchild == node)
{
register struct rb_node *tmp;
__rb_rotate_left(parent);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_right(gparent);
} else {
{
register struct rb_node *uncle = gparent->lchild;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->lchild == node)
{
register struct rb_node *tmp;
__rb_rotate_right(parent);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_left(gparent);
}
}
rb_set_black(m_pRoot);
}
void CRBTree :: __rb_erase_color(struct rb_node *node, struct rb_node *parent)
{
struct rb_node *other;
while ((!node || rb_is_black(node)) && node != m_pRoot)
{
if (parent->lchild == node)
{
other = parent->rchild;
if (rb_is_red(other))
{
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_left(parent);
other = parent->rchild;
}
if ((!other->lchild || rb_is_black(other->lchild)) &&
(!other->rchild || rb_is_black(other->rchild)))
{
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->rchild || rb_is_black(other->rchild))
{
rb_set_black(other->lchild);
rb_set_red(other);
__rb_rotate_right(other);
other = parent->rchild;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rchild);
__rb_rotate_left(parent);
node = m_pRoot;
break;
}
}
else
{
other = parent->lchild;
if (rb_is_red(other))
{
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_right(parent);
other = parent->lchild;
}
if ((!other->lchild || rb_is_black(other->lchild)) &&
(!other->rchild || rb_is_black(other->rchild)))
{
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->lchild || rb_is_black(other->lchild))
{
rb_set_black(other->rchild);
rb_set_red(other);
__rb_rotate_left(other);
other = parent->lchild;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->lchild);
__rb_rotate_right(parent);
node = m_pRoot;
break;
}
}
}
if (node)
rb_set_black(node);
}
void CRBTree :: AvlRemovePosition(struct rb_node *node)
{
RemoveNode(node);
DeleteRbtNode(node);
m_nCount--;
}
void CRBTree :: RemoveNode(struct rb_node *node)
{
struct rb_node *child, *parent;
int color;
if (!node->lchild)
child = node->rchild;
else if (!node->rchild)
child = node->lchild;
else
{
struct rb_node *old = node, *left;
node = node->rchild;
while ((left = node->lchild) != NULL)
node = left;
if (rb_parent(old)) {
if (rb_parent(old)->lchild == old)
rb_parent(old)->lchild = node;
else
rb_parent(old)->rchild = node;
} else
m_pRoot = node;
child = node->rchild;
parent = rb_parent(node);
color = rb_color(node);
if (parent == old) {
parent = node;
} else {
if (child)
rb_set_parent(child, parent);
parent->lchild = child;
node->rchild = old->rchild;
rb_set_parent(old->rchild, node);
}
//////////////////////////////////////////////////////////////////////////
//node->rb_parent_color = old->rb_parent_color;
node->nColor = old->nColor;
node->pParent = old->pParent;
//////////////////////////////////////////////////////////////////////////
node->lchild = old->lchild;
rb_set_parent(old->lchild, node);
goto color;
}
parent = rb_parent(node);
color = rb_color(node);
if (child)
rb_set_parent(child, parent);
if (parent)
{
if (parent->lchild == node)
parent->lchild = child;
else
parent->rchild = child;
}
else
m_pRoot = child;
color:
if (color == RB_BLACK)
__rb_erase_color(child, parent);
}
struct rb_node* CRBTree :: GetMinNode(LPRBTNODE pRoot)
{
struct rb_node *n;
n = pRoot;
if (!n)
return NULL;
while (n->lchild)
n = n->lchild;
return n;
}
LPRBTNODE CRBTree :: GetMaxNode(LPRBTNODE pRoot)
{
if(pRoot == NULL)
{
return NULL;
}
LPRBTNODE t;
t = pRoot;
while (t->rchild != NULL)
{
t = t->rchild;
}
return t;
}
LPRBTNODE CRBTree :: AvlGetNextPosition(LPRBTNODE pNode)
{
if(pNode->pParent == NULL)
{ // 是根节点
if(pNode->rchild != NULL)
{ // pNode存在非空的右节点
return(GetMinNode(pNode->rchild));
}
else
{
return NULL;
}
}
if(pNode->rchild != NULL)
{ // 有右子节点
return(GetMinNode(pNode->rchild));
}
if(pNode->pParent->lchild == pNode)
{ // pNode是父节点的左节点
return pNode->pParent;
}
if(pNode->pParent->rchild == pNode)
{ // pNode是父节点的右节点
if(pNode->rchild != NULL)
{ // pNode存在非空的右节点
return(GetMinNode(pNode->rchild));
}
LPRBTNODE pParent;
pParent = pNode->pParent;
while(true)
{
if(pParent->pParent == NULL)
{
return NULL;
}
if(pParent->pParent->lchild == pParent)
{
return pParent->pParent;
}
pParent = pParent->pParent;
}
}
return NULL;
}
LPRBTNODE CRBTree :: AvlGetPrevPosition(LPRBTNODE pNode)
{
if(pNode->pParent == NULL)
{ // 是根节点
if(pNode->lchild != NULL)
{ // pNode存在非空的左节点
return(GetMaxNode(pNode->lchild));
}
else
{
return NULL;
}
}
if(pNode->lchild != NULL)
{ // 有左子节点
return(GetMaxNode(pNode->lchild));
}
if(pNode->pParent->rchild == pNode)
{ // pNode是父节点的右节点
return pNode->pParent;
}
if(pNode->pParent->lchild == pNode)
{ // pNode是父节点的左节点
if(pNode->lchild != NULL)
{ // pNode存在非空的左节点
return(GetMaxNode(pNode->lchild));
}
LPRBTNODE pParent;
pParent = pNode->pParent;
while(true)
{
if(pParent->pParent == NULL)
{
return NULL;
}
if(pParent->pParent->rchild == pParent)
{
return pParent->pParent;
}
pParent = pParent->pParent;
}
}
return NULL;
}
LPRBTNODE CRBTree :: AvlGetHeadPosition()
{
return(GetMinNode(m_pRoot));
}
LPRBTNODE CRBTree :: AvlGetTailPosition()
{
return(GetMaxNode(m_pRoot));
}
LPRBTNODE CRBTree :: GetNodeSTKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{
if(pRoot == NULL)
{
return NULL;
}
int nRet;
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{ // 获取上一个节点
return AvlGetPrevPosition(pRoot);
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在m_pRoot的左树查找
return(GetNodeSTKey_Left(pRoot->lchild, pKey, fp));
}
else
{ // 节点pRoot < pKey,在m_pRoot的右树查找
return(GetNodeSTKey_Right(pRoot/*->rchild*/, pKey, fp));
}
}
LPRBTNODE CRBTree :: GetNodeGTKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{
if(pRoot == NULL)
{
return NULL;
}
int nRet;
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{ // 获取下一个节点
return AvlGetNextPosition(pRoot);
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在m_pRoot的左树查找
return(GetNodeGTKey_Left(pRoot/*->lchild*/, pKey, fp));
}
else
{ // 节点pRoot < pKey,在m_pRoot的右树查找
return(GetNodeGTKey_Right(pRoot->rchild, pKey, fp));
}
}
LPRBTNODE CRBTree :: GetNodeGTKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 左树查找 > pKey 的节点
LPRBTNODE pHigherSmall; // 最大的那个满足条件的节点
pHigherSmall = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{ // 获取下一个节点
return AvlGetNextPosition(pRoot);
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
pHigherSmall = pRoot;
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
return pRoot;
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
if(pRoot->rchild == NULL)
{ // 肯定是找不到满足条件的了
return pHigherSmall;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
LPRBTNODE CRBTree :: GetNodeSEKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 左树查找 < pKey 的节点
LPRBTNODE pUpperSmall; // 最大的那个满足条件的节点
pUpperSmall = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{
return pRoot;
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
return pUpperSmall;
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
pUpperSmall = pRoot;
if(pRoot->rchild == NULL)
{ // 肯定是找不到满足条件的了
return pRoot;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
LPRBTNODE CRBTree :: GetNodeSEKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 右树查找 < pKey 的节点
LPRBTNODE pUpperBig; // 最小的那个满足条件的节点
pUpperBig = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{ //
return pRoot;
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
return pUpperBig;
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
pUpperBig = pRoot;
if(pRoot->rchild == NULL)
{ //
return pRoot;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
LPRBTNODE CRBTree :: GetNodeGTKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 右树查找 > pKey 的节点
LPRBTNODE pLowerBig; // 最小的那个满足条件的节点
pLowerBig = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{ // 获取最小值节点(且 > pKey)
return AvlGetNextPosition(pRoot);
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
pLowerBig = pRoot;
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
return pRoot;
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
if(pRoot->rchild == NULL)
{ //
return pLowerBig;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
LPRBTNODE CRBTree :: AvlGetFirstPosGTKey(void* pKey)
{
return(GetNodeGTKey(m_pRoot, pKey, m_fpOnCompare));
}
LPRBTNODE CRBTree :: AvlGetFirstPosGEKey(void* pKey)
{
return(GetNodeGEKey(m_pRoot, pKey, m_fpOnCompare));
}
LPRBTNODE CRBTree :: AvlGetFirstPosSEKey(void* pKey)
{
return(GetNodeSEKey(m_pRoot, pKey, m_fpOnCompare));
}
LPRBTNODE CRBTree :: AvlGetFirstPosSTKey(void* pKey)
{
return(GetNodeSTKey(m_pRoot, pKey, m_fpOnCompare));
}
LPRBTNODE CRBTree :: GetNodeGEKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{
if(pRoot == NULL)
{
return NULL;
}
int nRet;
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{
return pRoot;
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在m_pRoot的左树查找
return(GetNodeGEKey_Left(pRoot/*->lchild*/, pKey, fp));
}
else
{ // 节点pRoot < pKey,在m_pRoot的右树查找
return(GetNodeGEKey_Right(pRoot->rchild, pKey, fp));
}
}
LPRBTNODE CRBTree :: GetNodeSEKey(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{
if(pRoot == NULL)
{
return NULL;
}
int nRet;
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{
return pRoot;
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在m_pRoot的左树查找
return(GetNodeSEKey_Left(pRoot->lchild, pKey, fp));
}
else
{ // 节点pRoot < pKey,在m_pRoot的右树查找
return(GetNodeSEKey_Right(pRoot/*->rchild*/, pKey, fp));
}
}
LPRBTNODE CRBTree :: GetNodeGEKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 左树查找 >= pKey 的节点
LPRBTNODE pHigherSmall; // 最大的那个满足条件的节点
pHigherSmall = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{
return pRoot;
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
pHigherSmall = pRoot;
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
return pRoot;
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
if(pRoot->rchild == NULL)
{ // 肯定是找不到满足条件的了
return pHigherSmall;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
LPRBTNODE CRBTree :: GetNodeGEKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 右树查找 >= pKey 的节点
LPRBTNODE pLowerBig; // 最小的那个满足条件的节点
pLowerBig = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{
return pRoot;
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
pLowerBig = pRoot;
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
return pRoot;
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
if(pRoot->rchild == NULL)
{ //
return pLowerBig;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
LPRBTNODE CRBTree :: GetNodeSTKey_Right(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 右树查找 < pKey 的节点
LPRBTNODE pUpperBig; // 最小的那个满足条件的节点
pUpperBig = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{ //
return AvlGetPrevPosition(pRoot);
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
if(pUpperBig == NULL)
{
return pRoot;
}
else
{
return pUpperBig;
}
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
pUpperBig = pRoot;
if(pRoot->rchild == NULL)
{ //
return pRoot;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
LPRBTNODE CRBTree :: GetNodeSTKey_Left(LPRBTNODE pRoot, void* pKey, ONRBTCOMPARE fp)
{ // 左树查找 < pKey 的节点
LPRBTNODE pUpperSmall; // 最大的那个满足条件的节点
pUpperSmall = NULL;
int nRet;
while(pRoot != NULL)
{
nRet = fp(pRoot->pKey, pKey);
if(nRet == 0)
{
return AvlGetPrevPosition(pRoot);
}
else if(nRet > 0)
{ // 节点pRoot > pKey,在pRoot的左树查找
if(pRoot->lchild == NULL)
{ // pRoot没有左节点,pRoot是最小的节点
return pUpperSmall;
}
else
{
pRoot = pRoot->lchild;
}
}
else
{ // 节点pRoot < pKey,在pRoot的右树查找 >= pKey
pUpperSmall = pRoot;
if(pRoot->rchild == NULL)
{ // 肯定是找不到满足条件的了
return pRoot;
}
else
{ // 在pRoot的右树中查找
pRoot = pRoot->rchild;
}
}
}
return NULL;
}
//////////////////////////////////////////////////////////////////////////
LPRBTNODE CRBTree :: AvlGetKeyPosition(void* pKey)
{
struct rb_node *node = m_pRoot;
while (node)
{
int nRet;
nRet = m_fpOnCompare(node->pKey, pKey);
if (nRet > 0)
node = node->lchild;
else if (nRet < 0)
node = node->rchild;
else
return node;
}
return NULL;
}
bool CRBTree :: AvlAddKey(void* pKey, HANDLE hValue, LPRBTNODE& pNewNode)
{
struct rb_node **New = &(m_pRoot), *parent = NULL;
while (*New)
{
parent = *New;
int nRet;
nRet = m_fpOnCompare((*New)->pKey, pKey);
if (nRet > 0)
{
New =&((*New)->lchild);
}
else if (nRet < 0)
{
New =&((*New)->rchild);
}
else
{
pNewNode = *New;
return false;
}
}
struct rb_node* pNode = NewRbtNode();
pNode->pKey = pKey;
pNode->hValue = hValue;
rb_link_node(pNode, parent, New);
rb_insert_color(pNode);
//////////////////////////////////////////////////////////////////////////
pNewNode = pNode;
m_nCount++;
return true;
}
bool CRBTree :: AvlRemoveKey(void* pKey, HANDLE& hValue, void*& pPosKey)
{
hValue = NULL;
pPosKey = NULL;
struct rb_node* pNode;
pNode = AvlGetKeyPosition(pKey);
if(pNode == NULL)
{
return false;
}
else
{
hValue = pNode->hValue;
pPosKey = pNode->pKey;
RemoveNode(pNode);
DeleteRbtNode(pNode);
m_nCount--;
return true;
}
}
LPRBTNODE NewRbtNode()
{
LPRBTNODE pNode;
pNode = (LPRBTNODE)(MMAlloc(sizeof(RBTNODE)));
memset(pNode, 0, sizeof(struct rb_node));
return pNode;
}
void DeleteRbtNode(LPRBTNODE pNode)
{
MMFree(pNode, 0);
}
CRBTree* NewRBTree()
{
CRBTree* pTree;
pTree = (CRBTree *)MMAlloc(sizeof(CRBTree));
pTree->Constructor();
return pTree;
}
void DeleteRBTree(CRBTree* pTree)
{
pTree->AvlRemoveAll();
MMFree(pTree, 0);
}
3、RbtAPI.h
#ifndef RBTAPI_H
#define RBTAPI_H
#include <stdio.h>
typedef void* HANDLE;
typedef void* POSITION;
typedef int (* ONRBTCOMPARE)(void* pNodeKey, void* pOutKey);
typedef bool (* ONRBTDELETE)(POSITION pos, void* pInputPara);
#define RBTAPI extern "C" __declspec(dllexport)
RBTAPI HANDLE RbtCreateTree(ONRBTCOMPARE OnCompare);
RBTAPI void RbtDeleteTree(HANDLE hTree, ONRBTDELETE OnDelete = NULL, void* pInputPara = NULL);
RBTAPI void RbtRemoveAll(HANDLE hTree, ONRBTDELETE OnDelete = NULL, void* pInputPara = NULL);
RBTAPI bool RbtAddKey(HANDLE hTree, void* pKey, HANDLE hValue, POSITION& pos);
RBTAPI bool RbtRemoveKey(HANDLE hTree, void* pKey, HANDLE& hValue);
RBTAPI bool RbtRemoveKeyEx(HANDLE hTree, void* pKey, HANDLE& hValue, void*& pPosKey);
RBTAPI bool RbtGetKeyValue(HANDLE hTree, void* pKey, HANDLE& hValue);
RBTAPI bool RbtGetHead(HANDLE hTree, HANDLE& hValue);
RBTAPI bool RbtGetTail(HANDLE hTree, HANDLE& hValue);
RBTAPI bool RbtGetHeadEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey);
RBTAPI bool RbtGetTailEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey);
RBTAPI POSITION RbtGetKeyPosition(HANDLE hTree, void* pKey);
RBTAPI POSITION RbtGetHeadPosition(HANDLE hTree);
RBTAPI POSITION RbtGetTailPosition(HANDLE hTree);
RBTAPI POSITION RbtGetNextPosition(HANDLE hTree, POSITION pos);
RBTAPI POSITION RbtGetPrevPosition(HANDLE hTree, POSITION pos);
RBTAPI HANDLE RbtGetNext(HANDLE hTree, POSITION& pos);
RBTAPI HANDLE RbtGetPrev(HANDLE hTree, POSITION& pos);
RBTAPI bool RbtRemoveHead(HANDLE hTree, HANDLE& hValue);
RBTAPI bool RbtRemoveTail(HANDLE hTree, HANDLE& hValue);
RBTAPI bool RbtRemoveHeadEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey);
RBTAPI bool RbtRemoveTailEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey);
RBTAPI void RbtRemoveAt(HANDLE hTree, POSITION pos);
RBTAPI POSITION RbtGetFirstPosGEKey(HANDLE hTree, void* pKey); // 节点值 >= pKey
RBTAPI POSITION RbtGetFirstPosGTKey(HANDLE hTree, void* pKey); // 节点值 > pKey
RBTAPI POSITION RbtGetFirstPosSEKey(HANDLE hTree, void* pKey); // 节点值 <= pKey
RBTAPI POSITION RbtGetFirstPosSTKey(HANDLE hTree, void* pKey); // 节点值 < pKey
RBTAPI size_t RbtGetCount(HANDLE hTree);
RBTAPI void* RbtGetPosKey(POSITION pos);
RBTAPI HANDLE RbtGetPosValue(POSITION pos);
RBTAPI int RbtGetPosColor(POSITION pos);
RBTAPI void RbtSetPosValue(POSITION pos, HANDLE hValue);
//////////////////////////////////////////////////////////////////////////
RBTAPI POSITION RbtGetRoot(HANDLE hTree);
RBTAPI POSITION RbtGetParent(POSITION pos);
RBTAPI POSITION RbtGetLeftChild(POSITION pos);
RBTAPI POSITION RbtGetRightChild(POSITION pos);
#endif
4、RbtAPI.cpp
#include "StdAfx.h"
#include "RbtAPI.h"
#include "RBTree.h"
RBTAPI HANDLE RbtCreateTree(ONRBTCOMPARE OnCompare)
{
CRBTree* pAlvTree;
pAlvTree = NewRBTree();
pAlvTree->m_fpOnCompare = OnCompare;
return pAlvTree;
}
RBTAPI void RbtDeleteTree(HANDLE hTree, ONRBTDELETE OnDelete, void* pInputPara)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
pAlvTree->AvlRemoveAll(OnDelete, pInputPara);
DeleteRBTree(pAlvTree);
}
RBTAPI void RbtRemoveAll(HANDLE hTree, ONRBTDELETE OnDelete, void* pInputPara)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
pAlvTree->AvlRemoveAll(OnDelete, pInputPara);
}
RBTAPI bool RbtAddKey(HANDLE hTree, void* pKey, HANDLE hValue, POSITION& pos)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
LPRBTNODE pNewNode;
bool bOK;
bOK = pAlvTree->AvlAddKey(pKey, hValue, pNewNode);
pos = pNewNode;
return bOK;
}
RBTAPI bool RbtRemoveKey(HANDLE hTree, void* pKey, HANDLE& hValue)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
void* pPosKey;
return(pAlvTree->AvlRemoveKey(pKey, hValue, pPosKey));
}
RBTAPI bool RbtRemoveKeyEx(HANDLE hTree, void* pKey, HANDLE& hValue, void*& pPosKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlRemoveKey(pKey, hValue, pPosKey));
}
RBTAPI void RbtRemoveAt(HANDLE hTree, POSITION pos)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
pAlvTree->AvlRemovePosition((LPRBTNODE)pos);
}
RBTAPI bool RbtGetKeyValue(HANDLE hTree, void* pKey, HANDLE& hValue)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
LPRBTNODE pNode;
pNode = pAlvTree->AvlGetKeyPosition(pKey);
if(pNode == NULL)
{
hValue = NULL;
return false;
}
hValue = pNode->hValue;
return true;
}
RBTAPI POSITION RbtGetKeyPosition(HANDLE hTree, void* pKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
LPRBTNODE pNode;
pNode = pAlvTree->AvlGetKeyPosition(pKey);
return pNode;
}
RBTAPI bool RbtGetHead(HANDLE hTree, HANDLE& hValue)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
LPRBTNODE pNode;
pNode = (LPRBTNODE)(pAlvTree->AvlGetHeadPosition());
if(pNode == NULL)
{
hValue = NULL;
return false;
}
hValue = pNode->hValue;
return true;
}
RBTAPI bool RbtGetHeadEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
LPRBTNODE pNode;
pNode = (LPRBTNODE)(pAlvTree->AvlGetHeadPosition());
if(pNode == NULL)
{
pPosKey = NULL;
hValue = NULL;
return false;
}
pPosKey = pNode->pKey;
hValue = pNode->hValue;
return true;
}
RBTAPI bool RbtGetTail(HANDLE hTree, HANDLE& hValue)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
LPRBTNODE pNode;
pNode = (LPRBTNODE)(pAlvTree->AvlGetTailPosition());
if(pNode == NULL)
{
hValue = NULL;
return false;
}
hValue = pNode->hValue;
return true;
}
RBTAPI bool RbtGetTailEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
LPRBTNODE pNode;
pNode = (LPRBTNODE)(pAlvTree->AvlGetTailPosition());
if(pNode == NULL)
{
pPosKey = NULL;
hValue = NULL;
return false;
}
pPosKey = pNode->pKey;
hValue = pNode->hValue;
return true;
}
RBTAPI POSITION RbtGetTailPosition(HANDLE hTree)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetTailPosition());
}
RBTAPI POSITION RbtGetHeadPosition(HANDLE hTree)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetHeadPosition());
}
RBTAPI POSITION RbtGetNextPosition(HANDLE hTree, POSITION pos)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetNextPosition(LPRBTNODE(pos)));
}
RBTAPI HANDLE RbtGetNext(HANDLE hTree, POSITION& pos)
{
CRBTree* pTree;
pTree = (CRBTree*)(hTree);
LPRBTNODE pNode;
pNode = (LPRBTNODE)pos;
pos = pTree->AvlGetNextPosition(pNode);
return pNode->hValue;
}
RBTAPI POSITION RbtGetPrevPosition(HANDLE hTree, POSITION pos)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetPrevPosition(LPRBTNODE(pos)));
}
RBTAPI HANDLE RbtGetPrev(HANDLE hTree, POSITION& pos)
{
CRBTree* pTree;
pTree = (CRBTree*)(hTree);
LPRBTNODE pNode;
pNode = (LPRBTNODE)pos;
pos = pTree->AvlGetPrevPosition(pNode);
return pNode->hValue;
}
RBTAPI POSITION RbtGetFirstPosGEKey(HANDLE hTree, void* pKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetFirstPosGEKey(pKey));
}
RBTAPI POSITION RbtGetFirstPosGTKey(HANDLE hTree, void* pKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetFirstPosGTKey(pKey));
}
RBTAPI POSITION RbtGetFirstPosSEKey(HANDLE hTree, void* pKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetFirstPosSEKey(pKey));
}
RBTAPI POSITION RbtGetFirstPosSTKey(HANDLE hTree, void* pKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetFirstPosSTKey(pKey));
}
RBTAPI size_t RbtGetCount(HANDLE hTree)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlGetCount());
}
RBTAPI HANDLE RbtGetPosValue(POSITION pos)
{
LPRBTNODE pNode;
pNode = LPRBTNODE(pos);
return pNode->hValue;
}
RBTAPI void* RbtGetPosKey(POSITION pos)
{
LPRBTNODE pNode;
pNode = LPRBTNODE(pos);
return pNode->pKey;
}
RBTAPI int RbtGetPosColor(POSITION pos)
{
LPRBTNODE pNode;
pNode = LPRBTNODE(pos);
return pNode->nColor;
}
RBTAPI void RbtSetPosValue(POSITION pos, HANDLE hValue)
{
LPRBTNODE pNode;
pNode = LPRBTNODE(pos);
pNode->hValue = hValue;
}
RBTAPI bool RbtRemoveHead(HANDLE hTree, HANDLE& hValue)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
void* pPosKey;
return(pAlvTree->AvlRemoveHead(hValue, pPosKey));
}
RBTAPI bool RbtRemoveTail(HANDLE hTree, HANDLE& hValue)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
void* pPosKey;
return(pAlvTree->AvlRemoveTail(hValue, pPosKey));
}
RBTAPI bool RbtRemoveHeadEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlRemoveHead(hValue, pPosKey));
}
RBTAPI bool RbtRemoveTailEx(HANDLE hTree, HANDLE& hValue, void*& pPosKey)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return(pAlvTree->AvlRemoveTail(hValue, pPosKey));
}
RBTAPI POSITION RbtGetRoot(HANDLE hTree)
{
CRBTree* pAlvTree;
pAlvTree = (CRBTree *)hTree;
return pAlvTree->GetRoot();
}
RBTAPI POSITION RbtGetParent(POSITION pos)
{
LPRBTNODE pNode;
pNode = LPRBTNODE(pos);
return pNode->pParent;
}
RBTAPI POSITION RbtGetLeftChild(POSITION pos)
{
LPRBTNODE pNode;
pNode = LPRBTNODE(pos);
return pNode->lchild;
}
RBTAPI POSITION RbtGetRightChild(POSITION pos)
{
LPRBTNODE pNode;
pNode = LPRBTNODE(pos);
return pNode->rchild;
}
具体使用可参看作者编写的对应的《红黑树SDK用户开发手册》