红黑树以及JAVA实现（一）

前言

红黑树是一种特殊的B树是B树种2-3-4树的一种特殊实现，红黑树保证了每个节点只会有两个子节点，通过对每个节点进行染色，然后通过不同颜色的节点组合来分别代表2-3-4的2节点、3节点、4节点树的情况。在学习红黑树之前，我们需要先去了解2-3-4树。

一、 B树

那么如果想要对红黑树有一个较为深刻的理解，我认为首先去理解其根源，也就是B树是必不可少的

1.1 概念

树形结构首先可以分为等叉树和不等叉树，等叉树是每个节点的键值个数都相同、子节点个数也都相同，不等叉树是每个节点的键值个数不一定相同、子节点个数也不一定相同。

最简单的等叉树是二叉树，直接二叉树的作用并不大，我们一般会要求二叉树所有的节点按照一定的顺序排列，这样我们进行插入、删除、查找时效率就会非常高，我们把这样的树叫做二叉搜索树或者二叉查找树。它的具体定义是这样的，二叉搜索树，要么是个空树，要么符合以下几个条件:

1. 左子树如果存在的话，左子树所有节点的键值都要小于根节点的键值
2. 右子树如果存在的话，右子树所有节点的键值都要大于根节点的键值
3. 它的所有子树也都要符合前面的两个条件(前面的小于同时换成大于也成立)。

经过这样定义之后，二叉树就变成了二叉搜索树，它的插入、删除、查找效率一般情况下都是O(logn)。

相较于等叉树，我们可以对不等叉树的节点键数值数和插入、删除逻辑添加一些特殊的要求使其能达到绝对平衡的效果，我们把这种树叫做 B树，全称Balance Tree，是一种自平衡树，它和等叉树最大的不同首先表现在存储结构上，等叉树上每个几点的键值数和分叉数都是相同的，而B树不是。如果某个B树上所有节点的分叉数最大值是m，则把这个B数叫做m阶B数。下面我们来看一下B树的具体定义：

1. 所有节点最多有m个子节点
2. 非根非叶子结点至少有m/2(向上取整)个子节点
3. 根节点至少有两个子节点(除非总结点数不足3个)
4. 所有叶子节点都在同一层
5. 任意节点如果有k个键值，则有k+1个子节点指针，键值要按照从小到大排列，子节点数上所有的键值都要在对应的两个键值之间

B树看似5条定义很复杂，但实际上自己分析一下理解后会发现还是蛮简单的。第一条，对子节点数进行限制，这也是m阶B树m的由来，第二条，是用来限制树的紧凑性，避免树又高又长。第三条没什么好说的。第四条规定了B树是一个绝对平衡树不会退化为线性结构，所以B树的效率永远是O(logn)。第5条保证了B树的元素的有序，以便高效率的查找。

1.2 2-3-4树

2-3-4树其实就是4阶的B树，目前网上讲的红黑树大多数就是2-3树或者是2-3-4树转化而成的。这里仅对2-3-4树进行讲解

1.3 2-3-4树的插入

节点分类

• 2节点：一个节点中有1个键值，2条链接
• 3节点：一个节点中有2个键值，3条链接
• 4节点：一个节点中有3个键值，4条链接

首先是2节点的插入，由于2-3-4树是4阶B树，最多可以有4条连接，一个节点最多有3个键值，所以这里直接添加即可

然后是3节点的插入，2节点插入之后，转化为4节点，仍保持一个节点的状态

4节点插入,由于2-3-4树是4阶B树，所以当对4节点插入的时候，就需要对4节点进行分裂，首先将中间的节点上升，然后,根据B树定义，将新增的节点和叶子的其中一个节点结合，形成一个3节点，比如，下图中要插入4,首先123分裂，之后4根据大小顺序，放在3的右边，和3形成一个3节点。

之后如果继续插入，第二层节点如果再形成4节点的情况下插入，那么分裂之后出来的节点，应该和父节点再构成节点

