TreeMap红黑树

  • 前言
  • 二叉查找树BST
  • BST存在的问题
  • 2-3-4树
  • 红黑树

前言

除了要学会着色、旋转规则，还要了解为什么变色，为什么旋转。

五大性质的缘由

jdk的TreeMap在红黑树上做了一些优化，原版红黑树删除操作它是找的前驱节点替代原删除节点，而TreeMap源码里是用的后继节点替代原删除节点，这两种方案实际效果一样，只不过树的结构不一样，但是对应的红黑树都是平衡的。

二叉查找树(BST)

定义

二叉查找树，就是一颗二叉树，他的左节点比父节点小，右节点比父节点大，他的高度决定查找效率。

操作

查找(红黑树通用)：查找每个节点从根开始

  • 查找值比当前大，搜右子树
  • 查找值等于当前值，停止查找，返回
  • 查找值比当前值小，则搜右子树

插入：要插入节点，必须先找到插入节点位置，按照搜索的流程，找到左子树或右子树为空的位置插入。

遍历(红黑树通用)：前中后序遍历。

查找最小值(红黑树通用)：沿着根节点的左子树一路查找，直到最后一个不为空的节点

查找最大值(红黑树通用)：沿着根节点的右子树一路查找，直到最后一个不为空的节点

查找前驱节点(红黑树通用)：小于当前节点的最大值

查找后继节点(红黑树通用)：大于当前节点的最小值

删除 : 本质上是找前驱或后继节点来替代

  • 叶子节点直接删除(没有前驱或或后继)
  • 只有一个子节点的用子节点替代(本质上就是找的前驱节点或者后继节点，左节点就是前驱节点，右节点就是后继节点)
  • 有两个子节点的，需要找到替代节点(替代节点也是前驱或者后继)

删除操作和红黑树一样，只不过红黑树多了着色和旋转过程。

BST存在的问题

BST存在的问题是，树在插入的时候会导倾斜，不同的插入顺序会导致高度不一样，而树的高度直接影响了树的查找效率。

基于这个问题平衡二叉树产生了，平衡树的插入和删除时，会通过旋转操作将高度保持在LogN。

其中两款有代表性的平衡树分别为

  • AVL树（高度平衡树，具备二叉搜索树的全部特性，而且左右子树高度差不超过1）
  • 红黑树

面试题：有了AVL树为什么还要红黑树？

AVL树由于实现比较复杂，而且插入和删除性能差。AVL很多性能耗在旋转操作上

在实际环境下的应用不如红黑树。

红黑树的实际应用范围广，如java中的HashMap和TreeSet，java8中HashMap的实现因为用RBTree代替链表(链表长度大于8时)，性能有提升。

2-3-4树

定义

2-3-4树是四阶B树(Balance Tree)，他属于一种多路查找树，他的结构有以下限制：

  • 所有叶子节点都拥有相同的深度。
  • 节点只能是2-节点、3-节点、4-节点之一。
    • 2-节点：包含1个元素的节点，有2个子节点；
    • 3-节点：包含2个元素的节点，有3个子节点；
    • 4-节点：包含3个元素的节点，有4个子节点；
    • 所有节点必须至少包含1个元素
  • 元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子节点，小于右子结点；而且结点有多个元素时，每个元素必须大于它左边的和它的右子树中元素。

结点插入

2-3-4树中结点添加需要遵循以下规则：

  • 插入都是向最下面一层插入
  • 升元：将插入结点由2-节点升级成3-节点，或由3-结点升级成4-结点
  • 向4-结点插入元素后，需要将中间元素提到父节点升元，原节点变成两个2-节点，再把元素插入2-结点中，如果父节点也是4-结点，则递归向上层升元，直到根节点后将树高加1。

而将这些规则对应到红黑树里，就是：

  • 新插入的结点颜色为红色，这样才可能不会对红黑树的高度产生影响。
  • 2-结点对应红黑树中的单个黑色结点，插入时直接成功(对应2-结点升元)
  • 3-结点对应红黑树中的黑+红子树，插入后将其修复成红+黑+红子树
  • 4-结点对应红黑树中的红+黑+红子树，插入后将其修复成红色祖父+黑色父叔+红色孩子子树，然后再把祖父结点当成新插入的红色结点递归向上层修复，直至修复成功或遇到root结点。

公式：红黑树+新增一个节点(红色) = 对等的2-3-4树+新增一个节点

删除结点

2-3-4树的删除可以全部转换为叶子节点的删除

