红黑树（四）C++实现

概要

前面分别介绍红黑树的理论知识和红黑树的C语言实现。本章是红黑树的C&＃43;&＃43;实现&＃xff0c;若读者对红黑树的理论知识不熟悉&＃xff0c;建立先学习红黑树的理论知识&＃xff0c;再来学习本章。

目录
1. 红黑树的介绍
2. 红黑树的C&＃43;&＃43;实现(代码说明)
3. 红黑树的C&＃43;&＃43;实现(完整源码)
4. 红黑树的C&＃43;&＃43;测试程序

转载请注明出处&＃xff1a;红黑树(四)之 C&＃43;&＃43;的实现 - 如果天空不死 - 博客园

更多内容&＃xff1a;数据结构与算法系列 目录

(01) 红黑树(一)之 原理和算法详细介绍
(02) 红黑树(二)之 C语言的实现
(03) 红黑树(三)之 Linux内核中红黑树的经典实现
(04) 红黑树(四)之 C&＃43;&＃43;的实现 
(05) 红黑树(五)之 Java的实现
(06) 红黑树(六)之 参考资料

红黑树的介绍

红黑树(Red-Black Tree&＃xff0c;简称R-B Tree)&＃xff0c;它一种特殊的二叉查找树。
红黑树是特殊的二叉查找树&＃xff0c;意味着它满足二叉查找树的特征&＃xff1a;任意一个节点所包含的键值&＃xff0c;大于等于左孩子的键值&＃xff0c;小于等于右孩子的键值。
除了具备该特性之外&＃xff0c;红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色&＃xff0c;颜色是红(Red)或黑(Black)。
红黑树的特性:
(1) 每个节点或者是黑色&＃xff0c;或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意&＃xff1a;这里叶子节点&＃xff0c;是指为空的叶子节点&＃xff01;]
(4) 如果一个节点是红色的&＃xff0c;则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性&＃xff0c;需要注意的是&＃xff1a;
第一&＃xff0c;特性(3)中的叶子节点&＃xff0c;是只为空(NIL或null)的节点。
第二&＃xff0c;特性(5)&＃xff0c;确保没有一条路径会比其他路径长出俩倍。因而&＃xff0c;红黑树是相对是接近平衡的二叉树。

红黑树示意图如下&＃xff1a;

红黑树的C&＃43;&＃43;实现(代码说明)

红黑树的基本操作是添加、删除和旋转。在对红黑树进行添加或删除后&＃xff0c;会用到旋转方法。为什么呢&＃xff1f;道理很简单&＃xff0c;添加或删除红黑树中的节点之后&＃xff0c;红黑树就发生了变化&＃xff0c;可能不满足红黑树的5条性质&＃xff0c;也就不再是一颗红黑树了&＃xff0c;而是一颗普通的树。而通过旋转&＃xff0c;可以使这颗树重新成为红黑树。简单点说&＃xff0c;旋转的目的是让树保持红黑树的特性。
旋转包括两种&＃xff1a;左旋 和 右旋。下面分别对红黑树的基本操作进行介绍。

1. 基本定义

enum RBTColor{RED, BLACK};template
class RBTNode{public:RBTColor color; // 颜色T key; // 关键字(键值)RBTNode *left; // 左孩子RBTNode *right; // 右孩子RBTNode *parent; // 父结点RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r):key(value),color(c),parent(),left(l),right(r) {}
};template
class RBTree {private:RBTNode *mRoot; // 根结点public:RBTree();~RBTree();// 前序遍历"红黑树"void preOrder();// 中序遍历"红黑树"void inOrder();// 后序遍历"红黑树"void postOrder();// (递归实现)查找"红黑树"中键值为key的节点RBTNode* search(T key);// (非递归实现)查找"红黑树"中键值为key的节点RBTNode* iterativeSearch(T key);// 查找最小结点&＃xff1a;返回最小结点的键值。T minimum();// 查找最大结点&＃xff1a;返回最大结点的键值。T maximum();// 找结点(x)的后继结点。即&＃xff0c;查找"红黑树中数据值大于该结点"的"最小结点"。RBTNode* successor(RBTNode *x);// 找结点(x)的前驱结点。即&＃xff0c;查找"红黑树中数据值小于该结点"的"最大结点"。RBTNode* predecessor(RBTNode *x);// 将结点(key为节点键值)插入到红黑树中void insert(T key);// 删除结点(key为节点键值)void remove(T key);// 销毁红黑树void destroy();// 打印红黑树void print();private:// 前序遍历"红黑树"void preOrder(RBTNode* tree) const;// 中序遍历"红黑树"void inOrder(RBTNode* tree) const;// 后序遍历"红黑树"void postOrder(RBTNode* tree) const;// (递归实现)查找"红黑树x"中键值为key的节点RBTNode* search(RBTNode* x, T key) const;// (非递归实现)查找"红黑树x"中键值为key的节点RBTNode* iterativeSearch(RBTNode* x, T key) const;// 查找最小结点&＃xff1a;返回tree为根结点的红黑树的最小结点。RBTNode* minimum(RBTNode* tree);// 查找最大结点&＃xff1a;返回tree为根结点的红黑树的最大结点。RBTNode* maximum(RBTNode* tree);// 左旋void leftRotate(RBTNode* &root, RBTNode* x);// 右旋void rightRotate(RBTNode* &root, RBTNode* y);// 插入函数void insert(RBTNode* &root, RBTNode* node);// 插入修正函数void insertFixUp(RBTNode* &root, RBTNode* node);// 删除函数void remove(RBTNode* &root, RBTNode *node);// 删除修正函数void removeFixUp(RBTNode* &root, RBTNode *node, RBTNode *parent);// 销毁红黑树void destroy(RBTNode* &tree);// 打印红黑树void print(RBTNode* tree, T key, int direction);#define rb_parent(r) ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r) ((r)->color&＃61;&＃61;RED)
#define rb_is_black(r) ((r)->color&＃61;&＃61;BLACK)
#define rb_set_black(r) do { (r)->color &＃61; BLACK; } while (0)
#define rb_set_red(r) do { (r)->color &＃61; RED; } while (0)
#define rb_set_parent(r,p) do { (r)->parent &＃61; (p); } while (0)
#define rb_set_color(r,c) do { (r)->color &＃61; (c); } while (0)
};