如果向上和父节点构成节点，但是父节点已经是4节点了，这个时候父节点就需要继续分裂，在往上的情况一次类推，进行递归分裂

1.4 2-3-4树的删除

相对于插入，B树的删除就相对复杂，需要分情况讨论

1.4.1 当删除节点是叶子节点

当删除节点是叶子节点的时候，又分为以下情况

1.4.1.1 当删除节点为非2节点

直接删除即可，因为从一个非2节点中删除一个键值以后，并不违反B树的定义

1.4.1.2 当删除节点为2节点

这种情况又要分多种情况

1.4.1.2.1 兄弟节点是非2节点

当兄弟节点是非2节点，我们可以直接从兄弟节点借一个元素过来，让当前删除节点形成非2节点，这样情况就转换为了2.3.3.1的情况，直接删除要删除的节点既可

1.4.1.2.2 兄弟节点是2节点

如果兄弟节点是2节点，那么此时就需要从父节点借元素了，待删除结点和父节点、兄弟节点构成一个4节点，然后将待删除节点删。

如果父节点是非2节点，那么借走就接走了，如果是2节点，借走了当前位置就空了，所以需要再从这个节点的兄弟或父节点借一个元素，如果直到根节点也没有找到一个非2节点，那么这个B树的高度就会减一。

1.4.2 如果删除节点是非叶子节点

1. 如果被删除节点是非叶子节点，那么我们就需要找到他的后继元素，然后将后继元素的值覆盖被删除元素，再将后继元素删除即可
2. 那么如何寻找后继节点呢？一般来说就是key大小最接近被删除元素的叶子节点中的元素，这个元素可以大于key也可以小于key，这个是我们可以自己定义，这里我们选小于被删除元素的那个。也就是左子树节点中最大的元素。

二、 红黑树

通过上一节，我们了解了红黑树的前身或者说是其本源B树之后我们再来看红黑树，相信你能够更容易理解红黑树，看出其操作的底层逻辑

在讲解之前我先讲红黑树的类结构放出来

public class RedBlackBSTextends Comparable, Value> {

    //很明显，这个常量用来代指红或黑
    private static final boolean Red = true;

    private static final boolean Black = false;

    //根节点
    private Node root;


    //节点类结构
    private class Node {
        Key key;
        Value value;
        Node left, right, parent;
        int N;
        boolean color;

        public Node(Key key, Value value, Node parent, int n, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.color = color;
            this.parent = parent;
        }

    }

    public RedBlackBST() {

    }

    //用来判断一个节点是还是黑色
    private boolean isRed(Node x) {
        if (x == null) return false;
        return x.color == Red;
    }

}

2.1 红黑树的定义

红黑树，本质上其实就是将一个B树（我们这里讨论2-3-4树）转化为一个二叉树。那么如何去转化的同时又能继承B树绝对平衡性呢？答案就是通过染色和旋转，到这里打住，让我们先来看红黑树的定义

1. 所有的节点不是黑色就是红色
2. 根节点是黑色的
3. 所有叶子节点是黑色的
4. 从每个叶子到跟的所有路径上不能有两个连续的红色节点
5. 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点

2.2 2-3-4树节点到红黑树的转换

在解释这几个定义之前我们需要先来开2-3-4树中节点转化到红黑树中的形式是怎样的

首先我们要明白的是，在红黑树中，只有黑色节点才计入高度，红色节点代表着其和父节点的链接是红色的。

非2节点由黑色节点+红色节点组合的形式表示，红黑树对应到2-3-4树的节点组合中只会存在一个黑色节点。

2.2.1 2节点转换

2.2.2 3节点转换

3节点转换成红黑树就是一个黑色节点带着红色子节点的树，这个树可以是左倾的也可以是右倾的，根据节点的key来决定，在以2-3树为基础实现的红黑树中，我们一般只允许左倾或则右倾树存在，如果出现不允许的倾斜树情况，一般会通过旋转变色来调整。

