@[toc]

红黑树

时间复杂度

是一种确保拥有对数级高度的二叉搜索树。

能保证在最坏的情况，所有动态操作的时间复杂度内为O(logn)。

问题一：STL中的set底层使用了什么数据结构？

答：红黑树

STL中set、map、multiset 、multimap底层都是红黑树。

java集合框架底层中 TreeMap 和 TreeSet的数据结构是红黑树。

问题二：红黑树有哪些性质？

同时满足以下四个性质：

1）每个节点或是红的，或者是黑的。

2）根节点和每个叶子节点(NIL)是黑色的

3）如果一个节点是红色的，那么他的两个儿子都是黑的。

4）对于每个节点，从该节点到子孙节点的所有路径上包含相同数目的黑色节点。

如图为一种红黑树

如果一棵树所有的节点颜色都是黑色，那么很容易满足红黑树性质，但是难点在于，在动态的删除和插入时，如何还能保证二叉搜索树有红黑树的性质。

关于红黑树的高度与证明

可以保证红黑树的高度 h <= 2log₂(n+1)

证明：

以上图为例，因为根据红黑树红色节点的双亲一定是黑色节点，可以将红黑树的红色节点并入到双亲节点

然后会成为下图：

这是一颗2-3-4树。

每个节点的叶子节点可以是2个3个和四个。

很明显，构成的这棵2-3-4树，还有一个性质，就是所有的叶子节点都有相同的黑高度。

假设之前的红黑树的高度是h ，现在这棵2-3-4树的高度是h₁

根据红黑树的第三个性质，红色节点不可能连续，从根节点到任意一个叶子节点的路径，红色节点的数量肯定不会过半。

得到 h < = 2h₁

因为红黑树除了叶子节点，所有的节点度都为2，所以n个非叶子节点，就有n+1个叶子节点。

可以归纳的证明，当红黑树只有1个根节点时，有2个叶子节点，

在这之后，每插入一个节点，首先会-1个叶子节点，然后会+2个叶子节点

-1+2 = +1

所以n个非叶节点，就有n+1个叶节点。

对于这棵2-3-4树，因为树的高度是h₁,想知道叶节点数leaves的范围，那么下界的情况应该是每个节点的子节点数都是2，上界的情况应该是每个节点的子节点数都是4

那么 2^h1 <= leaves <= 4^h1

已经知道，leaves = n+1

所以2^h1 <= n+1

两边取对数，得到

h₁ <= log₂(n+1)

因为h <= 2h₁

所以 h <= 2log₂(n+1)

问题三： 红黑树的数据结构怎么定义？

enum Color{
    RED = 0;
    BLACK =1;
};
struct RBTreeNode{
    struct RBTreeNode *left,*right,*parent;
    int key;
    int data;
    Color color;
}; 

关于红黑树的更新操作：插入和删除

在插入和删除节点时，为了维护红黑树性质，一般需要：

1）重新着色，为周边的节点重新着色

2）对树进行重新排列，即旋转

左旋和右旋

对同一个节点，左旋和右旋是可逆的

这种操作保持了二叉搜索树的性质。

左旋或者右旋后，其中序遍历序列都为 ：{ X 、 A、  Y、  B、  Z}

因为只需要修改一些节点的指针，所以这种操作是时间复杂度是常数级的

重新着色和旋转过程

1）首先根据平衡搜索树的性质，判断插入节点的key值应该插入的位置

2） 对这个节点进行染色，染为红色

​ 为什么是红色，因为BST树根节点是一开始初始化好的，那么要插入的节点肯定不会 一定是黑色，因为那样会违反性质2。关键是性质4，一定会维持，如果插入的是红节点，那么所有节点的黑高度肯定不会发生变化。

​ 但是如果插入节点的是红色，有可能会违反性质3。

​ 可以修补破坏的性质3 ， 把破坏带来的结果一步步上移，从节点X开始，往根节点上移。

​ 先考虑重新着色，上色不了再考虑旋转；

​ 旋转之后，可能还要重新着色

以上图代码为例

在这棵树插入15，

这个时候11 和 15 都是红色，产生冲突，需要重新着色

幸运的是，因为15的祖父节点的颜色是黑色，并且15祖父节点的两个孩子节点的颜色都是红色，那么刚好可以将10重新着色成红色，8和11重新着色为黑色。

这个时候10和18都是红色会产生冲突，但是10的祖父节点的两个孩子一个是红色一个是黑色，不能像刚才那样重新着色（先不论根节点不能为红色），所以需要旋转，进行右旋。

这个时候，7， 10 ， 18 三个节点会在一条线，而不是人字形折了一下，正是我们想要的。

这个时候，再将根节点左旋，会得到

这个时候，10的左子树的黑高度会+1，右子树的黑高度会-1，将7重新染色成红色，10染色成黑色

此时红黑树满足四条红黑性质。

红黑树伪代码

情况A和情况B

RB-INSERT(T X)    
    TREE-INSERT(T X);        //首先平衡树操作，找到节点要插入的位置
    color[x] = RED;           //要插入的节点为红色
    
    //从插入的节点一直开始上移到根节点或者当前节点染成黑色,用循环表示
    while(X != root[X] || color[x]!=BLACK) 
        
        do if(p[x] = left[p[p[x]]])            //称之为A类情况
            
            y = right[p[p[x]]] ;
            
            if(color[y] = RED)
            
                Then <Case 1>
                
            else 
                if(x = right[p[x]])        //x是父节点的右孩子，p[x]是x祖父节点的左孩子，即“人”形状 
                
                    Then <Case 2> 
                
                Then <Case 3>
            
        else if(p[x] = right[p[p[x]]]) {    //称之为B类情况，与A类镜像 
            //同A情况，镜像处理 
            
            
            
            
            
        } 
        //将根节点染成黑色，如果根节点被染成了红色，则需要改为黑色，因为维护性质1，但是并不会对
        //左右子树造成影响违反其他性质。 
        color[root[T]] = BLACK 
        

对于情况A：
Case1:
    如果x与p[x]冲突都为红色，而且y = right[p[p[x]]] 也为红色，那么可以将p[x]和y重新着色成黑色，将p[p[x]]重新着色为红色

Case2:
    此时，如果x是p[x]的右孩子，p[x]是p[p[x]]的左孩子。
    如果x与p[x]冲突都为红色，但是y = right[p[p[x]]] 为黑色，那么可以p[x]右旋。
    此时x是p[x]的左孩子，p[x]是p[p[x]]的左孩子

Case3:
    此时x是p[x]的左孩子，p[x]是p[p[x]]的左孩子,将p[x]左旋，并将p[p[x]]重新着色为红色。    

红黑树相比于BST和AVL树有什么优点

红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。红黑树的算法时间复杂度和 AVL相同，但统计性能比 AVL 树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于 AVL 树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL 树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

红黑树相比于哈希表，在使用时有什么依据？

权衡三个因素: 查找速度, 数据量, 内存使用，可扩展性。总体来说，hash 查找速度会比 map 快，而且查找速度基本和数据量大小无关，属于常数级别;而 map 的查找速度是 log(n)级别。并不一定常数就比 log(n)小，hash 还有 hash 函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash。但若你对内存使用特别严格， 希望程序尽可能少消耗内存，那么一定要小心，hash 可能会让你陷入尴尬，特别是当你的 hash对象特别多时，你就更无法控制了，而且hash 的构造速度较慢。红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。