【CPP】各种各样的树（9）——自顶向下的红黑树

本以为春节后马上就能写完这些树了，结果没想到一拖再拖居然拖到了开学前，很真实。红黑树还是蛮难的，写着写着才意识到应该先搞完B树然后再写2-3-4树然后再来讲红黑树的，然而还是按照计划勉强这么写了吧，B树之类的之后再来补上。

红黑树是在1972年由鲁道夫·贝尔发明的，被称之为"对称二叉B树"。它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它虽然是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：虽并不追求每个结点的绝对平衡，但综合可以在O(log n)的时间内做查找，插入和删除。

红黑树作为自平衡二叉树在实际中使用范围要比AVL树更加广泛，更加值得我们去掌握。在这里我想先链接一下网上的几篇文章：

• 简书上的这篇文章虽然后面写的有些杂乱，但是前面对于红黑树与2-3-4树的联系写的不错：https://www.jianshu.com/p/37c845a5add6
• CSDN上的这篇文章总体是跟随《数据结构与算法分析》的思路写的，实现了自顶而下的红黑树，对于书中没有详细解释的红黑树删除描述的比较详细，我的代码就参照了它的文章http://lib.csdn.net/article/c/19572
• wiki上的红黑树词条则清晰地描述了自底向上的红黑树的实现，这种实现实际上更加复杂，占用的空间也要更多些，不太推荐，但是写的条理很清晰https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

在粘贴完上面的三篇文章后，很不负责任地说其实只要认真把这三篇啃下来红黑树就可以算是理解了，在这里我贴贴我的实现，思路都分步写在了代码注释里面了，而详细的理论解释看看上面那几篇文章应该会更清楚些。我这份代码写的杂乱了些，主要是不喜欢使用Weiss书里的NullNode写法，还是使用了传统的nullptr来表示空结点。首先还是头部分：

红黑树的特色是每个结点都被染上了红色或者黑色，然后红黑树平衡的原理是通过让树在插入删除中始终遵循着红黑树的四条规则：

1. 节点是红色或黑色。
2. 根是黑色的。
3. 从每个叶子到根的所有路径上不能有两个连续的红色节点。
4. 从任一节点到其每个NULL指针的所有简单路径都包含相同数目的黑色节点。

使用红黑树就像在带着镣铐跳舞，不断地调整树的结构来达成平衡，由于这个实现是自上而下不回头的，所以这里我们先保存四世的指针，如果是自底向上的实现则类似之前的伸展树，要给每个结点多保存一个parent指针。

然后我们编写自动旋转，设置好根节点，写一个稍改动的Display函数，然后就按照注释中的思路写一个重定位函数，这个函数将会被下面的Insert函数所调用。

插入新节点的操作本身是不复杂的，红黑树最复杂的地方在于它的删除操作，由于要考虑到很多的情况红黑树的删除甚至有些树不会去详细描写它。但是红黑树删除再复杂也希望大家能看完它，自顶向下的删除操作没有自底向上的操作那么复杂，它的思路有些类似于解开一个递归函数，利用循环来模拟递归，改变几个常驻的指针来当作传递参数，然后在每次中努力地将树的状态转换为父结点为红，目标结点为黑的初始状态，然后通过里面Step2的各种操作来将目标结点变为红色以达成红色结点下移的目的。下移红色结点也是为了达成刚才说的递归的初始状态。而之所以要把目标结点变为红色则是因为红黑树的删除最简单的方法就是删除红色的叶子结点，删除红叶是不会对树的结构造成改变的。而对于中间出现的红色结点我们则利用之前常常用到的替换结点伪递归删除的方法来解决。所以其实在这里红黑树的删除就是一个构造初始条件（红色结点）然后来套用二叉查找树一般删除方法的过程。而如何构造这个初始条件就看看代码和第二篇文章的图文解释就好。

理解完删除就只剩下几个细节函数要实现了，然后便是测试部分，可以看到红黑树能达到较为高效的平衡效果。

啊，终于勉强算是在暑假结束了树的部分了，看一下树的第一篇文章【CPP】各种各样的树（1）——二叉森林树在文章开头立下的目标也算是都写完了。有些累，接下来该好好开学写些别的东西了，树的东西暂告一段落，接下来是什么还没想好。如果还有树的文章的话就是B-树，2-3-4树，treap树，trie树，AA树，k-d树吧...想想也是很大的坑啊（笑