[摘自算法(第4般)]

2-3 查找树

定义

一棵2-3查找树为一棵空树或者由以下节点组成:

2-节点, 含有一个键和2条边,左边指向的2-3树中的键都小于这个键,右键指向的2-3树种的键都大于这个键。

3-节点, 含有2个键3条边,左边指向的2-3树小于小键,中边指向2-3树的键大于小键小于大键,右边指向的2-3树的键大于大键。

示例如下:

image-20210301224030317

查找算法和普通BST类似

主要看插入算法

插入

向2-节点中插入新键

直接把2-节点变成3-节点即可。如图:

image-20210301224355013

向一棵只含有3-节点的树中插入新键

把新键存入这个3-节点,使之称为4-节点,然后把转化成3个2-节点。如图:

image-20210301224559413

向一个父节点为2-节点的3-节点插入新键

把新键存入这个3-节点,使之称为4-节点,但此时不会为中键创建新节点,而是将其移动至父亲节点中。

image-20210301224840517

向一个父节点为3-节点的3-节点插入新键

把新键存入这个3-节点,使之称为4-节点,将其移动至父亲节点中,但是父亲节点又成了4-节点,然后接着往上操作,直到遇到一个2-节点,或者是遇到3-节点的根。

如果是遇到了3-节点的根,则可以按照方法:向一棵只含有3-节点的树中插入新键。将其变成4-节点然后分解。注意:此时树的高度加一。

image-20210301225822653

局部变换不影响全局性质

将一个4-节点分解成2-3树可能有6种情况,但是不论怎么变都不会改变全局的有序性和平衡性。

image-20210301230232101

变换之前空链到根节点的长度为h,变换之后还是h(除了分解那个会变成h+1)

红黑二叉查找树

定义

红黑二叉查找树背后的思想是使用标准的二叉查找树(全是2-节点构成的)和一些额外信息。

我们将树中的连接(边)分成2种类型:

  • 红链接将两个2-节点连接起来构成3-节点
  • 黑链接则是2-3中的普通连接

也就是我们把3-节点表示成一条斜的红色连接。如图:(粗边表示红连接)

image-20210301231021102

对于任何2-3树,只要进行进行节点转换,我们就可以派生出来对应的二叉查找树。我们把这种方式表示的二叉查找树称为红黑二叉查找树(红黑树)。

另外一种等价的定义是:

含有红黑连接并满足下列条件的二叉查找树:

  • 红链接均为左连接
  • 没有任何一个结点同时和2条红连接相连
  • 该树是完美黑色平衡的,即任意空连接到根节点的路径上的黑连接数量相同

性质:

  • 一棵大小为N的红黑树的高度不会超过2lgN。

    证明:红黑树的最坏情况是它对应的2-3树中构成的最左边路径全都是3-节点,其余均为2-节点。此时最左边路径长度为只包含2-节点的2倍(lgn)。

颜色表示:

把连接的颜色保存在Node中的color中。如果指向它的连接时红色的,该变量为true,黑色则为false。当我们提到一个结点的颜色的时候指的是指向该结点连接的颜色。

注意:约定空节点为黑色。

部分代码:

static final boolean RED = true;
static final boolean BLACK = false;
Node root;
private class Node {
    int value;
    Node left, right;
    int n;
    boolean color;

    Node(int value, int n, boolean color) {
        this.value = value;
        this.n = n;
        this.color = color;
    }
}

boolean isRed(Node x) {
    if (x == null) {
        return false;
    }
    return x.color == RED;
}

旋转

左旋:

image-20210301232637347

image-20210301232649558

右旋:

image-20210301232706241

image-20210301232713498

旋转会返回一个连接,可能是黑的,也可能是红的,所以我们将用x.color=h.color保留原连接的红黑状态。部分代码如下:

Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
//        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
//        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

插入

向单个2-节点插入新键

(新增的一定是红色节点,这样可以尽可能保证黑色平衡)

如果新键小于老键,新增一个红色节点即可(即指向新键的红链),如果新键大于老键,新增的红色节点将产生右链,不满足条件,需要将老键进行左旋:root = rotate(root),如图:

image-20210301233455803

向3-节点插入新建

可以分为3种子情况:

  • 新键大于原树中的2个键。这样中间的那个键就会有2条红边,直接把2条红边变黑,然后中间那个节点变红(根节点除外)。如图左1。
  • 新键小于原树中的2个键。会产生两个相连的左红连接,需要右旋,然后变色。如图左2.
  • 新键位于原树2个件之间。会产生一个左红连接和右红连接相连。需要先左旋变成情况2,然后右旋变成情况1,然后变色。如图左3。

image-20210301233920564

颜色变换的时候需要将父节点的颜色由黑变红。这样是为了不影响整棵树的黑色平衡性。

变色之后呢?红链将向上传递。

image-20210301234921499

总结:

插入之后:

  • 如果右子节点是红色的而左子节点是黑色的则左旋,
  • 如果左子节点是红的且左子节点的左子节点也是红的,则右旋。
  • 如果左右节点均为红色,则颜色转换。

代码实现

package demo;

/**
 * @author TylerChen
 * @date 2021/3/1 - 21:39
 */
public class RedBlackTree {
    static final boolean RED = true;
    static final boolean BLACK = false;

    Node root;

    private class Node {
        int value;
        Node left, right;
        int n;
        boolean color;

        Node(int value, int n, boolean color) {
            this.value = value;
            this.n = n;
            this.color = color;
        }
    }

    boolean isRed(Node x) {
        if (x == null) {
            return false;
        }
        return x.color == RED;
    }

    Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
//        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
//        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

    void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    void put(int value) {
        root = put(root, value);
        root.color = BLACK;
    }

    //从下往上传递,要使用后序遍历
    Node put(Node h, int value) {
        if (h == null) {
            return new Node(value, 1, RED);
        }
        if (value < h.value) {
            h.left = put(h.left, value);
        } else if (value > h.value) {
            h.right = put(h.right, value);
        }
        if(isRed(h.right) && !isRed(h.left)){
            h = rotateLeft(h);
        }
        if(isRed(h.left) && isRed(h.left.left)){
            h = rotateRight(h);
        }
        if(isRed(h.left) && isRed(h.right)){
            flipColors(h);
        }
//        h.n = 1 + size(h.left) + size(h.right);
        return h;
    }
}