RBTNode是红黑树的节点类&＃xff0c;而RBTree对应是红黑树的操作实现类。在RBTree中包含了根节点mRoot和红黑树的相关API。
注意&＃xff1a;(01) 在实现红黑树API的过程中&＃xff0c;我重载了许多函数。重载的原因&＃xff0c;一是因为有的API是内部接口&＃xff0c;有的是外部接口&＃xff1b;二是为了让结构更加清晰。
          (02) 由于C&＃43;&＃43;的实现是在上一篇介绍的"C语言"实现基础上移植而来&＃xff0c;在该代码中&＃xff0c;保留了一些C语言的特性&＃xff1b;例如(宏定义)。

2. 左旋

对x进行左旋&＃xff0c;意味着"将x变成一个左节点"。

左旋的实现代码(C&＃43;&＃43;语言)

/* * 对红黑树的节点(x)进行左旋转** 左旋示意图(对节点x进行左旋)&＃xff1a;* px px* / /* x y * / \ --(左旋)--> / \ #* lx y x ry * / \ / \* ly ry lx ly ***/
template
void RBTree::leftRotate(RBTNode* &root, RBTNode* x)
{// 设置x的右孩子为yRBTNode *y &＃61; x->right;// 将 “y的左孩子” 设为 “x的右孩子”&＃xff1b;// 如果y的左孩子非空&＃xff0c;将 “x” 设为 “y的左孩子的父亲”x->right &＃61; y->left;if (y->left !&＃61; NULL)y->left->parent &＃61; x;// 将 “x的父亲” 设为 “y的父亲”y->parent &＃61; x->parent;if (x->parent &＃61;&＃61; NULL){root &＃61; y; // 如果 “x的父亲” 是空节点&＃xff0c;则将y设为根节点}else{if (x->parent->left &＃61;&＃61; x)x->parent->left &＃61; y; // 如果 x是它父节点的左孩子&＃xff0c;则将y设为“x的父节点的左孩子”elsex->parent->right &＃61; y; // 如果 x是它父节点的左孩子&＃xff0c;则将y设为“x的父节点的左孩子”}// 将 “x” 设为 “y的左孩子”y->left &＃61; x;// 将 “x的父节点” 设为 “y”x->parent &＃61; y;
}

3. 右旋

对y进行左旋&＃xff0c;意味着"将y变成一个右节点"。

右旋的实现代码(C&＃43;&＃43;语言)

/* * 对红黑树的节点(y)进行右旋转** 右旋示意图(对节点y进行左旋)&＃xff1a;* py py* / /* y x * / \ --(右旋)--> / \ #* x ry lx y * / \ / \ #* lx rx rx ry* */
template
void RBTree::rightRotate(RBTNode* &root, RBTNode* y)
{// 设置x是当前节点的左孩子。RBTNode *x &＃61; y->left;// 将 “x的右孩子” 设为 “y的左孩子”&＃xff1b;// 如果"x的右孩子"不为空的话&＃xff0c;将 “y” 设为 “x的右孩子的父亲”y->left &＃61; x->right;if (x->right !&＃61; NULL)x->right->parent &＃61; y;// 将 “y的父亲” 设为 “x的父亲”x->parent &＃61; y->parent;if (y->parent &＃61;&＃61; NULL) {root &＃61; x; // 如果 “y的父亲” 是空节点&＃xff0c;则将x设为根节点}else{if (y &＃61;&＃61; y->parent->right)y->parent->right &＃61; x; // 如果 y是它父节点的右孩子&＃xff0c;则将x设为“y的父节点的右孩子”elsey->parent->left &＃61; x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”}// 将 “y” 设为 “x的右孩子”x->right &＃61; y;// 将 “y的父节点” 设为 “x”y->parent &＃61; x;
}

4. 添加

将一个节点插入到红黑树中&＃xff0c;需要执行哪些步骤呢&＃xff1f;首先&＃xff0c;将红黑树当作一颗二叉查找树&＃xff0c;将节点插入&＃xff1b;然后&＃xff0c;将节点着色为红色&＃xff1b;最后&＃xff0c;通过"旋转和重新着色"等一系列操作来修正该树&＃xff0c;使之重新成为一颗红黑树。详细描述如下&＃xff1a;
第一步: 将红黑树当作一颗二叉查找树&＃xff0c;将节点插入。
       红黑树本身就是一颗二叉查找树&＃xff0c;将节点插入后&＃xff0c;该树仍然是一颗二叉查找树。也就意味着&＃xff0c;树的键值仍然是有序的。此外&＃xff0c;无论是左旋还是右旋&＃xff0c;若旋转之前这棵树是二叉查找树&＃xff0c;旋转之后它一定还是二叉查找树。这也就意味着&＃xff0c;任何的旋转和重新着色操作&＃xff0c;都不会改变它仍然是一颗二叉查找树的事实。
      好吧&＃xff1f;那接下来&＃xff0c;我们就来想方设法的旋转以及重新着色&＃xff0c;使这颗树重新成为红黑树&＃xff01;

第二步&＃xff1a;将插入的节点着色为"红色"。
      为什么着色成红色&＃xff0c;而不是黑色呢&＃xff1f;为什么呢&＃xff1f;在回答之前&＃xff0c;我们需要重新温习一下红黑树的特性&＃xff1a;
(1) 每个节点或者是黑色&＃xff0c;或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意&＃xff1a;这里叶子节点&＃xff0c;是指为空的叶子节点&＃xff01;]
(4) 如果一个节点是红色的&＃xff0c;则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
    将插入的节点着色为红色&＃xff0c;不会违背"特性(5)"&＃xff01;少违背一条特性&＃xff0c;就意味着我们需要处理的情况越少。接下来&＃xff0c;就要努力的让这棵树满足其它性质即可&＃xff1b;满足了的话&＃xff0c;它就又是一颗红黑树了。o(∩∩)o...哈哈

