526互联

2023-03-26 红黑树

发布时间 2023-03-25 21:18:43作者: 空無一悟

红黑树

1 红黑树与2-3树

红黑树举例

红黑树举例

《算法导论》中堆红黑树的定义

首先红黑树一定是一棵二分搜索树BST

  • 1.每个节点或者是红色的，或者是黑色的
  • 2.根节点是黑色的
  • 3.每一个叶子节点(最后的空节点)是黑色的
  • 4.如果一个节点是红色的，那么它的孩子节点都是黑色的
  • 5.从任意一个节点到叶子节点，经过的黑色节点时一样的

红黑树的作者

Robert Sedgewick，也是《算法(第4版)》的作者
红黑树的作者

红黑树作者的师傅正是TAOCP(《计算机编程艺术》)的作者高德纳
名人的关系

红黑树与2-3树之间的等价关系

理解了红黑树与2-3树之间的等价关系的等价关系，红黑树并不难。2-3树堆理解B类树也有很大的帮助。

2-3树的基本性质

  • 满足二分搜索树BST(见第6章)的基本性质
  • 节点可以存在一个元素或者两个元素
  • 每个节点可以有2个孩子或者3个孩子
  • 2-3树是一种绝对平衡的树。

    绝对平衡的含义：从根节点到任意一个叶子节点所经历的节点数都是相同的

2节点和3节点图示

举例如下：
2-3树举例

2 2-3树的绝对平衡性：从根节点到任意一个叶子节点所经历的节点数都是相同的

2-3树插入新节点的原则

  • 2-3树添加节点永远不会添加到一个空(NULL)的位置
  • 一个框内有3个数字我们称之为4节点(3个数字可以劈处4个叉，所以叫4节点)

    如下图，6插入已有的树中，因为不能插入到空节点子树上，所以只能和12、18组成4节点
    4节点

  • 2-3树其实就是不断地形成3节点、4节点，然后拆分4节点成三个2节点并保持绝对平衡的过程
    • 比如上面4节点的图，不能按照如下的方式，因为这样拆就不能保持绝对平衡了

      4节点的错误拆法

    • 正确的拆法应该是把4节点的中间节点12往上提，和父亲节点进行合并
      • 如果往上提的12和父亲节点37形成了3节点，就等待再有新节点来和12、37组成4节点

        4节点的正确拆分方法

      • 一旦12、37加上新来的节点组成了4节点，就可以4节点变成3个2节点，而且还能保持二叉树的绝对平衡

        1个4节点拆分成3个2节点

2-3树插入新节点的情况分类

  • 被插入地是2节点，直接和已有节点合并成3节点即可

    被插入地是2节点

  • 被插入地是3节点而且是根节点，可以先和3节点合并成4节点，然后把一个4节点拆分成3个2节点，仍能保持2-3树的绝对平衡

    被插入地是3节点而且是根节点

  • 被插入地是3节点但是是叶子节点，其父亲节点是2节点。可以先和被插入地3节点合并成4节点，把4节点的中间那个数上移到父亲节点和其组成3节点

    被插入地是3节点但是是叶子节点且其父亲节点是2节点

  • 被插入地是3节点但是是叶子节点，其父亲节点是3节点。可以先和被插入地3节点合并成4节点，把4节点的中间那个数上移到父亲节点和其组成4节点,这个4节点可以拆分成3个2节点

    被插入地是3节点但是是叶子节点且其父亲节点是3节点

通过上面的4操作，所有的新节点插入后都可以保持2-3树的绝对平衡。

3 2-3树和红黑树的等效关系

2节点和3节点的等效关系

2-3树和红黑树的节点对应关系

上面的对应关系的举例如下，自己画一下
2-3树变成红黑树的例子

红黑树的基础结构代码

架构还是用地支持键值对的BST，给每个节点加入了color属性

4 红黑树的基本性质和复杂度分析

红黑树的基本性质

红黑树是保持黑平衡的二叉树，严格意义上不是平衡二叉树。黑红合一形成的2-3才是绝对平衡的二叉树

  • 1.每个节点要么是红色的，要么是黑色的
  • 2.根节点是黑色的
  • 自己补充地：红黑树添加的节点初始一定是红色的
  • 3.每一个叶子节点(最后的空节点null)是黑色的
  • 4.如果一个节点是红色的，那么它的孩子节点都是黑色的
  • 自己补充地：黑色节点的右孩子一定是黑色的

    我们定义地2-3节点拆分时，红色节点一定是左倾地

  • 5.从任意一个节点到叶子节点，经过的黑子节点数是相等的

    因为是从绝对平衡的2-3树转化来地

2-3树变成红黑树的例子

红黑树的复杂度分析

红黑树的最大高度是2logn，所以增删改查的时间复杂度是O(logn)，并且绝对不会蜕化成链表。

