高级搜索树-红黑树(RBTree)代码实现

代码实现

代码参考了《数据结构(c++语言版)》--清华大学邓俊辉

"RBTree.h"


#pragma once
//#include"pch.h"
#include<iostream>
//宏定义
#define IsRoot(x)( !((x)->pa) )
#define IsLChild(x)( !(IsRoot(x)) && (x)==(x)->pa->lc)
#define IsRChild(x)( !(IsRoot(x)) && (x)==(x)->pa->rc)
#define HasLChild(x)((x)->lc )
#define HasRChild(x)((x)->rc )
#define HasChild(x)(HasLChild(x) || HasRChild(x))
#define HasBothChild(x)(HasRChild(x) && HasLChild(x) )
#define IsLeaf(x)(! HasChild(x) )#define RBNodePos(x)RBNode<x> *
typedef enum{RED,BLACK}RBColor;//节点颜色
#define IsBlack(x)((!x)||(x)->color == BLACK)
#define IsRed(x)(! IsBlack(x))//非黑即红
//RBNode定义
template<typename T>
struct RBNode {
public:
T key;
RBColor color;
RBNodePos(T) pa;//pa -- parent
RBNodePos(T) lc;//lc -- left child
RBNodePos(T) rc;//rc -- right child
//构造函数
RBNode() :color(RED),pa(NULL), lc(NULL), rc(NULL) {}
RBNode(T elem, RBColor c=RED,RBNodePos(T) pa = NULL, RBNodePos(T) lc = NULL, RBNodePos(T) rc = NULL) :
key(elem), color(c), pa(pa), lc(lc), rc(rc) { }
};
//RBTree 定义
template<typename T>
class RBTree {
private:
RBNodePos(T) root;//树根
RBNodePos(T)hot;//一个内置变量，方便类内其他函数使用
public:
//构造函数和析构函数
RBTree() :root(NULL) {}
~RBTree() {}//遍历函数
void preOrder();//前序遍历
void inOrder();//中序遍历
void postOrder();//后序遍历
//操作函数
RBNodePos(T)search(const T &key);//查找函数，若存在值为key的节点返回相应节点，若不存在则返回NULL，基于searchIn函数实现
RBNodePos(T) insert(const T &key);//插入值为key的节点
bool remove(const T &key);//移除值为key的节点private:
void preOrder(RBNodePos(T) &x);//以x节点为root进行前序遍历
void inOrder(RBNodePos(T) &x);//以x节点为root进行中序遍历
void postOrder(RBNodePos(T) &x);//以x节点为root进行后序遍历
RBNodePos(T) adjust(RBNodePos(T) &x);//调整x、p = x->pa,和g = p->pa三个节点的结构,返回调整后得到的局部子树的树根
RBNodePos(T) searchIn(const T & key, RBNodePos(T) &x);//以x节点为root查找值为key的节点，hot为返回节点的父节点
void solveDoubleRed(RBNodePos(T) & x);//修正双红问题
void solveDoubleBlack(RBNodePos(T) & x);//修正双黑问题
};
//lc作为p的左子接入，lc可能为空
template<typename NodePos>
inline void attachAsLChild(NodePos p, NodePos lc) {
p->lc = lc;
if (lc)lc->pa = p;
}
//rc作为p的右子子接入，lc可能为空
template<typename NodePos>
inline void attachAsRChild(NodePos p, NodePos rc) {
p->rc = rc;
if (rc)rc->pa = p;
}template<typename T>
inline void RBTree<T>::preOrder(RBNodePos(T) & x)
{
if (!x)return;
char c = 'b';
if (x->color == RED)
c='r';
std::cout << x->key << "-"<<c<<" ";
preOrder(x->lc);
preOrder(x->rc);
}template<typename T>
inline void RBTree<T>::inOrder(RBNodePos(T) & x)
{
if (!x)return;
inOrder(x->lc);
char c = 'b';
if (x->color == RED)
c = 'r';
std::cout << x->key << "-" << c << " ";
inOrder(x->rc);
}template<typename T>
inline void RBTree<T>::postOrder(RBNodePos(T)& x)
{
if (!x)return;
postOrder(x->lc);
postOrder(x->rc);
char c = 'b';
if (x->color == RED)
c = 'r';
std::cout << x->key << "-" << c << " ";
}template<typename T>
inline void RBTree<T>::preOrder()
{
preOrder(root);
}template<typename T>
inline void RBTree<T>::inOrder()
{
inOrder(root);
}template<typename T>
inline void RBTree<T>::postOrder()
{
postOrder(root);
}//调整x、p = x->pa,和g = p->pa三个节点的结构,返回调整后得到的局部子树的树根
template<typename T>
inline RBNodePos(T) RBTree<T>::adjust(RBNodePos(T)& x){
RBNodePos(T) p = x->pa;
RBNodePos(T)g = p->pa;
RBNodePos(T)r = NULL;//r为调整后局部子树的树根
if (IsLChild(p) && IsLChild(x)) {
attachAsLChild(g, p->rc); attachAsRChild(p, g); r = p;
}
else if (IsRChild(p) && IsRChild(x)) {
attachAsRChild(g, p->lc); attachAsLChild(p, g);r = p;
}
else if (IsLChild(p) && IsRChild(x)) {
attachAsRChild(p, x->lc); attachAsLChild(g, x->rc);
attachAsLChild(x, p);attachAsRChild(x, g);
r = x;
}
else if (IsRChild(p) && IsLChild(x)) {
attachAsLChild(p, x->rc); attachAsRChild(g, x->lc);
attachAsLChild(x, g);attachAsRChild(x, p);
r = x;
}
return r;
}//以x节点为root查找值为key的节点，hot为返回节点的父节点
template<typename T>
inline RBNodePos(T) RBTree<T>::searchIn(const T & key, RBNodePos(T) &x)
{
if (!x || key == x->key)return x;
hot = x;
return searchIn(key, (key < x->key ? x->lc : x->rc));
}//查找函数，若存在值为key的节点返回相应节点，若不存在则返回相应父节点
template<typename T>
inline RBNodePos(T) RBTree<T>::search(const T & key)
{
return searchIn(key, root);
}//插入值为key的节点
template<typename T>
RBNodePos(T) RBTree<T>::insert(const T & key)
{
RBNodePos(T) x = search(key);
if (x)return x;//已经存在值为key的节点
//否则确认key不存在
if (!root)
x = root = new RBNode<T>(key,BLACK);
else {
x = new RBNode<T>(key);//插入节点默认为红色，以方便调整
if (x->key < hot->key)
attachAsLChild(hot, x);//根据search函数定义，hot为返回节点的父亲，即要插入节点的父亲
else
attachAsRChild(hot, x);
solveDoubleRed(x);//解决双红问题
}
return x;//返回新插入节点位置
}//删除值为key的节点
template<typename T>
bool RBTree<T>::remove(const T &key) {
RBNodePos(T)x = search(key);
if (!x)
return false;//不存在值为key的节点
RBNodePos(T)w = x;//w是实际被摘除节点，初值等于x
RBNodePos(T)succ = NULL;//succ为被摘除节点的接替者
if(HasBothChild(x)){//如果x左右子树均存在，此时将x与x中序遍历下的直接后继交换数据，然后摘除后继
w = x->rc;//w为x中序遍历下的直接后继
while (HasLChild(w))//找到直接后继
w = w->lc;
//交换两个节点的数据
T tmp = x->key;
x->key = w->key;
w->key = tmp;
//隔离节点w
RBNodePos(T)p = w->pa;
if (p == x)//若x正好为w的父亲，即p->rc == w (x= p)
p->rc = succ = w->rc;//w没有左孩子
else//否则p->lc ==w
p->lc = succ = w->rc;
}else {//否则
if (!HasLChild(x)) //如果x左子树为空
succ = x->rc;//直接用右子树代替x
else//如果x右子树为空
succ = x->lc;//直接用左子树代替x，注意这里succ!= NULL，因为x存在左子树
//隔离节点w
if (!IsRoot(w))//若w非根,则w父亲存在
IsLChild(w) ? w->pa->lc = succ : w->pa->rc = succ;
}
hot = w->pa;//hot为实际被摘除节点的父亲
if (succ)//若继承者不为NULL
succ->pa = hot;
if(!hot)//摘除的是根节点
root = succ;//用succ作为root
//delete w;//摘除w
//以上和BST的remove操作一致
//下面是RBTree独有的部分//根据上面BST的remove操作，最终实际被摘除的节点最多只有一个孩子（如果有两个孩子最终也会通过寻找后继操作转换为摘除只有一个节点的节点）
//同时根据RBTree的定义，若摘除节点为黑色，则其孩子（若存在）必定为红色，若摘除节点为红色，则其孩子（若存在）必定为黑色if (!hot) {//根据以上BST的remove操作，若刚刚摘除的是根节点，则可知w至多只有一个孩子
if (root)//如果root存在
root->color = BLACK;//将根节点染黑即可
return true;
}
if (IsRed(w))//若被摘除节点w为红色，则无影响
return true;
//否则被摘除节点w为黑色
if (succ && IsRed(succ)) {//如果接替者succ为红色（若succ为NULL，根据定义外部节点为黑色，不影响下列操作)------情况1
succ->color = BLACK;
return true;
}
//否则w和接替者succ都为黑色，出现双黑问题(succ可能为外部节点，但是不影响，因为外部节点也可当作黑色节点）
solveDoubleBlack(succ);//解决双黑问题 -------情况2
return true;
}//解决双红问题
template<typename T>
inline void RBTree<T>::solveDoubleRed(RBNodePos(T)& x)//注意节点x一定是红色
{
if (IsRoot(x)) {//若x已经为根
x->color = BLACK;//将x染黑
return;
}
RBNodePos(T)p = x->pa;
if (IsBlack(p))return;//如果x的父亲p为黑，则双红问题解决，可以停止调整
RBNodePos(T)g = p->pa;//否则p为红色，必有黑色父亲g
RBNodePos(T)u = (IsLChild(p) ? g->rc : g->lc);//u为p的兄弟
if (IsBlack(u)) {//若u为黑色
if (IsLChild(x) == IsLChild(p))//若x与其父亲同侧
p->color = BLACK;
else
x->color =BLACK;
g->color = RED;//g必定由黑色染为红色
//调整树形
RBNodePos(T)gg = g->pa;
RBNodePos(T) r = adjust(x);//r为调整后得到的子树的root
//将r与原树相连
if (!gg) {
root = r;
r->pa = NULL;
r->color = BLACK;
}
else {
if (r->key < gg->key)
attachAsLChild(gg, r);
else
attachAsRChild(gg, r);
}
}else {//否则u为红色
p->color = BLACK;
u->color = BLACK;
if (!IsRoot(g))g->color = RED;
solveDoubleRed(g);//继续调整g
}
}//解决双黑问题
template<typename T>
inline void RBTree<T>::solveDoubleBlack(RBNodePos(T) &r) {
RBNodePos(T) p = (r?r->pa:hot);//r的父亲p --parent
if (!p)return;
RBNodePos(T) s = ((r ==p->lc)? p->rc : p->lc);//r的兄弟 s --sibling
if (IsRed(s)) {//兄弟s为红,此时p必为黑----情况2.3
s->color = BLACK;
p->color = RED;
RBNodePos(T)g = p->pa;
RBNodePos(T) tmp_root = (IsLChild(s) ? adjust(s->lc) : adjust(s->rc));//调整树形
//将tmp_root与原树相连
if (!g) {
tmp_root->color = BLACK;
root = tmp_root;
tmp_root->pa = NULL;
}
else {
if (tmp_root->key < g->key)
attachAsLChild(g, tmp_root);
else
attachAsRChild(g, tmp_root);
}
solveDoubleBlack(r);//递归执行
}else {//兄弟s为黑
RBNodePos(T)t = NULL;//t为兄弟s的红孩子，左右皆红优先取左，皆黑为NULL
if (HasLChild(s) && IsRed(s->lc))t = s->lc;
else if (HasRChild(s) && IsRed(s->rc))t = s->rc;
if (t) {//如果兄弟s有红孩子-----情况2.1
RBColor old_color = p->color;//拷贝原子树根节点p的颜色
RBNodePos(T)g= p->pa;//g为p的父亲
RBNodePos(T) tmp_root = adjust(t);//调整子树，tmp_root为调整后得到的局部子树的树根
//将tmp_root与原树相连
if (!g) {
root = tmp_root;
tmp_root->color = BLACK;
tmp_root->pa = NULL;
}
else {
if (tmp_root->key < g->key)
attachAsLChild(g, tmp_root);
else
attachAsRChild(g, tmp_root);
}
//重新染色
tmp_root->color = old_color;
tmp_root->lc->color = tmp_root->rc->color = BLACK;
}else {//兄弟s没有红孩子
if (IsRed(p)) {//如果p为红----情况2.4
p->color = BLACK;//p转黑
s->color = RED;//s转红
}else {//否则p为黑，s和其孩子都为黑，r也为黑----情况2.2
s->color = RED;//s转红
solveDoubleBlack(p);//递归
}
}
}
}