第三步: 通过一系列的旋转或着色等操作&＃xff0c;使之重新成为一颗红黑树。
       第二步中&＃xff0c;将插入节点着色为"红色"之后&＃xff0c;不会违背"特性(5)"。那它到底会违背哪些特性呢&＃xff1f;
       对于"特性(1)"&＃xff0c;显然不会违背了。因为我们已经将它涂成红色了。
       对于"特性(2)"&＃xff0c;显然也不会违背。在第一步中&＃xff0c;我们是将红黑树当作二叉查找树&＃xff0c;然后执行的插入操作。而根据二叉查找数的特点&＃xff0c;插入操作不会改变根节点。所以&＃xff0c;根节点仍然是黑色。
       对于"特性(3)"&＃xff0c;显然不会违背了。这里的叶子节点是指的空叶子节点&＃xff0c;插入非空节点并不会对它们造成影响。
       对于"特性(4)"&＃xff0c;是有可能违背的&＃xff01;
      那接下来&＃xff0c;想办法使之"满足特性(4)"&＃xff0c;就可以将树重新构造成红黑树了。

添加操作的实现代码(C&＃43;&＃43;语言)

/* * 将结点插入到红黑树中** 参数说明&＃xff1a;* root 红黑树的根结点* node 插入的结点 // 对应《算法导论》中的node*/
template
void RBTree::insert(RBTNode* &root, RBTNode* node)
{RBTNode *y &＃61; NULL;RBTNode *x &＃61; root;// 1. 将红黑树当作一颗二叉查找树&＃xff0c;将节点添加到二叉查找树中。while (x !&＃61; NULL){y &＃61; x;if (node->key key)x &＃61; x->left;elsex &＃61; x->right;}node->parent &＃61; y;if (y!&＃61;NULL){if (node->key key)y->left &＃61; node;elsey->right &＃61; node;}elseroot &＃61; node;// 2. 设置节点的颜色为红色node->color &＃61; RED;// 3. 将它重新修正为一颗二叉查找树insertFixUp(root, node);
}/* * 将结点(key为节点键值)插入到红黑树中** 参数说明&＃xff1a;* tree 红黑树的根结点* key 插入结点的键值*/
template
void RBTree::insert(T key)
{RBTNode *z&＃61;NULL;// 如果新建结点失败&＃xff0c;则返回。if ((z&＃61;new RBTNode(key,BLACK,NULL,NULL,NULL)) &＃61;&＃61; NULL)return ;insert(mRoot, z);
}

内部接口 -- insert(root, node)的作用是将"node"节点插入到红黑树中。其中&＃xff0c;root是根&＃xff0c;node是被插入节点。
外部接口 -- insert(key)的作用是将"key"添加到红黑树中。

添加修正操作的实现代码(C&＃43;&＃43;语言)

/** 红黑树插入修正函数** 在向红黑树中插入节点之后(失去平衡)&＃xff0c;再调用该函数&＃xff1b;* 目的是将它重新塑造成一颗红黑树。** 参数说明&＃xff1a;* root 红黑树的根* node 插入的结点 // 对应《算法导论》中的z*/
template
void RBTree::insertFixUp(RBTNode* &root, RBTNode* node)
{RBTNode *parent, *gparent;// 若“父节点存在&＃xff0c;并且父节点的颜色是红色”while ((parent &＃61; rb_parent(node)) && rb_is_red(parent)){gparent &＃61; rb_parent(parent);//若“父节点”是“祖父节点的左孩子”if (parent &＃61;&＃61; gparent->left){// Case 1条件&＃xff1a;叔叔节点是红色{RBTNode *uncle &＃61; gparent->right;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node &＃61; gparent;continue;}}// Case 2条件&＃xff1a;叔叔是黑色&＃xff0c;且当前节点是右孩子if (parent->right &＃61;&＃61; node){RBTNode *tmp;leftRotate(root, parent);tmp &＃61; parent;parent &＃61; node;node &＃61; tmp;}// Case 3条件&＃xff1a;叔叔是黑色&＃xff0c;且当前节点是左孩子。rb_set_black(parent);rb_set_red(gparent);rightRotate(root, gparent);} else//若“z的父节点”是“z的祖父节点的右孩子”{// Case 1条件&＃xff1a;叔叔节点是红色{RBTNode *uncle &＃61; gparent->left;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node &＃61; gparent;continue;}}// Case 2条件&＃xff1a;叔叔是黑色&＃xff0c;且当前节点是左孩子if (parent->left &＃61;&＃61; node){RBTNode *tmp;rightRotate(root, parent);tmp &＃61; parent;parent &＃61; node;node &＃61; tmp;}// Case 3条件&＃xff1a;叔叔是黑色&＃xff0c;且当前节点是右孩子。rb_set_black(parent);rb_set_red(gparent);leftRotate(root, gparent);}}// 将根节点设为黑色rb_set_black(root);
}

insertFixUp(root, node)的作用是对应"上面所讲的第三步"。它是一个内部接口。

5. 删除操作

将红黑树内的某一个节点删除。需要执行的操作依次是&＃xff1a;首先&＃xff0c;将红黑树当作一颗二叉查找树&＃xff0c;将该节点从二叉查找树中删除&＃xff1b;然后&＃xff0c;通过"旋转和重新着色"等一系列来修正该树&＃xff0c;使之重新成为一棵红黑树。详细描述如下&＃xff1a;

第一步&＃xff1a;将红黑树当作一颗二叉查找树&＃xff0c;将节点删除。
      这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况&＃xff1a;
① 被删除节点没有儿子&＃xff0c;即为叶节点。那么&＃xff0c;直接将该节点删除就OK了。
② 被删除节点只有一个儿子。那么&＃xff0c;直接删除该节点&＃xff0c;并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么&＃xff0c;先找出它的后继节点&＃xff1b;然后把“它的后继节点的内容”复制给“该节点的内容”&＃xff1b;之后&＃xff0c;删除“它的后继节点”。在这里&＃xff0c;后继节点相当于替身&＃xff0c;在将后继节点的内容复制给"被删除节点"之后&＃xff0c;再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了&＃xff0c;下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下&＃xff0c;它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空&＃xff0c;就意味着"该节点的后继节点"要么没有儿子&＃xff0c;要么只有一个儿子。若没有儿子&＃xff0c;则按"情况① "进行处理&＃xff1b;若只有一个儿子&＃xff0c;则按"情况② "进行处理。

