红黑树

在红黑树（RB tree）之前，一定要提二叉查找树（binary search tree）。

最普通的二叉查找树，就是保持“左<=父<=右”的形式的一棵树。由于将数据在某一个子树的范围内分成大小两部分，因此可以避免不必要的查找，从而节省了时间。如果用线性非有序的结构存储，每次查找都要遍历一次，复杂度为O(n)，若为有序的，可以用二分查找，复杂度为O(log n)，而排序需要O(n*log n)。但通常很多数据是在线维护的——即并非所有数据一次性存储再查找而是随时插入新元素，也随时进行查找甚至删除。因而线性数据结构的维护性能很低。而二叉查找树由于插入和查询都类似二分因而期望复杂度均为O(log n)，且由于类似链表的数据结构让删除很容易进行，所以性能更好。

但问题来了，虽然理论上数据是分为比父节点大和小两部分的，但一旦所有数据都比父节点大或者小，那么一头很大一头很小，就让这个节点上的二分失去意义。进而得出，如果数据是按照递增或者递减的顺序，BST会蜕化为一条线，而且是一个链表。链表无法进行随机访问，只能按照顺序依次遍历，而且树形算法中我们查找一个元素总是从根节点开始遍历，因而查询和插入的复杂度会蜕化为与线性结构一个数量级。

任何一个算法都要考虑特殊数据的蜕化问题，比如快排有可能蜕化成平方级。有时我们通过随机来让平均期望很小以尽量避免极端情况，比如快排可以随机选取中点，因为我们已经知道了所有数据。但由于BST是随时插入随时查询，我们无法使其按照我们的意愿把所有数据打乱随机再一个个插入，因此我们需要在数据结构上避免BST出现极端情况（即随时保持平衡）。于是又了AVL、红黑树等改进的BST。记住，他们依然是二叉查找树，因为依然要满足“左<=父<=右”，或者说，在不修改结构的情况下，单纯看查询过程，都应该是一样的。

所以任何改进BST的本质就是如何通过一些操作来让失去平衡的BST变得平衡。所谓的平衡，就是让每个叶子节点的深度都几乎相等，或者最深的和最浅的在一个可以接受的范围内。而这一过程称为“旋转”——让深的变浅，浅的变深，并保持BST的性质。

红黑树，顾名思义，在节点上赋予颜色，红和黑。每个节点要么是红的，要么是黑的，并且人为规定每个叶子都是一个为空的黑色节点。根节点为黑，每个红色节点的两个子节点均为黑。此外，任何一个节点从此点到后续节点的所有路径经过的黑色节点数都一样多。以上这就是红黑树的性质。下面将为何这样做。

设bh(x)为结点x为根的子树的黑色高度（路径上有几个黑节点），所以x的两个子节点的黑色高度为bh(x)或bh(x)-1，即至少bh(x)-1。黑色高度意味着每条路径的黑节点个数据为高度值，因此如果子节点的子树中只有黑色节点，那么就是一棵高度为bh(x)或bh(x)-1的满二叉树，此树节点个数为2^(bh(x)-1)-1或2^bh(x)-1，我们取下界，即两个子节点的子树至少有2^(bh(x)-1)-1个节点。那么，以x为跟的子树节点数至少为(2^(bh(x)-1)-1)*2+1=2^bh(x)-1 。

由于红黑树中还有红色节点，因而h>=bh，又因为每个红节点的儿子一定是黑，而黑节点的儿子不限制颜色，因而黑节点数一定不小于红节点数，因此bh>=h/2。

于是  n>=2^bh-1>=2^(h/2)-1，移项，取对数，得h<=2*log(n+1)，因此红黑树的总高度得到了保障。虽然不是完美的的log n，但也能让查找的时间在数量级上实现O(log n)。AVL树在高度的限制上比红黑树严格（红黑树最大深度小于等于最小深度的二倍，而AVL要求最大深度只能比最小深度多1），理论上效率更好，但实际经验表明两者性能相近。

从原理上明白为何红黑树可以保持良好的BST特性之后，剩下的就是如何让每次插入后的树形都符合红黑树的性质了。

任何旋转都遵循一个道理，那就是“左<=父<=右”永远成立，记住这条就不难理解了。比如现在y是x的右子节点，意味着x<=y，那么我们可以通过旋转让y是x的父节点，所以x一定在新树的左侧。如果你画个图（我懒得画图了，虽然这种东西想讲明白，必要的图是必须的），就知道如果从旋转的角度考虑，这个操作相当于将x-y的边逆时针旋转，我们叫他“左旋”（left-rotate），反之就是右旋，两个操作互拟，先左再右就会得到原图。

这就是红黑树的核心操作。当然，因为x和y都还有其他子节点，因而同样画图就能明白，在左旋过程中，x的左节点依然是它的左节点，而y的左节点变成x，因为原来y下的所有点均大于x，因此y原来的左节点变成现在x的右节点，而y原来的右节点现在依然是y的右节点，成为x的兄弟。迷糊吗？迷糊就画图……