删除原则是先看能不能和下面的叶子节点合并，能合并的直接合并完后删除，不能合并的就要找个元素替换上去，最终都是要保持平衡。

合并—>删除

合并—>替换—>删除

合并—>无法替换—>再合并—>删除

红色结点一定全部都在多元素节点中

红黑树的删除要比插入复杂，还是类比2-3-4树：

  • 查找最近的叶子结点的元素替代被删除元素，删除替代元素后，从替代元素所处叶子结点开始处理
  • 降元：4-结点变3-结点，3-结点变2-结点。
  • 2-结点中只有一个元素，所以借兄弟结点中的元素来补充删除后的造成的空结点。
  • 当兄弟结点中也没有多个元素可以补充时，尝试将父节点降元，失败时向上递归，直到子树降元成功或root结点树高减一

将这些规则对应到红黑树中即：

  • 查找离当前结点最近的叶子结点作为替代节点，(左子树的最右结点或右子树的最左结点都能保证替换后二叉树的节点排序性质，叶子节点的替代结点是自身) 替换掉被删除结点，从替代的叶子结点向上递归修复。
  • 替代结点颜色为红色(对应2-3-4树中 4-节点或3-结点) 时删除子结点直接成功
  • 替代节点为黑色(对应2-3-4树中 2-节点)时， 意味着替代结点所在的子树会降一层，需要依次检验以下三项，以恢复子树高度：
    • 兄弟结点的子结点中有红色节点(兄弟结点对应3-结点或4-结点) 能够“借用”，旋转过来后修正颜色。
    • 父结点是红色结点（父结点对应3-结点或4-结点，可以降元）时，将父结点变为黑色，自身和兄弟结点变红色后删除。
    • 父结点和兄弟结点都是黑色时，将子树降一层后把 父结点当做替代结点 递归向上处理。

红黑树对应一颗2-3-4数，一颗2-3-4树对应多颗红黑树

红黑树和2-3-4树的结点添加和删除都有一共基本规则：避免子树高度变化，因为无论是2-3-4树还是红黑树，一旦子树高度有变动，势必会影响其他子树进行调整。所以我们在插入和删除节点时尽量通过子树内部调整来达到平衡。

2-3-4树实现平衡是通过结点的旋转和结点元素变化，红黑树是通过结点旋转和变色。

2节点全是黑色，3节点有左倾右倾两种情况，4节点上黑下红

2-3-4树的裂变状态: 红黑树新增都是以红色节点进来的，11裂变上去变成红色，下面两个变成黑色

整体对比2-3-4树和红黑树

红黑树

定义

红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外还有以下五大性质：

  • 结点是红色或黑色
  • 根是黑色
  • 所有叶子都是黑色(叶子是NIL节点，这类节点不可忽视，否则代码会看不懂)
  • 每个红色节点必须有两个黑色子节点（从每个叶子到根的所有路径上不能有两个连续的红色结点）
  • 从任意一节点到其每个叶子的所有简单路径都包含相同数目的黑色结点（黑色平衡）

常见操作

变色、左旋、右旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
private RBNode root;

/**
 * 围绕p左旋
 * @param p
 *              pf                  pf
 *            /                   /
 *           p                   pr(r)
 *          / \                 /  \
 *         pl  pr(r)    ->     p   rr
 *             / \            / \
 *            rl rr          pl  rl
 */
private void leftRotate(RBNode p) {
    if (p != null) {
        RBNode r = p.right;
        p.right = r.left;
        if (r.left != null) {
            r.left.parent = p;
        }
        r.parent = p.parent;
        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            p.parent.left = r;
        } else {
            p.parent.right = r;
        }
        r.left = p;
        p.parent = r;
    }
}

/**
 * 围绕p右旋
 * @param p
 *          pf                        pf
 *           \                         \
 *            p                         pl(l)
 *           / \           ->           /  \
 *       pl(l)  pr                    ll    p
 *       / \                               / \
 *     ll   lr                            lr  pr
 */
private void rightRotate(RBNode p) {
    if (p != null) {
        RBNode l = p.left;
        p.left = l.right;
        if (l.right != null) {
            l.right.parent = p;
        }
        l.parent = p.parent;
        if (p.parent != null) {
            root = l;
        } else if (p.parent.right == p) {
            p.parent.right = l;
        } else {
            p.parent.left = l;
        }
        l.right = p;
        p.parent = l;
    }
}

新增 （七种情况，五种情况需要考虑自平衡）