第二步&＃xff1a;通过"旋转和重新着色"等一系列来修正该树&＃xff0c;使之重新成为一棵红黑树。
       因为"第一步"中删除节点之后&＃xff0c;可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树&＃xff0c;使之重新成为一棵红黑树。

删除操作的实现代码(C&＃43;&＃43;语言)

/* * 删除结点(node)&＃xff0c;并返回被删除的结点** 参数说明&＃xff1a;* root 红黑树的根结点* node 删除的结点*/
template
void RBTree::remove(RBTNode* &root, RBTNode *node)
{RBTNode *child, *parent;RBTColor color;// 被删除节点的"左右孩子都不为空"的情况。if ( (node->left!&＃61;NULL) && (node->right!&＃61;NULL) ) {// 被删节点的后继节点。(称为"取代节点")// 用它来取代"被删节点"的位置&＃xff0c;然后再将"被删节点"去掉。RBTNode *replace &＃61; node;// 获取后继节点replace &＃61; replace->right;while (replace->left !&＃61; NULL)replace &＃61; replace->left;// "node节点"不是根节点(只有根节点不存在父节点)if (rb_parent(node)){if (rb_parent(node)->left &＃61;&＃61; node)rb_parent(node)->left &＃61; replace;elserb_parent(node)->right &＃61; replace;} else // "node节点"是根节点&＃xff0c;更新根节点。root &＃61; replace;// child是"取代节点"的右孩子&＃xff0c;也是需要"调整的节点"。// "取代节点"肯定不存在左孩子&＃xff01;因为它是一个后继节点。child &＃61; replace->right;parent &＃61; rb_parent(replace);// 保存"取代节点"的颜色color &＃61; rb_color(replace);// "被删除节点"是"它的后继节点的父节点"if (parent &＃61;&＃61; node){parent &＃61; replace;} else{// child不为空if (child)rb_set_parent(child, parent);parent->left &＃61; child;replace->right &＃61; node->right;rb_set_parent(node->right, replace);}replace->parent &＃61; node->parent;replace->color &＃61; node->color;replace->left &＃61; node->left;node->left->parent &＃61; replace;if (color &＃61;&＃61; BLACK)removeFixUp(root, child, parent);delete node;return ;}if (node->left !&＃61;NULL)child &＃61; node->left;else child &＃61; node->right;parent &＃61; node->parent;// 保存"取代节点"的颜色color &＃61; node->color;if (child)child->parent &＃61; parent;// "node节点"不是根节点if (parent){if (parent->left &＃61;&＃61; node)parent->left &＃61; child;elseparent->right &＃61; child;}elseroot &＃61; child;if (color &＃61;&＃61; BLACK)removeFixUp(root, child, parent);delete node;
}/* * 删除红黑树中键值为key的节点** 参数说明&＃xff1a;* tree 红黑树的根结点*/
template
void RBTree::remove(T key)
{RBTNode *node; // 查找key对应的节点(node)&＃xff0c;找到的话就删除该节点if ((node &＃61; search(mRoot, key)) !&＃61; NULL)remove(mRoot, node);
}

内部接口 -- remove(root, node)的作用是将"node"节点插入到红黑树中。其中&＃xff0c;root是根&＃xff0c;node是被插入节点。
外部接口 -- remove(key)删除红黑树中键值为key的节点。

删除修正操作的实现代码(C&＃43;&＃43;语言)