2.2.3 4节点转换

2.2.4 例子

2.3 红黑树定义解释

先在我们再来来挨个看这5条定义

1. 第一条这个没什么好说的，红黑树红黑树，那肯定节点不是红色就是黑色

2. 由于根节点必然是没有父节点的，而在上面我们所列举的转换形式中并没有红色节点为父节点的结构，所以根节点必然是黑色的

3. 在红黑树中叶子节点会默认拥有两个为null的子节点，颜色自然是黑色
   

4. 不允许又连续两个红色节点是为了限制红黑树的阶数为4，不允许出现2、3、4节点之外的节点类型

5. 对应2-3-4树的第五条，保证了树的绝对平衡，对应到红黑树中只有黑色节点代表高度，所以只需要保证黑色节点的数目一致即可。

2.3.1 红黑树的旋转与变色

我们在对红黑树进行添加的时候，一开始按照二叉树的方式添加，每个新节点的初始元素为红色（root节点为黑色），当我们继续进行添加，发现当前的红黑树结构不符合定义时，我们就需要通过旋转和对节点变色来重新平衡红黑树。

2.3.2 红黑树的旋转

先说旋转，红黑树的旋转分为左旋和右旋，我们先通过左旋来进行详细讲解。左旋就是一个节点绕着他的右子节点逆时针旋转，变成右子节点的左子节点，我们以下图为例

A进行左旋，变成B的左子节点，于此同时，B原先的左子树变成A的右子树，A的父节点变为B的父节点。

A的左子树依旧是A的左子树，B的右子树也依旧是B的右子树，不做变化。

这样，我们就完成了一次左旋，右旋则是绕则操作节点自身的子节点顺时针旋转，变成左子节点的右子树，左子节点的右子树迁移到操作节点的左子树，操作节点的父节点变成左子节点的父节点。原理一模一样。

2.3.3 红黑树的变色

当然，我们在旋转以后，如果不变色，结果肯定是不正确的，只有进行变色之后的红黑树才是正确的，由于变色有很多种情况，所以我们这里只举一个简单的例子，后面在讲解添加和删除的时候再进行细致列举。

首先我们这里有一个两个节点的二叉树，现在他是正确的，这个时候我们再插入一个新的节点3，那么根据二叉树的性质，插入后这个树会变成这个样子

当然，这个结果明显是错误的，其结构明显不符合我们我们在2.2.2中展示的任何一种形式,所以我们要通过旋转和变色变换为2.2.2中的哪几种形式。

首先这个组合在2-3-4树种是一个4节点，但是他的形态并不符合红黑树的节点，所以我们需要将它转换为已个合法的形态，先进行旋转，1节点左旋，这个时候结构对了，但是颜色不对，需要将2变色为黑色，而1变色为红色，这样我们的这个红黑树就完全符合定义了。

这就是一个最简单的旋转变色的红黑树自动平衡过程。

下面是左旋和右旋的java代码实现，并没有添加变色，因为变色的逻辑并不是固定的故而我们将其解耦到其他方法中

    //左旋
    Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        if(h.right!=null){
            h.right.parent = h;
        }
        x.parent = h.parent;
        h.parent = x;
        x.left = h;
        if(x.left!=null){
            x.left.parent = x;
        }
        if(x.parent!=null){
            int cmp = x.parent.key.compareTo(x.key);
            if(cmp>0) x.parent.left = x;
            else x.parent.right = x;
        }
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        show();
        return x;
    }

    //右旋
    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        if(h.left!=null){
            h.left.parent = h;
        }
        x.parent = h.parent;
        h.parent = x;
        x.right = h;
        if(x.right!=null){
            x.right.parent = x;
        }
        if(x.parent!=null){
            int cmp = x.parent.key.compareTo(x.key);
            if(cmp>0) x.parent.left = x;
            else x.parent.right = x;
        }
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        show();
        return x;
    }