5 红黑树添加元素：保持根节点为黑色和左旋转

时时记住2节2-3树添加节点步骤和情形

参考2-3树中添加一个元素，只是要针对红黑树做对应的颜色设置

  • 添加进一个2节点，形成一个3节点
  • 添加进一个3节点，暂时形成一个4节点，4节点可以拆分成3个2节点

对应2-3树永远添加到非空节点组成3节点或4节点：红黑树添加节点，永远添加红色节点。好好回下2-3树和红黑树的节点等效关系

2-3树中的4节点拆分时向上融合的元素在红黑树中一定是红色的，一直上浮到根节点才能变成黑色

2-3树中的4节点拆分时向上融合的元素在红黑树中一定是红色的

新加入的节点的情况

新插入的节点初始一定是作为红色节点

  • 插入的位置是左节点，不用做调整，这样就行，符合红黑树的定义

    红黑树插入的位置是左节点

  • 插入的位置是右节点，需要进行左旋转，这样是为了把新插入节点的父节点变为它的左节点，然后颜色取反，就又满足红黑树的特点了。

    插入的位置是右节点则需要进行左旋转

左旋转的详细解析

  • 仍以42作为新节点插入到37的右侧为例，37称为node，42称为x。插入后的树如下：
    新节点插入到右子树中
  • x的左子树T2卸下来挂到node的右子树上：node.right = x.left
    x的左子树T2卸下来挂到node的右子树上
  • x的左子树连接到node上：x.left=node
    x的左子树连接到node上
  • 根据红黑树的性质更新节点的颜色
    • x.color = node.color：x替代了原来node节点的位置变成了新的根节点，所以要继承node的颜色
    • node.color = RED：node-x相当于2-3树中的3节点，node作为左侧节点，按照红黑树的定义应该是红色

      原来node的颜色红或者黑都可能，如果原来node就是红色，那么node和x作为连接的父子节点就都是红色，产生了两个连续的红色节点，这不符合红黑树的性质第4条。其实左旋转只是一个中间步骤，当遇到两个连续的红色节点时还会有进一步的操作(递归传给父节点让父节点处理)，见后面的课程。
      左旋转后更新颜色

左旋转的代码实现

/**
     * 新加入节点后进行左旋转
     * node.right = x.left;
     * x.left=node;
     * x.color = node.color;
     * node.color = RED
     * 图示如下：
     * //   node                     x
     * //  /   \     左旋转         /  \
     * // T1   x   --------->   node   T3
     * //     / \              /   \
     * //    T2 T3            T1   T2
     *
     * @param node 新加入节点的父节点
     * @return 左旋转后原本以node作为根节点的子树的新的根节点
     */
private Node rotateLeft(Node node) {
    // 暂存节点
    Node x = node.right;
    // 左旋转
    node.right = x.left;
    x.left = node;
    // 更新颜色
    x.color = node.color;
    node.color = RED;
    return x;
}

6 颜色翻转和右旋转

上一节的两种情况实际是新的节点x插入到一个已有的2节点中，本节我们将看向红黑树中的3节点(要被新节点插入的节点是红色，且其父节点是黑色，红色节点是其父亲节点的左节点)，如下图就是一个红黑树中等效于2-3树中3节点的两个相连节点
红黑树中新节点插入一个3节点

红黑树中新插入的节点和已有节点组成了4节点，而且是平衡的一个小树，则需要进行颜色翻转

红黑树中新插入的节点和已有节点组成了4节点

/**
 * 把以node为根的节点和左右孩子节点的颜色进行翻转(红变黑，黑变红)
 * 红黑树中新插入的节点和已有节点组成了4节点，而且是平衡的一个小树，则需要进行颜色翻转.
 *
 * @param node 要翻转子树的根节点
 */
private void flipColors(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}

红黑树中新插入的节点和已有节点组成了4节点，而且是不平衡的一个小树，则需要先进行右旋转，然后颜色翻转

插入新节点后生成的等效4节点树不平衡

右旋转的详细图示如下：
右旋转的详细过程

/**
 * 新加入节点后进行右旋转
 * 下面的伪代码
 * node.left = T1
 * x.right = node
 * x.color = node.color
 * node.color = RED
 * flipColors()
 * 下面是图示：
 * //     node                   x
 * //    /   \     右旋转       /  \
 * //   x    T2   ------->   y   node
 * //  / \                       /  \
 * // y  T1                     T1  T2
 *
 * @param node 新加入节点的父节点
 * @return 右旋转后原本以node作为根节点的子树的新的根节点
 */
private Node rotateRight(Node node) {
    // 暂存节点
    Node x = node.left;
    Node T1 = x.right;
    // 右旋转
    node.left = T1;
    x.right = node;
    // 颜色更新
    x.color = node.color;
    node.color = RED;
    return x;
}