/** 红黑树删除修正函数** 在从红黑树中删除插入节点之后(红黑树失去平衡)&＃xff0c;再调用该函数&＃xff1b;* 目的是将它重新塑造成一颗红黑树。** 参数说明&＃xff1a;* root 红黑树的根* node 待修正的节点*/
template
void RBTree::removeFixUp(RBTNode* &root, RBTNode *node, RBTNode *parent)
{RBTNode *other;while ((!node || rb_is_black(node)) && node !&＃61; root){if (parent->left &＃61;&＃61; node){other &＃61; parent->right;if (rb_is_red(other)){// Case 1: x的兄弟w是红色的 rb_set_black(other);rb_set_red(parent);leftRotate(root, parent);other &＃61; parent->right;}if ((!other->left || rb_is_black(other->left)) &&(!other->right || rb_is_black(other->right))){// Case 2: x的兄弟w是黑色&＃xff0c;且w的俩个孩子也都是黑色的 rb_set_red(other);node &＃61; parent;parent &＃61; rb_parent(node);}else{if (!other->right || rb_is_black(other->right)){// Case 3: x的兄弟w是黑色的&＃xff0c;并且w的左孩子是红色&＃xff0c;右孩子为黑色。 rb_set_black(other->left);rb_set_red(other);rightRotate(root, other);other &＃61; parent->right;}// Case 4: x的兄弟w是黑色的&＃xff1b;并且w的右孩子是红色的&＃xff0c;左孩子任意颜色。rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->right);leftRotate(root, parent);node &＃61; root;break;}}else{other &＃61; parent->left;if (rb_is_red(other)){// Case 1: x的兄弟w是红色的 rb_set_black(other);rb_set_red(parent);rightRotate(root, parent);other &＃61; parent->left;}if ((!other->left || rb_is_black(other->left)) &&(!other->right || rb_is_black(other->right))){// Case 2: x的兄弟w是黑色&＃xff0c;且w的俩个孩子也都是黑色的 rb_set_red(other);node &＃61; parent;parent &＃61; rb_parent(node);}else{if (!other->left || rb_is_black(other->left)){// Case 3: x的兄弟w是黑色的&＃xff0c;并且w的左孩子是红色&＃xff0c;右孩子为黑色。 rb_set_black(other->right);rb_set_red(other);leftRotate(root, other);other &＃61; parent->left;}// Case 4: x的兄弟w是黑色的&＃xff1b;并且w的右孩子是红色的&＃xff0c;左孩子任意颜色。rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->left);rightRotate(root, parent);node &＃61; root;break;}}}if (node)rb_set_black(node);
}

removeFixup(root, node, parent)是对应"上面所讲的第三步"。它是一个内部接口。

红黑树的C&＃43;&＃43;实现(完整源码)

下面是红黑树实现的完整代码和相应的测试程序。
(1) 除了上面所说的"左旋"、"右旋"、"添加"、"删除"等基本操作之后&＃xff0c;还实现了"遍历"、"查找"、"打印"、"最小值"、"最大值"、"创建"、"销毁"等接口。
(2) 函数接口大多分为内部接口和外部接口。内部接口是private函数&＃xff0c;外部接口则是public函数。
(3) 测试代码中提供了"插入"和"删除"动作的检测开关。默认是关闭的&＃xff0c;打开方法可以参考"代码中的说明"。建议在打开开关后&＃xff0c;在草稿上自己动手绘制一下红黑树。

红黑树的实现文件(RBTree.h)

 View Code

红黑树的测试文件(RBTreeTest.cpp)

 View Code

红黑树的C&＃43;&＃43;测试程序

测试程序已经包含在相应的实现文件(MaxHeap.cpp)中了&＃xff0c;这里就不再重复说明。下面是测试程序的运行结果&＃xff1a;

&＃61;&＃61; 原始数据: 10 40 30 60 90 70 20 50 80
&＃61;&＃61; 前序遍历: 30 10 20 60 40 50 80 70 90
&＃61;&＃61; 中序遍历: 10 20 30 40 50 60 70 80 90
&＃61;&＃61; 后序遍历: 20 10 50 40 70 90 80 60 30
&＃61;&＃61; 最小值: 10
&＃61;&＃61; 最大值: 90
&＃61;&＃61; 树的详细信息:
30(B) is root
10(B) is 30&＃39;s left child
20(R) is 10&＃39;s right child
60(R) is 30&＃39;s right child
40(B) is 60&＃39;s left child
50(R) is 40&＃39;s right child
80(B) is 60&＃39;s right child
70(R) is 80&＃39;s left child
90(R) is 80&＃39;s right child

上面的内容错误较多&＃xff0c;看一下下面这个文章给出已给较为准确的实现

C&＃43;&＃43;红黑树
零、前言
一、红黑树的概念及性质
二、红黑树结点的定义
三、红黑树的插入操作
1、变色处理
2、单旋&＃43;变色
3、双旋&＃43;变色
4、插入实现
四、红黑树的验证
五、红黑树的删除
六、红黑树与**AVL**树的比较
零、前言
本章继AVL树后继续讲解学习C&＃43;&＃43;中另一个二叉搜索树–红黑树

一、红黑树的概念及性质
概念&＃xff1a;
红黑树&＃xff0c;是一种二叉搜索树&＃xff0c;但在每个结点上增加一个存储位表示结点的颜色&＃xff0c;可以是Red或Black

通过对任何一条从根到叶子的路径上各个结点着色方式的限制&＃xff0c;红黑树确保没有一条路径会比其他路径长出俩倍&＃xff0c;因而是接近平衡的

注&＃xff1a;AVL树是严格平衡的二叉搜索树&＃xff0c;左右子树高度不超过1&＃xff1b;红黑树是近似平衡&＃xff0c;最长路径不超过最短路径的二倍

示图&＃xff1a;

红黑树的性质&＃xff1a;
每个结点不是红色就是黑色

根节点是黑色的

如果一个节点是红色的&＃xff0c;则它的两个孩子结点是黑色的

对于每个结点&＃xff0c;从该结点到其所有后代叶结点的简单路径上&＃xff0c;均包含相同数目的黑色结点

每个NIL结点都是黑色的(此处的结点指的是空结点)&＃xff08;该条规则确定了路径条数&＃xff09;

为什么红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍&＃xff1a;
红黑树第三条性质说明红黑树不能存在连续&＃xff08;父子相连&＃xff09;的红结点&＃xff0c;可以存在连续的黑结点&＃xff0c;又由于第四条性质每个路径上的黑结点个数都相同 &＃xff0c;所以对于最短路径来说一定是都是黑色结点&＃xff0c;对于最长路径来说一定是黑色红色相间的路径&＃xff0c;所以最长路径不超过最短路径长度的二倍

示图&＃xff1a;

二、红黑树结点的定义
对于红黑树来说以颜色来代替AVL树的平衡因子的作用&＃xff0c;除此之外在定义上没有什么区别

实现代码&＃xff1a;
enum Colour//颜色
{
    RED,
    BLACK,
};
template
struct RBTreeNode
{
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;

    pair _kv;
    Colour _col;

    RBTreeNode(const pair& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(RED)
    {}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
注&＃xff1a;此处采用枚举来表示&＃xff0c;当然也可以使用其他方式

在节点的定义中为什么要将节点的默认颜色给成红色的&＃xff1a;
如果默认颜色为黑&＃xff0c;那么在插入中插入一个黑结点一定会让该路径上的黑结点数量加1&＃xff0c;从而与其他路径上黑结点数量造成不一致&＃xff0c;而一定会影响该棵红黑树

如果默认颜色为红&＃xff0c;那么在插入中插入一个红结点&＃xff0c;可能新插入结点的父结点为黑色结点则没有影响&＃xff0c;也可能新插入结点的父结点为红结点&＃xff0c;由于不能存在连续的&＃xff08;父子相连的&＃xff09;红色结点&＃xff0c;而对该棵树造成影响

所以默认为红色比较黑色来说是好的

三、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件&＃xff0c;当违反限制条件时就需要做出相应的调整

红黑树的插入可分为两步&＃xff1a;
按照二叉搜索的树规则插入新节点

新节点插入后检查红黑树的性质是否造到破坏

注意&＃xff1a;
因为新节点的默认颜色是红色&＃xff0c;如果其父亲节点的颜色是黑色&＃xff0c;则没有违反红黑树任何性质&＃xff0c;则不需要调整

当新插入节点的父亲节点颜色为红色时&＃xff0c;就违反了性质三不能有连在一起的红色节点&＃xff0c;此时需要对红黑树分情况来讨论

因为插入结点的父结点是红色的&＃xff0c;说明父结点不是根结点&＃xff08;根结点是黑色的&＃xff09;&＃xff0c;因此插入结点的祖父结点&＃xff08;父结点的父结点&＃xff09;就一定存在

红黑树调整时具体应该如何调整&＃xff0c;主要是看插入结点的叔叔&＃xff08;插入结点的父结点的兄弟结点&＃xff09;&＃xff0c;根据插入结点叔叔的不同&＃xff0c;可将红黑树的调整分为三种情况

注&＃xff1a;约定cur为当前节点&＃xff0c;p为父节点&＃xff0c;g为祖父节点&＃xff0c;u为叔叔节点

1、变色处理
情况一: cur为红&＃xff0c;p为红&＃xff0c;g为黑&＃xff0c;u存在且为红

示图&＃xff1a;

分析&＃xff1a;
为了让该以 g 为根的子树不存在连续的红色结点&＃xff0c;并且不增加路径上的黑色结点&＃xff0c;我们让 g 的颜色变红&＃xff0c;让 u 和 p 的颜色变黑&＃xff0c;各路径上黑色结点数量没变&＃xff0c;以此达到红黑树的性质

因为 p 和 u 的颜色变黑&＃xff0c;对其子树没有影响&＃xff0c;但是 g 的颜色变红&＃xff0c;可能存在影响&＃xff0c;需要继续向上判断

判断逻辑&＃xff1a;
如果 g 就是该棵树的根那么最后需要将 g 的颜色变黑

如果 g 是整棵树的子树&＃xff0c;如果 g 的父节点是是黑色结点则不用调整&＃xff0c;如果是红色结点则需要根据具体情况来做出调整

解决方式&＃xff1a;
将p,u改为黑&＃xff0c;g改为红&＃xff0c;然后把g当成cur&＃xff0c;继续向上调整

抽象示图&＃xff1a;

动图演示1&＃xff1a;

动图演示2&＃xff1a;

2、单旋&＃43;变色
情况二: cur为红&＃xff0c;p为红&＃xff0c;g为黑&＃xff0c;u不存在**/u**为黑

示图&＃xff1a;

分析&＃xff1a;
当 u 节点不存在时&＃xff0c;说明cur一定是插入节点&＃xff0c;如果 cur 不是新插入节点&＃xff0c;那么在插入前时 cur 一定是黑色结点&＃xff08;由黑色变红&＃xff09;&＃xff0c;则插入前就不符合路径上黑结点数量相同的性质

当 u 节点存在且为黑色时&＃xff0c;说明 cur 的颜色插入前一定是黑色&＃xff0c;进过插入后变色为红色&＃xff0c;否则在插入前就存在连续的红色结点&＃xff0c;不符合红黑树性质

解决方法&＃xff1a;
如果p为g的左孩子&＃xff0c;cur为p的左孩子&＃xff0c;则进行右单旋转&＃xff0c;p变黑&＃xff0c;g变红

如果p为g的右孩子&＃xff0c;cur为p的右孩子&＃xff0c;则进行左单旋转&＃xff0c;p变黑&＃xff0c;g变红

抽象示图&＃xff1a;

动态示图&＃xff1a;

动图演示2&＃xff1a;

3、双旋&＃43;变色
情况三: cur为红&＃xff0c;p为红&＃xff0c;g为黑&＃xff0c;u不存在**/u**为黑

示图&＃xff1a;

分析&＃xff1a;
这里显然一次旋转也无法让达到红黑树平衡&＃xff0c;由此就需要进行两次旋转

解决方式&＃xff1a;
如果p为g的左孩子&＃xff0c;cur为p的右孩子&＃xff0c;则针对p做左单旋转&＃xff0c;p旋转后再对g进行右单旋&＃xff0c;旋转后将cur变黑&＃xff0c;g变红

如果p为g的右孩子&＃xff0c;cur为p的左孩子&＃xff0c;则针对p做右单旋转&＃xff0c;p旋转后再对g进行左单旋&＃xff0c;旋转后将cur变黑&＃xff0c;g变红

抽象示图&＃xff1a;

动图演示1&＃xff1a;

动图演示2&＃xff1a;

4、插入实现
插入主体实现&＃xff1a;

pair Insert(const pair& kv)
{
    //空树的情况
    if (_root &＃61;&＃61; nullptr)
    {
        _root &＃61; new Node(kv);
        _root->_col &＃61; BLACK;
        return make_pair(_root, true);
    }

    //查找位置插入节点
    Node* cur &＃61; _root, * parent &＃61; _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent &＃61; cur;
            cur &＃61; cur->_left;
        }
        else if (cur->_kv.first         {
            parent &＃61; cur;
            cur &＃61; cur->_right;
        }
        else
        {
            return make_pair(cur, false);
        }
    }

    //创建链接节点
    cur &＃61; new Node(kv);
    Node* newnode &＃61; cur;
    if (parent->_kv.first > kv.first)
    {
        parent->_left &＃61; cur;
    }
    else
    {
        parent->_right &＃61; cur;
    }
    cur->_parent &＃61; parent;
    
    //父节点存在且为红&＃xff0c;则需要调整&＃xff08;不能存在连续的红色节点&＃xff09;
    while (parent && parent->_col &＃61;&＃61; RED)
    {
        //此时当前节点一定有祖父节点
        Node* granparent &＃61; parent->_parent;
        //具体调整情况主要看叔叔节点
        //分左右讨论
        if (parent &＃61;&＃61; granparent->_left)
        {
            Node* uncle &＃61; granparent->_right;
            //情况1&＃xff1a;叔叔节点存在且为红
            if (uncle && uncle->_col &＃61;&＃61; RED)
            {
                //修改颜色&＃xff0c;继续向上检查
                granparent->_col &＃61; RED;
                parent->_col &＃61; uncle->_col &＃61; BLACK;

                cur &＃61; granparent;
                parent &＃61; cur->_parent;
            }
            else//情况2和3&＃xff1a;叔叔节点不存在 或者存在且为黑
            {
                //单旋(三代节点为斜线)&＃43;变色
                if (cur &＃61;&＃61; parent->_left)
                {
                    RotateR(granparent);

                    granparent->_col &＃61; RED;
                    parent->_col &＃61; BLACK;
                }
                else//双旋(三代节点为折线)&＃43;变色
                {
                    RotateL(parent);
                    RotateR(granparent);

                    cur->_col &＃61; BLACK;
                    granparent->_col &＃61; RED;
                }
                //旋转后不需再向上调整了
                break;
            }
        }
        else//parent&＃61;grandparent->right
        {
            Node* uncle &＃61; granparent->_left;
            if (uncle && uncle->_col &＃61;&＃61; RED)
            {
                parent->_col &＃61; uncle->_col &＃61; BLACK;
                granparent->_col &＃61; RED;

                cur &＃61; granparent;
                parent &＃61; cur->_parent;
            }
            else
            {
                if (cur &＃61;&＃61; parent->_right)
                {
                    RotateL(granparent);

                    parent->_col &＃61; BLACK;
                    granparent->_col &＃61; RED;
                }
                else
                {
                    RotateR(parent);
                    RotateL(granparent);

                    cur->_col &＃61; BLACK;
                    granparent->_col &＃61; RED;
                }
                break;
            }
        }
    }
    
    //确保根节点为黑
    _root->_col &＃61; BLACK;
    return make_pair(newnode, true);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
旋转实现&＃xff1a;

void RotateL(Node* parent)
{
    Node* subR &＃61; parent->_right;
    Node* subRL &＃61; subR->_left;
    Node* parentP &＃61; parent->_parent;

    parent->_right &＃61; subRL;
    if (subRL)
    {
        subRL->_parent &＃61; parent;
    }

    subR->_left &＃61; parent;
    parent->_parent &＃61; subR;

    if (parent &＃61;&＃61; _root)
    {
        _root &＃61; subR;
        subR->_parent &＃61; nullptr;
    }
    else
    {
        subR->_parent &＃61; parentP;
        if (parentP->_left &＃61;&＃61; parent)
        {
            parentP->_left &＃61; subR;
        }
        else
        {
            parentP->_right &＃61; subR;
        }
    }
}

void RotateR(Node* parent)
{
    Node* subL &＃61; parent->_left;
    Node* subLR &＃61; subL->_right;
    Node* parentP &＃61; parent->_parent;

    parent->_left &＃61; subLR;
    if (subLR)
    {
        subLR->_parent &＃61; parent;
    }

    subL->_right &＃61; parent;
    parent->_parent &＃61; subL;

    if (parent &＃61;&＃61; _root)
    {
        _root &＃61; subL;
        subL->_parent &＃61; nullptr;
    }
    else
    {
        subL->_parent &＃61; parentP;
        if (parentP->_left &＃61;&＃61; parent)
        {
            parentP->_left &＃61; subL;
        }
        else
        {
            parentP->_right &＃61; subL;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
四、红黑树的验证
红黑树的检测分为两步&＃xff1a;
检测其是否满足二叉搜索树(中序遍历是否为有序序列)

检测其是否满足红黑树的性质

实现代码&＃xff1a;
bool IsRBTree()
{
    //空树
    if (_root &＃61;&＃61; nullptr)
    {
        return true;
    }
    //根节点为黑色
    if (_root->_col &＃61;&＃61; RED)
    {
        cout <<"根节点为红色" <         return false;
    }
    //黑色结点数量各路径上相同
    //先走一条得到基准值
    int Blacknum &＃61; 0;
    Node* cur &＃61; _root;
    while (cur)
    {
        if (cur->_col &＃61;&＃61; BLACK)
            Blacknum&＃43;&＃43;;
        cur &＃61; cur->_left;
    }
    //检查子树
    int i &＃61; 0;
    return _IsRBTree(_root, Blacknum, i);
}

bool _IsRBTree(Node* root, int blacknum, int count)
{
    //递归到空节点
    if (root &＃61;&＃61; nullptr)
    {
        if (blacknum &＃61;&＃61; count)
            return true;
        cout <<"各路径上黑色节点个数不同" <         return false;
    }
    //子节点为红则检查父节点是否为红&＃xff08;通过父节点检查子节点会遇到空节点&＃xff09;
    if (root->_col &＃61;&＃61; RED && root->_parent->_col &＃61;&＃61; RED)
    {
        cout <<"存在连续红色节点" <         return false;
    }
    //计数黑结点
    if (root->_col &＃61;&＃61; BLACK)
        count&＃43;&＃43;;
    //递归左右子树
    return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
五、红黑树的删除
红黑树的删除不做讲解&＃xff0c;有兴趣可参考&＃xff1a;《算法导论》或者《STL源码剖析》
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
http://blog.csdn.net/chenhuajie123/article/details/11951777

六、红黑树与AVL树的比较
分析总结&＃xff1a;
红黑树和AVL树都是高效的平衡二叉树&＃xff0c;增删改查的时间复杂度都是O( )

红黑树不追求绝对平衡&＃xff0c;其只需保证最长路径不超过最短路径的2倍&＃xff0c;相对而言&＃xff0c;降低了插入和旋转的次数

所以在经常进行增删的结构中性能比AVL树更优&＃xff0c;而且红黑树实现比较简单&＃xff0c;所以实际运用中红黑树更多

附上源码

RBTree.h:

#pragma once
#include
#include
using namespace std;

//颜色
enum Colour
{
    RED,
    BLACK,
};
template
struct RBTreeNode
{
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;

    pair _kv;
    Colour _col;

    RBTreeNode(const pair& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(RED)
    {}
};

template
class RBTree
{
    typedef RBTreeNode Node;
public:
    RBTree()
        :_root(nullptr)
    {
    }

    void _Destory(Node*& root)
    {
        if (root &＃61;&＃61; nullptr)
            return;

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;
        root &＃61; nullptr;
    }
    ~RBTree()
    {
        _Destory(_root);
    }

    Node* Find(const K& key)
    {
        Node* cur &＃61; _root;
        while (cur)
        {
            if (cur->_kv.first > key)
            {
                cur &＃61; cur->_left;
            }
            else if (cur->_kv.first             {
                cur &＃61; cur->_right;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }

    pair Insert(const pair& kv)
    {
        //空树的情况
        if (_root &＃61;&＃61; nullptr)
        {
            _root &＃61; new Node(kv);
            _root->_col &＃61; BLACK;
            return make_pair(_root, true);
        }

        //查找位置插入节点
        Node* cur &＃61; _root, * parent &＃61; _root;
        while (cur)
        {
            if (cur->_kv.first > kv.first)
            {
                parent &＃61; cur;
                cur &＃61; cur->_left;
            }
            else if (cur->_kv.first             {
                parent &＃61; cur;
                cur &＃61; cur->_right;
            }
            else
            {
                return make_pair(cur, false);
            }
        }

        //创建链接节点
        cur &＃61; new Node(kv);
        Node* newnode &＃61; cur;
        if (parent->_kv.first > kv.first)
        {
            parent->_left &＃61; cur;
        }
        else
        {
            parent->_right &＃61; cur;
        }
        cur->_parent &＃61; parent;

        //父节点存在且为红&＃xff0c;则需要调整&＃xff08;不能存在连续的红色节点&＃xff09;
        while (parent && parent->_col &＃61;&＃61; RED)
        {
            //此时当前节点一定有祖父节点
            Node* granparent &＃61; parent->_parent;
            //具体调整情况主要看叔叔节点
            //分左右讨论
            if (parent &＃61;&＃61; granparent->_left)
            {
                Node* uncle &＃61; granparent->_right;
                //情况1&＃xff1a;叔叔节点存在且为红
                if (uncle && uncle->_col &＃61;&＃61; RED)
                {
                    //修改颜色&＃xff0c;继续向上检查
                    granparent->_col &＃61; RED;
                    parent->_col &＃61; uncle->_col &＃61; BLACK;

                    cur &＃61; granparent;
                    parent &＃61; cur->_parent;
                }
                else//情况2和3&＃xff1a;叔叔节点不存在 或者存在且为黑
                {
                    //单旋(三代节点为斜线)&＃43;变色
                    if (cur &＃61;&＃61; parent->_left)
                    {
                        RotateR(granparent);

                        granparent->_col &＃61; RED;
                        parent->_col &＃61; BLACK;
                    }
                    else//双旋(三代节点为折线)&＃43;变色
                    {
                        RotateL(parent);
                        RotateR(granparent);

                        cur->_col &＃61; BLACK;
                        granparent->_col &＃61; RED;
                    }
                    //旋转后不需再向上调整了
                    break;
                }
            }
            else//parent&＃61;grandparent->right
            {
                Node* uncle &＃61; granparent->_left;
                if (uncle && uncle->_col &＃61;&＃61; RED)
                {
                    parent->_col &＃61; uncle->_col &＃61; BLACK;
                    granparent->_col &＃61; RED;

                    cur &＃61; granparent;
                    parent &＃61; cur->_parent;
                }
                else
                {
                    if (cur &＃61;&＃61; parent->_right)
                    {
                        RotateL(granparent);

                        parent->_col &＃61; BLACK;
                        granparent->_col &＃61; RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(granparent);

                        cur->_col &＃61; BLACK;
                        granparent->_col &＃61; RED;
                    }
                    break;
                }
            }
        }

        //确保根节点为黑
        _root->_col &＃61; BLACK;
        return make_pair(newnode, true);
    }

    bool IsRBTree()
    {
        if (_root &＃61;&＃61; nullptr)
        {
            return true;
        }

        if (_root->_col &＃61;&＃61; RED)
        {
            cout <<"根节点为红色" <             return false;
        }

        int Blacknum &＃61; 0;
        Node* cur &＃61; _root;
        while (cur)
        {
            if (cur->_col &＃61;&＃61; BLACK)
                Blacknum&＃43;&＃43;;
            cur &＃61; cur->_left;
        }

        int i &＃61; 0;
        return _IsRBTree(_root, Blacknum, i);
    }

private:
    bool _IsRBTree(Node* root, int blacknum, int count)
    {
        if (root &＃61;&＃61; nullptr)
        {
            if (blacknum &＃61;&＃61; count)
                return true;
            cout <<"各路径上黑色节点个数不同" <             return false;
        }

        if (root->_col &＃61;&＃61; RED && root->_parent->_col &＃61;&＃61; RED)
        {
            cout <<"存在连续红色节点" <             return false;
        }

        if (root->_col &＃61;&＃61; BLACK)
            count&＃43;&＃43;;

        return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
    }

    void RotateL(Node* parent)
    {
        Node* subR &＃61; parent->_right;
        Node* subRL &＃61; subR->_left;
        Node* parentP &＃61; parent->_parent;

        parent->_right &＃61; subRL;
        if (subRL)
        {
            subRL->_parent &＃61; parent;
        }

        subR->_left &＃61; parent;
        parent->_parent &＃61; subR;

        if (parent &＃61;&＃61; _root)
        {
            _root &＃61; subR;
            subR->_parent &＃61; nullptr;
        }
        else
        {
            subR->_parent &＃61; parentP;
            if (parentP->_left &＃61;&＃61; parent)
            {
                parentP->_left &＃61; subR;
            }
            else
            {
                parentP->_right &＃61; subR;
            }
        }
    }

    void RotateR(Node* parent)
    {
        Node* subL &＃61; parent->_left;
        Node* subLR &＃61; subL->_right;
        Node* parentP &＃61; parent->_parent;

        parent->_left &＃61; subLR;
        if (subLR)
        {
            subLR->_parent &＃61; parent;
        }

        subL->_right &＃61; parent;
        parent->_parent &＃61; subL;

        if (parent &＃61;&＃61; _root)
        {
            _root &＃61; subL;
            subL->_parent &＃61; nullptr;
        }
        else
        {
            subL->_parent &＃61; parentP;
            if (parentP->_left &＃61;&＃61; parent)
            {
                parentP->_left &＃61; subL;
            }
            else
            {
                parentP->_right &＃61; subL;
            }
        }
    }

private:
    Node* _root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
test.cpp:
#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"
#include
#include
#include
#include

void TestRBTree()
{
    //int a[] &＃61; { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    //int a[] &＃61; { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    RBTree t;
    int n &＃61; 1000000;
    srand(time(0));
    for (int i &＃61; 0; i     {
        int e &＃61; rand();
        t.Insert(make_pair(e, e));
    }

    //t.InOrder();
    cout < }
void test_RBTree()
{
    int a[] &＃61; { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    RBTree t;
    for (auto e : a)
    {
        t.Insert(make_pair(e, e));

    }
    cout < }
int main()
{
    test_RBTree();
    TestRBTree();
    return 0;
}