分情况讨论，主要是找到插入位置，然后自平衡(左旋或者右旋) 且插入结点是红色节点(如果是黑色的话那么当前分支上就会多出一个黑色结点出来，从而破坏了黑色平衡)，以下分析全部以左子树为例，右子树的情况则相反。

  • 情况1、如果插入的是第一个节点(根节点)，红色变黑色
  • 情况2、如果父节点为黑色，则直接插入，不需要变色
  • 如果父节点为红色，叔叔节点也是红色（此种情况爷爷节点一定是黑色），则父节点和叔叔节点变黑色，爷爷节点变红色（如果爷爷节点是根节点，则再变成黑色），爷爷节点此时需要递归（把爷爷节点当做新插入的节点再次进行比较）
  • 如果父节点是红色，没有叔叔节点或者叔叔节点是黑色（此时只能是NIL节点），则以爷爷节点为支点右旋，旋转之后原来的爷爷节点变红色，原来的父节点变黑色。

还是与2-3-4树对比，新增一定在叶子节点上

情况1

情况2——右边相当于左右旋了

与3节点合并情况

裂变情况

删除 (重点) 五种情况、两种需要考虑自平衡，又细分八种情况，其中四种为镜像情况

先看二叉搜索树的删除：

  • 删除叶子节点，直接删除
  • 删除的节点有一个子节点，那么用子节点来替代
  • 如果删除的节点有2个子节点，此时需要找到前驱节点或者后继节点来替代

写代码时，删除方案：

  • 找到前驱节点，复制前驱节点值覆盖准备删除的节点值，然后删除前驱节点
  • 找到后继节点，复制后继节点的值覆盖准备删除的节点值，然后删除后继节点
  • 被删除的前驱节点或者后继节点只有两种情况：1、被删除节点是叶子节点。2、被删除节点只有一个孩子。

找前驱后继代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
     * 找到指定节点的前驱节点，即找小于node节点的最大值
     *
     * @param node
     */
    private RBNode preedecessor(RBNode node) {
        if (node == null) return null;
        else if (node.left != null) {
            RBNode p = node.left;
            while (p.right != null) {
                p = p.right;
            }
            return p;
        } else {
            // 删除时不一定用到，但找前驱时，左子树就得向上找了
            // 找到第一个左拐的地方
            RBNode p = node.parent;
            RBNode ch = node;
            while (p != null && p.left == ch) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    /**
     * 找到指定节点的后继节点，大于节点的最小值
     *
     * @param node
     * @return
     */
    private RBNode sucessor(RBNode node) {
        if (node == null) return null;
        else if (node.right != null) {
            RBNode p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        } else {
            // 删除时不一定用到，但找前驱时，左子树就得向上找了
            // 找到第一个左拐的地方
            RBNode p = node.parent;
            RBNode ch = node;
            while (p != null && p.right == ch) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

红黑树的删除：1先找到节点，2删除

红黑树上面的删除节点一定是2-3-4树上的叶子节点

三局话：

  • 自己能搞定的自己搞定：
    • 如果删除的节点对应于2-3-4树的3节点或者4节点，则直接删除，不用和兄弟或父亲借。
    • 如果删除的是红色节点，则直接删除；如果是黑色节点，则红色节点上来替代，变黑即可
  • 搞不定的找兄弟和父亲帮忙:
    • 前提是找到真正的可用的兄弟结点 (真正的兄弟节点是对应于2-3-4树中的兄弟节点，如上图左，5的兄弟节点是8，图右中5的兄弟节点应该是7和7.5，可以通过旋转来找)
    • 兄弟节点有的借(此时兄弟节点一定是黑色，如果是红色那说明这个节点不是真正的兄弟节点，需要回到上一步找真正的兄弟节点)
    • 兄弟节点有两个子节点的情况(两个子节点肯定是红色，如果是黑色的话相当于此时兄弟节点对应2-3-4树是2节点，不可能有多余的元素可以借)，此时需要旋转变色
    • 兄弟节点只有一个子节点的情况，此时需要旋转变色
  • 父亲和兄弟帮不了那有福同享，有难同当(父亲和兄弟自损)：
    • 前提还是找到真正的兄弟节点
    • 兄弟节点没有多余的元素可借（此时兄弟节点一定为黑色的2节点），此时兄弟节点所在分支也要自损一个黑色节点以达到黑色平衡，最快的方式就是兄弟节点直接变红(相当于减少一个黑色节点)，此时以父节点为root的子树又达到了平衡(两边都比之前少了一个黑色)。但是以祖父结点为root的树依然是不平衡的，此时需要递归处理。