数据结构和算法：红黑二叉树
（点击上方公众号，可快速关注）
来源：taozj
taozj.org/201611/data-structure-and-algorithm-(3)-rbtree.html
AVL自平衡二叉树在教科书上比较常见，因为是最先提出的自平衡二叉树，自然是学术价值比较的高，但是目前工业环境觉得名为红黑二叉树(Red-Black Tree)的自平衡二叉树使用的更为的广泛，比如C++标准库中的有序容器(std::set、std::map)，Linux内核中的很多数据结构等，都是用的RBTree来维护管理的。
当看完RBTree后发现，其实相对来说AVL自平衡树比RBTree更加的平衡，理论上访问效果也会更好，但是为此AVL自平衡树在插入、删除修改树结构的时候，会引入更多的旋转操作来保持平衡，所以对于经常需要添加、删除的高动态数据来说，维护这种数据结构的代价显得十分高昂，而RBTree对于树的高度限制相对要宽松的多，等于是在牺牲了部分完全性(平衡性)的条件下，以换取插入、删除操作时少量的旋转操作(但是一调整起来复杂的情况麻烦的要死~~~)。
一、红黑二叉树简介
说到红黑二叉树，不得不先请出红黑树的基本法则，虽然简单，但是维护起来还是挺复杂的：
(1). 节点都有颜色标记，且只能是红色或黑色。
(2). 根是黑色。
(3). 所有叶子都是黑色（叶子是NIL/nill_节点，不保存实际的数据）。
(4). 每个红色节点必须有两个黑色的子节点，也可以表述为从每个叶子到根的所有路径上不能有两个连续的红色节点。
(5). 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
上述这些条件中，(1)(3)是很容易遵守的，(2)只有确实在操作到根节点的时候需要注意调整一下就行了，而(4)(5)是维持红黑树结构中常常会用到的准则。
之所以要有上面的条件和规则，就是为了这么一个保证：从根到任何一个叶子，最好的情况是整条路径全部都是黑色，假设为N，最坏的情况是黑色和红色交替的情况，那也不会超过2N，因此红黑二叉树对操作的复杂度作出了最差的保证。而维护这种数据结构，需要少量的颜色变更和不超过三次树旋转（对于插入操作最多是两次），虽然插入和删除很复杂，但操作时间复杂度仍可以保持为O(log n)而不会因为元素的数目增加而性能恶化。
之一个典型的红黑二叉树的样子。
二、红黑二叉树实现
二、红黑二叉树实现
此处还需要事先强调一下，红黑树再复杂也是一个基本的BST，所以和AVL自平衡二叉树一样，所有的插入和删除操作，也是先按照操作BST的基本方式进行插入、删除，然后再检查是否平衡而做出相应调整，RBTree的调整操作包括着色重绘和旋转操作。
2.1 节点数目
1 2 3 4 5 6 7 8 9 | class RBNode { private: int data_; SmartNodePtr left_; SmartNodePtr right_; SmartNodePtr parent_; enum Color color_; ... }; |
和之前的AVL平衡二叉树一样，节点所有指针域都使用了智能指针，这样在删除的时候只需要更改指针域，智能指针维护引用计数，并在必要的时候自动析构节点并释放内存。但和AVL Tree节点不同的是，这里多了一个parent_节点，因为在后面对RBTree做维护的时候，会有大量涉及到父亲、兄弟节点的操作，而这些亲戚节点的访问，以及当前处于左还是右子树的判断，都需要parent_域辅助完成。
2.2 插入操作
规定，新增加的节点着色必须是红色。插入操作分以下情况：
(1). 如果此时还是空的红黑树，则该节点为根节点，将其重绘为黑色，然后返回；否则进行步骤(2)
(2). 根据BST递归查找，找到可以插入的位置时候，创建新节点后进行BST插入(更新parent_、left_、right_指针域)，然后进行步骤(3)
(3). 如果父亲节点P是黑色，此时红色节点作为孩子是允许的，红色节点的加入不会影响黑色路径的计数，原先父亲的叶子节点黑色由新插入节点的叶子节点继承，对于(4)(5)规则没有任何影响，操作完成直接返回；否则进行步骤(4)
(4). 父亲节P点是红色的，如果此时叔父节点U也是红色的，而且此刻确定祖父节点G是黑色的，进行如下操作：将祖父节点G重绘为红色，将父亲P和叔父节U点重绘为黑色，此处操作虽然子树平衡了，但是修改了祖父节点G可能导致祖父节点G和其他节点不平衡，以祖父节点G为参数重新进入步骤(3)检查递归；否则进行(5)
(5). 此时父节点P是红色、叔父节点U是黑色、祖父节点G是黑色、新增节点N是红色，根据插入节点N是父亲节点G的左孩子还是右孩子，以及父亲节点P是祖父节点G的左孩子还是右孩子分别组合，一共形成四种情况，依次处理
a. 如果祖父节点G、父亲节点P、插入节点N在一条直线上，即插入节点N是父亲节点P的左孩子且父节点P是祖父节点G的左孩子，或者镜像情况下插入节点N是父亲节点P的右孩子且父亲节点P是祖父节点G的右孩子，此时只需将祖父节点G改为红色，父亲节点P改为黑色，然后以祖父亲节点G为中心做一个相反方向的旋转就可以了；
b. 如果祖父节点G、父亲节点P、插入节点N不在一条直线上，此时需要以父亲节点P为中心，事先进行一次旋转使得祖父节点、父亲节点、插入节点三者在一条直线上，然后就可以按照a的情况所对应的步骤进行处理了；
至此，红黑树的插入操作完成。
2.3 删除操作
红黑树的删除操作算是比较复杂的数据结构操作了，分出的情况比较的多，而且操作过程中涉及到的亲戚节点也比较多。
此处需要说明的是，所有BST的删除操作，都可以转换看作是单个子树的删除操作，因为删除的节点只可能有三种情况：叶子节点，这时候可以将任意一个NIL节点看做单个子树；含有一个子树的节点；含有两个子树的节点，此时按照BST的删除操作，还是会寻找一个左子树最大值或者右子树最小值替换他，并将替换节点重绘成删除节点的颜色，然后问题实质上就转化成替换节点的删除了，而替换节点不可能有两个子树的情况。
(1). 如果整个RBTree为空，直接返回；否则进入(2)
(2). 查找当前节点是否待删除节点，如果不是递归进行左树或者右树删除，如果遍历完了还未找到直接返回，否则当前就是待删除节点，进入步骤(3)
(3). 如果当前待删除节点的右子树为空，表明无法找到一个用于替换的右子树最小值节点，直接进入步骤(4)，否则查找右子数最小节点，和当前节点进行数据部分的交换(而位置关系、着色得以保留)，然后将待删除节点设置为替换节点，进入步骤(4)，至此我们找到了需要真正进行删除操作的节点N
(4). 寻找当前删除节点node的非NIL子树(如果当前节点两个孩子都是NIL那就选随便选一个假设为非NIL)作为child，然后判断当前节点是否是根节点而需要做特殊处理(此处不展开这种情况，只考虑一般的删除节点)，对于一般的删除情况，通过将node父节点指针引用到child而使用child顶替当前删除节点node，node的引用计数减少(后续会被自动析构释放)，而且此时如果删除掉的节点node是红色的，那么表明被删除节点的父亲和孩子child都是黑色的，最主要的是删除一个红色节点不影响RBTree的规则，此处就可以直接返回了；否则进入步骤(5)
(5). 此处删除掉的节点node是黑色的，而如果替换的child是红色的，那么将孩子重绘为黑色，这样原来通过黑色删除节点的路线现在都由孩子去作为黑色节点顶替了，红黑树的特性没有被破坏，直接返回；否则进入步骤(6)
(6). 进入步骤(6)就是传说中最复杂的double black情况了，在所有讨论之前这里先声明，到达这里节点的删除工作已经完成，接下来的都是调整工作了。我们将主角命名为N，其本质就是(4)操作中顶替的child节点，原先的祖父节点现在是父亲节点，原先的叔父节点现在是兄弟节点，且此时节点N是黑色的。检测兄弟节点S如果是红色，那么父亲节点P肯定是黑色，此时重绘父亲节点P成红色，重绘兄弟节点S为黑，并且如果N是父亲节点P的左儿子，则以父亲节点P为中心进行左旋操作，否则进行右旋操作，经过这一步调整，N有了一个黑色的兄弟节点和一个红色的父亲节点，但是N和现在兄弟节点S原来的儿子(现在的兄弟)挂着子树上黑色节点的数目肯定不一样，子树是不平衡的，所以还需要继续进行下面的处理，进入步骤(7)
(7). 无论是原生的还是经过步骤(6)修改得到的，此处兄弟节点S是黑色、N是黑色，然后检查兄弟节点S的两个孩子的颜色，如果兄弟节点S的两个孩子都是黑色，那么就根据父亲节点P的颜色进行讨论
a.如果此时父亲节点P的颜色是红色，则重绘兄弟节点S成红色、重绘父亲节点P成黑色，通过这样后原先删除掉的黑色节点就由父亲节点P补偿回来了，而兄弟节点S的整个分支没有改变，满足红黑树条件，就直接返回；
b.如果父亲节点P的颜色是黑色，则重绘兄弟节点S成红色，此时虽然得到的整个子树是平衡的，但是原先经过兄弟节点S的子树都减少了一个黑色，此处需要以父亲节点P为参数步入步骤(4)重新调整；
如果兄弟节点S的两个孩子不都是黑色，此时步入步骤(8)
(8). 此时兄弟节点S是黑色、N是黑色，而且兄弟节点S的两个孩子至少有一个是红色的，但是父亲节点P多次递归已经不确定颜色了，然后当Parnet-Sibling-r_child不在一条线上面时(此时兄弟节点S的孩子由一个红色和一个黑色构成的时候，假设红色孩子记为r_child)，需要先旋转成一条线，同时进行颜色的修正，把兄弟节点S改成红色且r_child改成黑色，经过这个旋转后的子树是满足二叉树性质的，但是N和新的兄弟节点S不平衡(本身这个操作不会涉及到N和父亲节点P)，而且这个不平衡的情况刚好会fall through到下面步骤(9)的情况处理；而如果Parnet-Sibling-r_child在一条线上面(这其实就是前面旋转着色后的结果)，直接进入步骤(9)处理
(9). 此时兄弟节点S是黑色，且依次挂了红色孩子、黑色孙子一条线的子树，操作是通过以父亲节点P为中心进行旋转，让原来的兄弟节点S代替父亲节点P的颜色，同时重绘原来父亲节点P成黑色，重绘原来兄弟节点S的孩子成黑色。
由于原先的父亲节点P和现在兄弟节点S的颜色是不确定的，无非做两种情况进行讨论：a. 父亲节点P原先是黑色的；b. 父亲节点P原先是红色的，看图可以直接分析出来，修改之后这条子树到其所有子叶的黑色节点数目和原先都是一样的，满足红黑树条件，删除结束。
按照维基百科的红黑树解释的代码，自己修改整理了一下并附上注释，代码已经上传了，欢迎各位Review。http://github.com/taozhijiang/learncpp
觉得本文有帮助？请分享给更多人
关注「算法爱好者」，修炼编程内功