[Tree]手撕红黑树（LLRBT）

Git 实现代码

自己的红黑树代码实现总结。目标是快速手撕红黑树（插入和查询，不包括删除操作）。

注意，左倾红黑树等价于 2-3 树。

定义

• （节点颜色为红和黑）
• 根节点为黑
• （叶节点为黑）
• 红节点的子节点为黑
• （每个节点到其子孙节点的所有路径上包含相同数目的黑节点）

括号括起来的部分其实是不用记忆的，因为实现了红黑树（左倾）的操作方法后自然会满足其特性。

下面这点也得记住：

• 插入的新节点为红色

结构

RedBlackTree 结构非常简单。

public class RedBlackTree<V extends Comparable<V>, T> {
    Node root;

    // 内部类 Node
    class Node{}

    // 插入方法
    Node insert(V key, T value);
    
    // 查找方法
    T find(V key);
}

核心结构就是一个 Node 节点。

// Node
class Node<V extends Comparable<V>, T> {
    V key;
    Object value;
    boolean isRed;
    Node left;
    Node right;
    Node parent;
    
    // 左旋操作
    void rotateLeft(boolean isLeft);

    // 右旋操作（和左旋完全镜像）
    void rotateRight(boolean isLeft);

    // 平衡操作（LLRBT 的核心部分）
    void balance();

    // 判断当前节点是否是左节点（单纯用于配合左旋和右旋操作）
    boolean isLeft();

    // 查找 value 值
    T find(V key);

    // 查找对应 key 应该在哪个节点下
    Node<V, T> findNode(V key);
}

操作方法

左旋 / 右旋

这个其实是树结构的基础操作了。这里的左旋详细描述是 当前节点的右子节点旋转到当前节点的位置，当前节点变为其右子节点的左子节点（同时也要将右子节点的左子节点接到当前节点的右子节点）。

之所以加一个 isLeft 作为入参，并额外添加 isLeft() 方法，就是为了构建一个通用的左旋 / 右旋操作，对于任何位置的节点都适用（因为正常左旋后，原节点往左下旋转，原节点父节点的子节点被左旋操作替换，因此要修改得知道原节点是其父节点的左还是右子节点）。

// 判断当前节点是否是其父节点的左子节点
private boolean isLeft() {
    if (parent == null || this == parent.left) {
        return true;
    }
    return false;
}

左旋操作（右旋完全镜像就不说明了）：

// 左旋
private void rotateLeft(boolean isLeft) {
    // 右节点为空无法左旋
    if (this.right == null) {
        return;
    }
    // 取到父节点和右节点
    Node parent = this.parent;
    Node right = this.right;
    // 如果当前节点为根节点，则左旋后右节点变为根节点
    if (this == root) {
        root = right;
    }
    // 当前节点的右节点，连接右节点的左子树
    this.right = right.left;
    if (right.left != null) {
        right.left.parent = this;
    }
    // 右节点的左子树连接当前节点
    right.left = this;
    this.parent = right;
    // 如果父节点不为空
    if (parent != null && isLeft) {
        parent.left = right;
        right.parent = parent;
        return;
    }
    if (parent != null) {
        parent.right = right;
        right.parent = parent;
    }
}

这两个方法进行组合，比如：

rotateLeft(isLeft());

无论当前节点是其父节点的左子节点还是右子节点都可以进行左旋。

插入节点定位

findNode() 是在插入操作时，获取新的节点应该到插入到哪个节点下。每个节点都有这个方法，就可以递归调用。

// 给定 key，返回有合适插入位置的父节点
private Node<V, T> findNode(V key) {
    if (key.compareTo(this.key) > 0 && right != null) {
        return right.findNode(key);
    }
    if (key.compareTo(this.key) < 0 && left != null) {
        return left.findNode(key);
    }
    return this;
}

平衡操作

最关键的平衡操作，也就是在插入节点后调用，对整棵红黑树旋转平衡。

只要记住 4 种情况：

private void balance() {
    // ！！！关键点！！！ -> 刷新 root 的状态
    root.isRed = false;
    root.parent = null;
    
    // 黑色节点的左右子节点都为红，调整颜色（情况4）
    if (left != null && right != null && !isRed && left.isRed && right.isRed) {
        isRed = true;
        left.isRed = false;
        right.isRed = false;
        if (parent != null) {
            parent.balance();
        }
        return;
    }
    // 插入在红色左子节点的左侧，右旋（情况3）
    if (parent != null && !parent.isRed && isRed && left != null && left.isRed) {
        parent.rotateRight(parent.isLeft());
        isRed = false;
        right.isRed = true;
        balance();
        return;
    }
    // 插入在红色左子节点的右侧，左旋（情况2）
    if (parent != null && !parent.isRed && isRed && right != null && right.isRed) {
        rotateLeft(true);
        parent.balance();
        return;
    }
    // 直接插在节点右侧，左旋（情况1）
    if (right != null && !isRed && right.isRed) {
        this.right.isRed = false;
        this.isRed = true;
        rotateLeft(isLeft());
    }
}

关键点在于平衡操作之前刷新 root 的信息，因为递归平衡后，root 可能会变化，这里要保证根节点为黑的性质，并且修改 parent 指向 null，不然在递归中会出现错误。

查询和插入

查询就是二叉树查询的方式。

insert 其实是很简单的，通过根节点的 findNode() 递归查找插入位置节点（新节点应该放到到这个节点下面），然后创建新节点（key 相同就不用创建了，直接覆盖插入位置节点的 value 就行），根据大小判断是放在左侧还是右侧（成为插入位置节点的左子节点还是右子节点），然后调用插入位置节点的平衡方法。