前言

红黑树是一种特殊的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 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树绝对平衡性呢?答案就是通过染色和旋转,到这里打住,让我们先来看红黑树的定义

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