红黑树在插入的时候跟BST一样，因为都还是那个“左<=父<=右”，只不过红黑树的叶子节点都是空，所以额外处理一下就好。他俩真正的区别在于，红黑树插入之后，新的节点先定义为红色，这时候的树并不一定是红黑树，因为可能违背了某条红黑树性质，因此需要进行一个修复来保持性质。

修复是一个迭代的过程，自下而上，初始迭代对象x为新增红色节点。

然后就是一个需要很严谨的分情况讨论的过程…………

假如x的父节点是黑色，那么世界是和平的，树是红黑的，直接收工。

假如x的父节点是红的，那么就违反了红色子节点均为黑的性质。显然不能直接将x变黑，这里继续分情况讨论：

如果x的叔叔是红的，那么x的爷爷的两个儿子（就是x的父亲和叔叔）都是红的，因此将两者变黑，x不变。然后让x指向原来x的爷爷，继续迭代；

如果x的叔叔是黑的，继续分情况……看x是父亲的左儿子还是右儿子：

如果是右儿子，将这爷俩进行一个左旋，就变成“x的爸爸是红色，叔叔是黑色x是爸爸的左节点”。也就是跟下面的情况相同；

如果是左儿子（或者原本是右儿子左旋而来），那么此时x是红色，x的父亲是红色，x的爷爷是黑色，对x的父亲和爷爷进行一次旋转（看x的父亲是左儿子还是右儿子了），让原来的父亲变成新的根，x还是它的左儿子，原来的爷爷是右儿子。而且新根依然是黑色，不影响上一层的性质，而新子树也满足红黑树性质，因此迭代完毕。

以上就是插入后进行修复的全部情况。

除了插入之外，还应该支持删除操作。跟插入一样，都是按照SBT的方法进行，然后可能损害了RBT的性质，进行修复。

首先介绍一下普通二叉查找树的删除方式。因为删除会破坏二叉树结构，因而并非直接删除那个值的点。当然如果那个点是叶子，删除即可，如果只有一个子节点，删除并把子节点跟父节点连接就行。如果是在树丛中删某个点，就不能真的删它，而是它的后继。准确的说，是从左子树找最右侧的，或者右子树找最左侧的，把那个点按照前两个方案删除，然后用那个点的值把本应删除的点的数据覆盖掉。这样才能保证删除后依然为SBT。同样，看不懂，画图就理解了。

在RBT中，也是进行一样的操作，然后看被删除的点（实际树结构中被删除的点而非删除的值所在的点）的颜色，因为被删除的点要么是端点要么是一个直线上的，因此如果这个点是红色的，那么世界是和平的，树还是红黑的。

如果是黑色的，那么继续分情况讨论……

设那个黑色的点被删除后，补上来的点（原来的唯一儿子或者是空的子节点）是x。

此时，如果x的兄弟是红色，那么他的父亲一定是黑色，则将x的兄弟和父亲进行一次旋转并交换颜色（左旋还是右旋看x是左儿子还是右儿子，对称的操作）这时候x的新兄弟是原来兄弟的儿子，颜色为黑。此时不一定是红黑树，根据其颜色进入如下若干情况；

x的兄弟是黑色，且兄弟的两个孩子均黑。则让x的兄弟变红，x指向原来x的父亲。即若父亲为红，推出，为黑，迭代；

x的兄弟是黑色，兄弟的儿子左红右黑（此时相当于x是左儿子兄弟是右儿子，下同。相反情况则完全对称）。则将x的兄弟与它的红儿子旋转并交换颜色。这时变成下一种情况；

x的兄弟是黑色，兄弟的儿子右红左随意。则将x的父亲与兄弟进行左旋，并交换颜色。此时新的x的父亲为原来的兄弟，x的兄弟为原来兄弟的右红节点，将这个点变黑。x指向整个树的根，使其结束迭代。

这就是4种删除的情况。注意迭代的判定条件为x!=root&&color(x)==black，而且推出迭代后将此时的x变黑，无论之前什么颜色（主要是应对情况2）。

这就是及其恶心的红黑树的删除过程……而整个红黑树也就是这些。理论上就是这样，真写的话会及其蛋疼……

为什么要说红黑树呢，因为这个算是最常用的BST的实现方法之一，尤其是在c++ STL中使用。STL不提供直接的红黑树接口，但所有需要BST的容器均底层均用红黑树实现，比如set和map。只不过map是<key,value>，set是key=value。而存储的时候通过key进行排序，所以用迭代器遍历的话，set和map都是有序的。但只能改变value（因为不在树结构中存储），不能改变key（一旦改变树就不是BST更何况红黑树了，只能先删除再插入新的），因此set::iterator是const类，不能修改值。此外，与链表一样，进行插入、删除等操作不会损坏已有的迭代器，vector一类则不然。而且<algorithm>里的find(xx.begin(),xx.end(),value)函数虽然可以用于RBT实现的容器中，但由于是顺序遍历，效率远没有自带的如set.find(value)高，原因应该都明白。

此外，字典的实现方式并不只有BST一种，还有一种方式是哈希。Java的hashMap什么的就是通过哈希实现，但由于不是左<=父<=右，因而hashmap迭代器不是按大小顺序的。至于哈希是如何实现的，那又是一个得又臭又长的文章才能写完的了……