红黑树实现源码(C++)

本文展示红黑树的源码，源码是作者由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用户开发手册》

原文链接：https://blog.csdn.net/freeland008/article/details/107259793

你可能也喜欢