文章目录

红黑树

知识储备

1. 红黑树的定义

2. 红黑树结点API

3. 平衡化

3.1 左旋

3.2 右旋

4. 颜色反转

5. 插入

5.1 向单个2-结点中插入新键

5.2 向底部的2-结点插入新键

5.3 向一棵双键树(即一个3-结点)中插入新键

5.4 向树底部的3-结点插入新键

6. 根结点的颜色总是黑色

7. 红黑树的实现

7.1 红黑树的API设计

7.2 代码

7.3 测试代码

红黑树

知识储备

在学习红黑树之前我们应先了解2-3查找树的一些特性，可以看到2-3树能保证在插入元素之后，树依然保持平衡状态，它的最坏情况下所有子结点都是2-结点，树的高度为lgN,相比于我们普通的二叉查找树，最坏情况下树的高度为N，确实保证了最坏情况下的时间复杂度，但是2-3树实现起来过于复杂，所以我们介绍一种2-3树思想的简单实现：红黑树。

红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型：

红链接： 将两个2-结点连接起来构成一个3-结点

黑链接： 则是2-3树中的普通链接

确切的说，我们将3-结点表示为由由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2-结点。这种表示法的一个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。

1. 红黑树的定义

红黑树是含有红黑链接并满足下列条件的二叉查找树：

红链接均为左链接；

没有任何一个结点同时和两条红链接相连；

该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同；

下面是红黑树与2-3树的对应关系：

2. 红黑树结点API

因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们可以在之前的Node结点中添加一个布尔类型的变量color来表示链接的颜色。如果指向它的链接是红色的，那么该变量的值为true，如果链接是黑色 的，那么该变量的值为false。

API设计：

代码：

private class Node<Key,Value>{
    //存储键  
    public   Key key;
    //存储值
    private Value value;
    //记录左子结点 public Node left;
    //记录右子结点
    public Node right;
    //由其父结点指向它的链接的颜色 
    public boolean color;
    public Node(Key key, Value value, Node left,Node right,boolean color) {
        this.key = key; 
        this.value = value; 
        this.left = left;
        this.right = right;
        this.color = color;
    }
}

3. 平衡化

在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。

3.1 左旋

当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。

**前提：**当前结点为h，它的右子结点为x；

左旋过程：

让x的左子结点变为h的右子结点：h.right=x.left;

让h成为x的左子结点：x.left=h;

让h的color属性变为x的color属性值：x.color=h.color;

让h的color属性变为RED：h.color=true;

3.2 右旋

当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋

**前提：**当前结点为h，它的左子结点为x；

右旋过程：

让x的右子结点成为h的左子结点：h.left = x.right;

让h成为x的右子结点：x.right=h;

让x的color变为h的color属性值：x.color = h.color;

让h的color为RED；

右旋后会出现右结点出现红链接的情况，右旋不会解决该情况，该情况会在颜色反转阶段解决

4. 颜色反转

当一个结点的左子结点和右子结点的color都为RED时，也就是出现了临时的4-结点，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可。

5. 插入

5.1 向单个2-结点中插入新键

一棵只含有一个键的红黑树只含有一个2-结点。插入另一个键后，我们马上就需要将他们旋转。

如果新键小于当前结点的键，我们只需要新增一个红色结点即可，新的红黑树和单个3-结点完全等价。

如果新键大于当前结点的键，那么新增的红色结点将会产生一条红色的右链接，此时我们需要通过左旋，把红色右链接变成左链接，插入操作才算完成。形成的新的红黑树依然和3-结点等价，其中含有两个键，一条红色链接。