目录
前言
一、 B树
1.1 概念
1.2 2-3-4树
1.3 2-3-4树的插入
节点分类
1.4 2-3-4树的删除
1.4.1 当删除节点是叶子节点
1.4.1.1 当删除节点为非2节点
1.4.1.2 当删除节点为2节点
1.4.1.2.1 兄弟节点是非2节点
1.4.1.2.2 兄弟节点是2节点
1.4.2 如果删除节点是非叶子节点
二、红黑树
2.1 红黑树的定义
2.2 2-3-4树节点到红黑树的转换
2.2.1 2节点转换
2.2.2 3节点转换
2.2.3 4节点转换
2.2.4 例子
2.3 红黑树定义解释
2.3.1 红黑树的旋转与变色
2.3.2 红黑树的旋转
2.3.3 红黑树的变色
2.4 红黑树的添加
2.4.1 在黑色节点下面插入
2.4.2 在红色节点下插入且被插入节点无兄弟节点
2.4.2.1 当被插入的节点是右子节点
2.4.2.2 当被插入节点是左子节点
2.4.3 在红色节点下插入且被插入节点有兄弟节点
代码
结语

前言

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

一、 B树

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

1.1 概念

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

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

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

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

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 如果删除节点是非叶子节点

二、红黑树

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

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

public class RedBlackBST<Key extends Comparable<Key>, 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树绝对平衡性呢？答案就是通过染色和旋转，到这里打住，让我们先来看红黑树的定义

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条定义

不允许又连续两个红色节点是为了限制红黑树的阶数为4，不允许出现2、3、4节点之外的节点类型
对应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变色为红色， 2变色为黑色

在左侧插入

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

节点1左旋

变色，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树，然后学习了红黑树的插入。由于红黑树的删除较为复杂，我们放到下一章在进行讲解

红黑树以及JAVA实现（一）

前言