"main.cpp"


//#include"pch.h"
#include"RBTree.h"
#include<iostream>
using namespace std;
int main() {
RBTree<int> t;
int n;
int tmp;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
t.insert(tmp);
cout << "PreOrder:";
t.preOrder();
cout << endl;
cout << "InOrder:";
t.inOrder();
cout << endl;
}
for (int i = 0; i < n; i++) {
cin >> tmp;
t.remove(tmp);
cout << "PreOrder:";
t.preOrder();
cout << endl;
cout << "InOrder:";
t.inOrder();
cout << endl;
}
}

测试实例

实例来源:红黑树从头至尾插入和删除结点的全程演示图

图片可以看上面的链接

以下是运行结果：

20// 插入节点个数
//插入节点
12
PreOrder:12-b
InOrder:12-b
1
PreOrder:12-b 1-r
InOrder:1-r 12-b
9
PreOrder:9-b 1-r 12-r
InOrder:1-r 9-b 12-r
2
PreOrder:9-b 1-b 2-r 12-b
InOrder:1-b 2-r 9-b 12-b
0
PreOrder:9-b 1-b 0-r 2-r 12-b
InOrder:0-r 1-b 2-r 9-b 12-b
11
PreOrder:9-b 1-b 0-r 2-r 12-b 11-r
InOrder:0-r 1-b 2-r 9-b 11-r 12-b
7
PreOrder:9-b 1-r 0-b 2-b 7-r 12-b 11-r
InOrder:0-b 1-r 2-b 7-r 9-b 11-r 12-b
19
PreOrder:9-b 1-r 0-b 2-b 7-r 12-b 11-r 19-r
InOrder:0-b 1-r 2-b 7-r 9-b 11-r 12-b 19-r
4
PreOrder:9-b 1-r 0-b 4-b 2-r 7-r 12-b 11-r 19-r
InOrder:0-b 1-r 2-r 4-b 7-r 9-b 11-r 12-b 19-r
15
PreOrder:9-b 1-r 0-b 4-b 2-r 7-r 12-r 11-b 19-b 15-r
InOrder:0-b 1-r 2-r 4-b 7-r 9-b 11-b 12-r 15-r 19-b
18
PreOrder:9-b 1-r 0-b 4-b 2-r 7-r 12-r 11-b 18-b 15-r 19-r
InOrder:0-b 1-r 2-r 4-b 7-r 9-b 11-b 12-r 15-r 18-b 19-r
5
PreOrder:9-b 1-b 0-b 4-r 2-b 7-b 5-r 12-b 11-b 18-b 15-r 19-r
InOrder:0-b 1-b 2-b 4-r 5-r 7-b 9-b 11-b 12-b 15-r 18-b 19-r
14
PreOrder:9-b 1-b 0-b 4-r 2-b 7-b 5-r 12-b 11-b 18-r 15-b 14-r 19-b
InOrder:0-b 1-b 2-b 4-r 5-r 7-b 9-b 11-b 12-b 14-r 15-b 18-r 19-b
13
PreOrder:9-b 1-b 0-b 4-r 2-b 7-b 5-r 12-b 11-b 18-r 14-b 13-r 15-r 19-b
InOrder:0-b 1-b 2-b 4-r 5-r 7-b 9-b 11-b 12-b 13-r 14-b 15-r 18-r 19-b
10
PreOrder:9-b 1-b 0-b 4-r 2-b 7-b 5-r 12-b 11-b 10-r 18-r 14-b 13-r 15-r 19-b
InOrder:0-b 1-b 2-b 4-r 5-r 7-b 9-b 10-r 11-b 12-b 13-r 14-b 15-r 18-r 19-b
16
PreOrder:9-b 1-b 0-b 4-r 2-b 7-b 5-r 14-b 12-r 11-b 10-r 13-b 18-r 15-b 16-r 19-b
InOrder:0-b 1-b 2-b 4-r 5-r 7-b 9-b 10-r 11-b 12-r 13-b 14-b 15-b 16-r 18-r 19-b
6
PreOrder:9-b 1-b 0-b 4-r 2-b 6-b 5-r 7-r 14-b 12-r 11-b 10-r 13-b 18-r 15-b 16-r 19-b
InOrder:0-b 1-b 2-b 4-r 5-r 6-b 7-r 9-b 10-r 11-b 12-r 13-b 14-b 15-b 16-r 18-r 19-b
3
PreOrder:9-b 1-b 0-b 4-r 2-b 3-r 6-b 5-r 7-r 14-b 12-r 11-b 10-r 13-b 18-r 15-b 16-r 19-b
InOrder:0-b 1-b 2-b 3-r 4-r 5-r 6-b 7-r 9-b 10-r 11-b 12-r 13-b 14-b 15-b 16-r 18-r 19-b
8
PreOrder:9-b 4-b 1-r 0-b 2-b 3-r 6-r 5-b 7-b 8-r 14-b 12-r 11-b 10-r 13-b 18-r 15-b 16-r 19-b
InOrder:0-b 1-r 2-b 3-r 4-b 5-b 6-r 7-b 8-r 9-b 10-r 11-b 12-r 13-b 14-b 15-b 16-r 18-r 19-b
17
PreOrder:9-b 4-b 1-r 0-b 2-b 3-r 6-r 5-b 7-b 8-r 14-b 12-r 11-b 10-r 13-b 18-r 16-b 15-r 17-r 19-b
InOrder:0-b 1-r 2-b 3-r 4-b 5-b 6-r 7-b 8-r 9-b 10-r 11-b 12-r 13-b 14-b 15-r 16-b 17-r 18-r 19-b//删除节点
12
PreOrder:9-b 4-b 1-r 0-b 2-b 3-r 6-r 5-b 7-b 8-r 14-b 11-r 10-b 13-b 18-r 16-b 15-r 17-r 19-b
InOrder:0-b 1-r 2-b 3-r 4-b 5-b 6-r 7-b 8-r 9-b 10-b 11-r 13-b 14-b 15-r 16-b 17-r 18-r 19-b
1
PreOrder:9-b 4-b 2-r 0-b 3-b 6-r 5-b 7-b 8-r 14-b 11-r 10-b 13-b 18-r 16-b 15-r 17-r 19-b
InOrder:0-b 2-r 3-b 4-b 5-b 6-r 7-b 8-r 9-b 10-b 11-r 13-b 14-b 15-r 16-b 17-r 18-r 19-b
9
PreOrder:10-b 4-b 2-r 0-b 3-b 6-r 5-b 7-b 8-r 14-b 11-b 13-r 18-r 16-b 15-r 17-r 19-b
InOrder:0-b 2-r 3-b 4-b 5-b 6-r 7-b 8-r 10-b 11-b 13-r 14-b 15-r 16-b 17-r 18-r 19-b
2
PreOrder:10-b 4-b 3-b 0-r 6-r 5-b 7-b 8-r 14-b 11-b 13-r 18-r 16-b 15-r 17-r 19-b
InOrder:0-r 3-b 4-b 5-b 6-r 7-b 8-r 10-b 11-b 13-r 14-b 15-r 16-b 17-r 18-r 19-b
0
PreOrder:10-b 4-b 3-b 6-r 5-b 7-b 8-r 14-b 11-b 13-r 18-r 16-b 15-r 17-r 19-b
InOrder:3-b 4-b 5-b 6-r 7-b 8-r 10-b 11-b 13-r 14-b 15-r 16-b 17-r 18-r 19-b
11
PreOrder:10-b 4-b 3-b 6-r 5-b 7-b 8-r 14-b 13-b 18-r 16-b 15-r 17-r 19-b
InOrder:3-b 4-b 5-b 6-r 7-b 8-r 10-b 13-b 14-b 15-r 16-b 17-r 18-r 19-b
7
PreOrder:10-b 4-b 3-b 6-r 5-b 8-b 14-b 13-b 18-r 16-b 15-r 17-r 19-b
InOrder:3-b 4-b 5-b 6-r 8-b 10-b 13-b 14-b 15-r 16-b 17-r 18-r 19-b
19
PreOrder:10-b 4-b 3-b 6-r 5-b 8-b 14-b 13-b 16-r 15-b 18-b 17-r
InOrder:3-b 4-b 5-b 6-r 8-b 10-b 13-b 14-b 15-b 16-r 17-r 18-b
4
PreOrder:10-b 5-b 3-b 6-b 8-r 14-b 13-b 16-r 15-b 18-b 17-r
InOrder:3-b 5-b 6-b 8-r 10-b 13-b 14-b 15-b 16-r 17-r 18-b
15
PreOrder:10-b 5-b 3-b 6-b 8-r 14-b 13-b 17-r 16-b 18-b
InOrder:3-b 5-b 6-b 8-r 10-b 13-b 14-b 16-b 17-r 18-b
18
PreOrder:10-b 5-b 3-b 6-b 8-r 14-b 13-b 17-b 16-r
InOrder:3-b 5-b 6-b 8-r 10-b 13-b 14-b 16-r 17-b
5
PreOrder:10-b 6-b 3-b 8-b 14-b 13-b 17-b 16-r
InOrder:3-b 6-b 8-b 10-b 13-b 14-b 16-r 17-b
14
PreOrder:10-b 6-b 3-b 8-b 16-b 13-b 17-b
InOrder:3-b 6-b 8-b 10-b 13-b 16-b 17-b
13
PreOrder:10-b 6-r 3-b 8-b 16-b 17-r
InOrder:3-b 6-r 8-b 10-b 16-b 17-r
10
PreOrder:16-b 6-r 3-b 8-b 17-b
InOrder:3-b 6-r 8-b 16-b 17-b
16
PreOrder:6-b 3-b 17-b 8-r
InOrder:3-b 6-b 8-r 17-b
6
PreOrder:8-b 3-b 17-b
InOrder:3-b 8-b 17-b
3
PreOrder:8-b 17-r
InOrder:8-b 17-r
8
PreOrder:17-b
InOrder:17-b
17
PreOrder:
InOrder:D:\College_Data\编程相关\代码存放\program\RBTree\Debug\RBTree.exe (进程 13036)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口...