红黑树（第一章：基础）
1. 前提条件

红黑树（Red-Black Tree）是一种：

 自平衡二叉搜索树（Self-Balancing BST）

它和 AVL 一样：

左子树 < 根 < 右子树
中序遍历仍然是有序序列
查找、插入、删除平均都是
O(log n)

所以：红黑树 = BST + 自动保持平衡

为什么还要发明红黑树？

因为BST：

插入：

1

2

3

4

5

会变成：

1
 \
  2
   \
    3
     \
      4
       \
        5

高度：5

查找：O(n)

于是AVL 出来了。

AVL：任何节点：

左右高度差 ≤ 1

非常平衡。

但是：

AVL 的缺点：

插入旋转较多

删除旋转更多

工程上：例如：

Linux 内核

C++ STL(set/map)

更多使用：红黑树

因为宁可稍微高一点，也尽量少旋转。

2. 红黑树是什么？

BST+颜色(Color)

每个节点：

除了key，还多了color

例如：

struct TreeNode
{
    int key;

    int color;

    struct TreeNode* left;

    struct TreeNode* right;

    struct TreeNode* parent;
};

颜色只有：

RED

BLACK

例如：

        20(B)

      /       \

   10(R)     30(R)


3. 红黑树五条性质
性质一

每个节点不是红色就是黑色

只有：

RED

BLACK

性质二

根节点

必须是黑色

例如：

正确：

      20(B)

错误：

      20(R)

性质三
所有 NULL

都是黑色

例如：

      20(B)

     /

   10(R)

其实：

真正画出来：

           20(B)

          /     \

      10(R)    NULL(B)

      /   \

 NULL(B) NULL(B)

注意：

NULL

也算：

黑节点


性质四

这是最重要的一条。

红节点

不能有红孩子

也就是说：

RED

↓

RED

禁止。

例如：

错误：

      20(B)

      /

   10(R)

    /

 5(R)

因为：

红

↓

红

违反。

所以插入如果出现：

红

↓

红

必须调整

性质五

任何节点：

到所有NULL
路径黑节点数量必须一样。

例如：

正确：

          20(B)

        /       \

    10(R)      30(B)

    /   \      /   \

 NULL NULL   NULL    NULL

左边：

20(B)

↓

NULL(B)

黑：2

右边：

20(B)

↓

30(B)

↓

NULL(B)

黑：

3

这棵树其实不满足性质五。

再举一个满足的例子：

        20(B)

      /       \

   10(R)     30(R)

   /   \     /   \

 NULL NULL NULL NULL

左边：

20(B)

↓

NULL(B)

黑：

2

右边：

20(B)

↓

NULL(B)

黑：

2

一样。

所以合法。

4. 什么叫黑高（Black Height）

黑高，定义：

从某节点到所有 NULL

经过黑节点数量。

例如：

        20(B)

      /

   10(R)

从20往下：

20(B)

↓

10(R)

↓

NULL(B)

黑：

20

NULL

=

2

黑高：2

5. 为什么能保持平衡？

AVL保证：左右高度差≤1

所以非常平衡。
红黑树不是

例如可以：

左边高一点。

但是由于不能连续两个红节点

所以：

最长路径：

最多：

黑

红

黑

红

黑

红

最短可能：

黑

黑

黑

因此最长最多是最短2 倍

红黑树高度≤2log₂(n+1)

所以查找仍然O(logn)

6. 红黑树和 AVL 的区别



AVL	               红黑树
高度最平衡	       近似平衡
左右高度差≤1	   五条颜色规则
查找最快	       查找稍慢
插入旋转较多	    插入旋转较少
删除最麻烦        	删除简单一些
适合查询	       适合插入删除频繁


AVL：查找最快。

红黑树：综合性能最好。


7. 为什么颜色只有红黑？

颜色其实是一种状态

红表示这一层可以不算高度

黑表示真正增加高度。

所以红节点：只是缓冲

真正限制高度的是黑节点数量。

8. 为什么新插入节点都是红色？

先记结论：

如果插入：黑节点：

例如：20(B)

插10(B)

那么左边：

黑节点立刻增加。

性质五马上坏掉。

如果：插10(R)，黑节点没增加。

更容易调整。

所以新节点默认红色

9. 红黑树整体结构

例如：

               20(B)

          /             \

      10(R)           40(R)

      /   \           /    \

   5(B) 15(B)    30(B)     50(B)


10. 总结

红黑树

本质：BST+颜色约束

--------------------------------

五条性质：

① 每个节点非红即黑

② 根必须黑

③ NULL都是黑

④ 红节点不能有红孩子

⑤ 任意路径黑节点数相同

--------------------------------

为什么平衡？

不能连续红

最长路径≤最短路径2倍

高度：

≤2log(n)

--------------------------------

AVL：

更平衡

查询最快

--------------------------------

红黑树：

稍高一点

旋转少

工程最常用

--------------------------------

插入删除

都是为了维护：

第四条

第五条