7 红黑树添加新元素的完整代码

综合前两节，新节点加入红黑树的情况有如下几种

  • 一、新加入的节点被添加到2节点下作为孩子节点
    • 1.作为左孩子，和父节点组成一个2-3树中的3节点，且符合红黑树定义，所以不用任何调整
    • 2.作为右孩子，和父节点组成一个2-3树中的3节点，不符合红黑树定义，实际恰好相反，需要进行左旋转
  • 二、新加入的节点被添加到3节点下作为孩子节点

    红黑树中的3节点：要被新节点插入的节点是红色，且其父节点是黑色，红色节点是其父亲节点的左节点

    • 1.作为3节点的右孩子(被插入节点的父节点的右孩子)，直接就是平衡地，不需要旋转，只需要颜色翻转即可
    • 2.作为3节点的左孩子(被插入节点的左孩子)，需要先进行右旋转，然后颜色翻转
    • 3.作为3节点的中孩子(被插入节点的右孩子)，需要先进行左旋转，变成上一种情况，然后按照上一种情况先后进行右旋转和颜色翻转即可

      这种情况前面没有讲，其实是前面几种情况的综合，用下面的图示自己体会下吧。
      先左旋转再右旋转然后颜色翻转

    被添加到3节点的3这种情况总结如下图：
    红黑树插入新节点形成4节点的3种情况都可以用一个图表示

/**
 * 新加入节点后进行左旋转
 * node.right = T2;
 * x.left=node;
 * x.color = node.color;
 * node.color = RED
 * 图示如下：
 * //   node                     x
 * //  /   \     左旋转         /  \
 * // T1   x   --------->   node   T3
 * //     / \              /   \
 * //    T2 T3            T1   T2
 *
 * @param node 新加入节点的父节点
 * @return 左旋转后原本以node作为根节点的子树的新的根节点
 */
private Node rotateLeft(Node node) {
    // 暂存节点
    Node x = node.right;
    Node T2 = x.left;
    // 左旋转
    node.right = T2;
    x.left = node;
    // 更新颜色
    x.color = node.color;
    node.color = RED;
    return x;
}

/**
 * 新加入节点后进行右旋转
 * 下面的伪代码
 * node.left = T1
 * x.right = node
 * x.color = node.color
 * node.color = RED
 * flipColors()
 * 下面是图示：
 * //     node                   x
 * //    /   \     右旋转       /  \
 * //   x    T2   ------->   y   node
 * //  / \                       /  \
 * // y  T1                     T1  T2
 *
 * @param node 新加入节点的父节点
 * @return 右旋转后原本以node作为根节点的子树的新的根节点
 */
private Node rotateRight(Node node) {
    // 暂存节点
    Node x = node.left;
    Node T1 = x.right;
    // 右旋转
    node.left = T1;
    x.right = node;
    // 颜色更新
    x.color = node.color;
    node.color = RED;
    return x;
}

/**
 * 把以node为根的节点和左右孩子节点的颜色进行翻转(红变黑，黑变红)
 * 红黑树中新插入的节点和已有节点组成了4节点，而且是平衡的一个小树，则需要进行颜色翻转.
 *
 * @param node 要翻转子树的根节点
 */
private void flipColors(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}
/**
 * 红黑树的颜色和节点平衡
 *
 * @param node 要维护的节点
 * @return 维护后新的根节点
 */
private Node rbManage(Node node) {
    // 左孩子不是红色，右孩子是红色，就左旋转
    if (!isRed(node.left) && isRed(node.right)) {
        node = rotateLeft(node);
    }
    // 左孩子是红色，左孩子的左孩子还是红色，就左旋转
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rotateRight(node);
    }
    // 左孩子和右孩子都是红色
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }
    return node;
}
// 在添加节点时调用下即可
private Node add(Node node, K key, V val) {
    ......
    return rbManage(node);
}

8 红黑树的性能测试

代码

总结

  • 对于完全随机的数据，普通的二分搜索树很好用。但是对于较有序的数据容易蜕化成链表，性能就会大大降低。
  • 对于查询(contains)较多的情况，平衡的BST即AVL树很好用。但是旋转次数比较多，会影响插入节点(add)的性能。
  • 对于插入(add)较多的情况，保持绝对黑平衡的红黑树很好用。但是红黑树牺牲了平衡性(2logn的高度)，所以会影响查询(contains)的性能。

红黑树的统计性能更优：即从数学角度上看，综合增删改查所有的操作，红黑树是平均性能最好的。

9 红黑树的更多相关问题

红黑树删除节点

极其复杂，《算法4》282页，基本不会遇到~

另一种统计性能更优的树：Splay Tree(伸展树)，比红黑树的实现简单点

局部性原理：刚被访问的内容下次高概率被再次访问

JDK中的TreeMap和TreeSet就是基于红黑树实现的