欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

红黑树实现源码(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用户开发手册》