2.4 红黑树的添加

红黑树的添加分为以下几种情况

2.4.1 在黑色节点下面插入

这种情况无论是插入在左还是右，都可以直接插入，红黑树的正确性不会受到影响

2.4.2 在红色节点下插入且被插入节点无兄弟节点

2.4.2.1 当被插入的节点是右子节点

在右侧插入

操作步骤：

1. 节点1左旋
   

2. 变色，1变色为红色， 2变色为黑色
   

在左侧插入

这种情况会比上面那种多一个步骤

1. 节点3右旋，无需变色，这个操作主要是为了将情况转换为上面在右侧插入的情况，然后下面按照在右侧的情况处理即可
   
   )

2. 节点1左旋
   

3. 变色，1变色为红色，2变色为黑色
   

2.4.2.2 当被插入节点是左子节点

其实这种情况和上面的处理逻辑是一样的，只不过左右是反过来的，就不再赘述了，大家自己举一反三即可。

2.4.3 在红色节点下插入且被插入节点有兄弟节点

这种时候，我们需要先进行变色，再插入，如下图（这里，我们默认，1节点是有父节点的，1节点非根节点）

2和3节点变黑色，1节点变红色，这个变化其实对应着2-3-4树的4节点插入，其实就是讲一个4节点拆分开来，中间的节点向上和父节点组合，左右两边的节点分裂为两个单独的节点，然后再正常插入一个新的节点。红黑树也是这么个道理。

2、3节点变黑，形成单独的节点，而1节点则变红和父节点结合，那么这里我们要注意的是，1节点和父节点结合的时候，也相当于一次新的插入，相当于在1的父节点新插入一个红色，所以这个过程是递归的，一直向上传递，直到红黑树的结构符合定义为止。

到这里，红黑树的插入操作就结束了，以上的操作，只是单纯的一步操作，这些操作只是在插入之后对被插入节点红黑树的一个平衡，我们在进行旋转变色之后，很有可能上层的节点就又不符合定义了，这个时候我们就需要进行递归的旋转变色， 直到最后整个红黑树平衡。

下面扔代码

代码

    private void put(Key key, Value val) {
        root = put(root, null, key, val); //进行插入，返回根节点作为查询遍历的起始节点保存
        root.color = Black; //根节点的颜色必然是黑色
    }

    private Node put(Node h, Node p, Key key, Value val) {
        if (h == null) {
            return new Node(key, val, p, 1, Red);
        }
        //当插入的时候，发现路径上有-4节点
        if (isRed(h.left) && isRed(h.right)) flipColors(h);
        //递归搜索树，直到找到相同的key，修改，或者搜索到底层，进行插入。
        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, h, key, val);
        else if (cmp > 0) h.right = put(h.right, h, key, val);
        else h.value = val;

        //判断红黑，进行旋转，调整树的平衡
        if (isRed(h.right) && isRed(h.right.right)) {
            h.right.color = h.color;
            h.color = Red;
            h = rotateLeft(h);
        }
        if (isRed(h.right) && isRed(h.right.left)) {
            //RL问题，先右旋,将问题转换为RR
            h.right = rotateRight(h.right);
            //变色
            h.right.color = h.color;
            h.color = Red;
            //再左旋
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h.left.color = h.color;
            h.color = Red;
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.left.right)) {
            //LR问题，先左旋，将问题转换为LL问题
            h.left = rotateLeft(h.left);
            //变色
            h.left.color = h.color;
            h.color = Red;
            //再右旋
            h = rotateRight(h);
        }

        h.N = size(h.left) + size(h.right) + 1;

        return h;
    }

结语

本章中我们学习了红黑树的起源，B树，然后学习了红黑树的插入。由于红黑树的删除较为复杂，我们放到下一章在进行讲解