红黑树详解：性质、查找、插入与删除操作

红黑树详解：性质、查找、插入与删除操作

红黑树是一种常用的数据结构，在C++标准库中，为了能够节约平衡时间，map和set都使用了红黑树而不是AVL树（当然不是BST因为它不平衡）。

红黑树的基本概念

BST因为不平衡，查找的糟糕情况可能退化成链表，所以我们考虑使用AVL，这样就保证了查找速率在O(logn)，但是AVL需要经常平衡。

红黑树有两者的优点：平衡快，查找速度也能到O(logn+k)的级别。这是它的几个性质所带来的：

1. 它所有的节点分为红色和黑色
2. 根节点是黑色（实际上只要在删除和插入的时候处理就可以）
3. 红色节点不能连续
4. 任何一条到叶子节点的路径上，黑色节点的数量都相同。
5. 空叶子节点必须是黑色。

第3条和第4条导致了最长和最短路径之间差距不会超过一倍，在最差的情况下只有一条最长，其他的长度都是最短，那么最长那条路径用来查找也不过是O(logn)级别的。又由于没有AVL要求那么严格，所以需要平衡的次数变少了。

第2条有利于后面的递归插入和删除。

在查找中，红黑树和所有排序树一样，按照左中右的顺序依次增大，因此查找方式也没有变化。

对于插入和删除导致的不平衡，为了让它变为少数现象，所以我们增加了额外的规定：插入的节点初始置为红色（这样不会影响这条路径上黑色节点的数量）。

插入操作

如果插入节点的位置的双亲节点不是红色，那就完全不需要调整。我把要调整的情况称之为双红。

对于双红来说，它的祖父母一定是黑色（因为不连续）。双红的核心问题是一个必须变为黑色，为了能够保持递归传递性，我们考虑使用双亲节点变黑色。

我们调整的思路是这个唯一的缺点是双红，不要引入其他的东西（比如黑色节点数量不平衡）。

1. 所以我们首先考虑如果只是染色是否能够解决问题，如果双亲的兄弟姐妹是红色就很好办，直接让祖父母变成红色，然后双亲和双亲的兄弟姐妹都变成黑色就行。（Case1)
   这就可以让祖父成为新的双红，往上走能够靠根节点改变颜色不损伤黑色节点数平衡，向下走可能会有无法解决的麻烦。

2. 如果是双亲的兄弟姐妹是黑色，那么它们就不能染色了直接解决了，需要看兄弟姐妹的孩子能不能帮忙解决问题（让红色的后代挑起支脉大梁，成为黑色，而让它们的父母变为家主）
   2.2. 如果有红色的话，我们可以想办法让这个红色变成黑色，然后让这个支脉留在这里，把另外一个支脉过继给祖父母，祖父母不再担任黑色大任后可以换色。
   2.2.1. 如果远离插入节点的一脉表亲是红色，那么它就可以直接变成黑色，然后让祖父母到双亲那一脉去，让双亲有机会和祖父母交换颜色变成黑色。（Case2）
   2.2.2. 如果靠近插入节点的一脉表亲是红色，那么因为它们的顺序原因导致它不能直接被过继，所以它应该到远离的支脉去。（Case3)
   这样我们就得到了Case2的情形。

3. 如果不仅双亲的兄弟姐妹是黑色，表亲也是黑色，那么双亲的兄弟姐妹那脉就难以提供帮助，但是祖父母可以让双亲继位，自己去作为连接它两个孩子的桥梁。（Case4）

简单来说就是双亲必然变成黑色，威胁到祖父母，要么让祖父母让位给它们，要么祖父母让位给它们的兄弟姐妹。如果兄弟姐妹那边的王位有红色儿女能够继承就让兄弟姐妹登基，没有就只能镇守王庭看着双亲继位。如果表亲的继承人在内部，看到这样的机会，就会很快先篡位王庭再登基，如果在外部就来不及回来，只能作为贤德的王太子继承王位。

删除操作

对于删除来说，和AVL一样，只会删除右子树的最左边那个位置（后继节点），为了平衡先不变颜色。

如果删掉了红色，没有什么影响，让这个位子的后代顶上就行（因为最左只有右孩子，独生子女）

如果删掉了黑色影响就会比较大，因为黑色节点不平衡了。但是这个整体的红黑树可能很大，不能通过偷兄弟姐妹的黑色节点来达到整体平衡，所以我们必须制造一个黑色的节点到这边来。

1. 如果兄弟姐妹是红色，没有什么好办法可以用，只能让父母下来帮忙，让兄弟姐妹变成黑色挑起大梁，过继兄弟姐妹的孩子给父母，在新的环境中，兄弟姐妹就变成黑色了（Case1)
2. 如果兄弟姐妹是黑色，那就看兄弟姐妹的孩子能不能挑起它那边的大梁，让父母到我这边来帮助我（父母变黑，兄弟姐妹变成父母颜色）
   2.1. 如果兄弟姐妹的孩子在外面，就会乖乖回来直接变成王太子，把它的兄弟姐妹（被删除节点兄弟姐妹的另一个孩子）驱逐出这个地方，给黑色的祖父母。（Case2)
   2.2. 如果兄弟姐妹的孩子在内部，就会篡位成王再登基，和插入时一样。(Case3)
3. 如果兄弟姐妹和它们的孩子全是黑色，那么只能靠递归到根节点解决这个不平衡问题了。
   3.1. 如果双亲是红色，直接变黑，让被删节点的兄弟姐妹变红，递归结束。(Case4)
   3.2. 如果双亲是黑色，那么就让两个孩子都差一个黑节点，于是把被删除节点的兄弟姐妹也变成红色，这样双亲就是新的缺黑节点了，往上递归一直到根节点（根节点只有两个孩子节点，当然没有其他树，少一个黑色节点也是新平衡），或者被解决(进入其他Case)。（Case5)

简单来说就是被删节点一脉缺黑了，必须要有新王出现。要么父母不是皇帝，父母登基，自己成王；或者父母新登基，把被删点的兄弟姐妹降级和被删点一致；如果父母是皇帝，要么父母让兄弟姐妹的王庭完蛋，父母降级为王；要么兄弟姐妹是红色可以直接继位，兄弟姐妹一脉的王太子发卖它的兄弟姐妹；要么兄弟姐妹一脉的王太子在内部篡位，再登基成皇。