关于java:硬核图解红黑树并手写实现

在上一篇中咱们通过二叉树作为了 Map 的实现，最初也剖析了该版本的工夫复杂度以及最蹩脚的状况；本篇咱们将会应用红黑树来实现 Map，改善上一篇中二叉树版本的有余；对于 Map 接口的定义以及曾经实现的专用办法将不会反复叙述，比方二叉树的查找办法（get）；不理解的兄弟请查看上一篇《基于二叉树实现 Map》

红黑树算是数据结构中比拟有难度的知识点，尽管在理论的业务开发工作中应用的不多，然而这是面试官最喜爱问的知识点。

我在之前也看过很多对于红黑树的文章，然而很多都是从红黑树的性质来讲红黑树，基本未从红黑树的实践模型登程讲红黑树，所以造成红黑树比拟难了解。

了解并把握红黑树还是有必要的，Java 中的 HashMap 当链表的节点数超过了 8 个就会把链表转换成红黑树；TreeMap 底层也是用的是红黑树；

红黑树于咱们上一篇探讨的二叉树相比，红黑树简直是完满均衡的，并且可能保障操作的运行工夫都是对数级别

在学习红黑树之前，咱们先来看看红黑树的性质，针对每一条性质咱们都须要问一个 Why，带着问题去学习红黑树；如果咱们搞懂了这些问题，那么就了解了红黑树实质，当然与实现还有一些间隔。

性质 1. 结点是红色或彩色。（why：为什么节点要辨别色彩，红色节点的作用是什么？）
性质 2. 根结点是彩色。（why：为什么根节点必须是彩色）
性质 3. 所有叶子都是彩色。（why）
性质 4. 从每个叶子到根的所有门路上不能有两个间断的红色结点。(why)
性质 5. 从任一节结点其每个叶子的所有门路都蕴含雷同数目的彩色结点。(why)
性质 6. 每次新插入的节点都必须是红色（why）

红黑树是近似均衡的二叉树，红黑树对应的实践模型能够是 2 - 3 树，也能够是 2 -3- 4 树，所以在学习红黑树之前，咱们须要先理解 2 - 3 树和 2 -3- 4 树；

红黑树与 2 - 3 树、2-3- 4 树的关系就好比接口与实现类的关系；2- 3 树与 2 -3- 4 树是接口，而红黑树是基于接口的实现

2- 3 树、2-3- 4 树都是 B 树的特列状况

为了保障树的相对均衡，容许树中的节点保留多个键值，在 2 - 3 树中能够呈现一个节点存在一个键值两条链接，也容许同一个节点蕴含最多两个键三条链接；

2- 3 树如下图：

2- 3 树的查找过程与二叉树相似，查找键与节点中的键比拟，如果遇到与查找键相等的节点，查找命中；否则持续去对应的子树中去查找，如果遇到空的链接示意查找未命中。

向单键 key 的节点中插入：以后节点只有一个 key, 间接在以后节点新增一个 key

向双键 key 的节点中插入：先插入新的 key 到以后节点，如果以后节点大于了两个 key

向双键 key 的节点中插入，并且父节点也是双键

通过下面的三种状况的演示，咱们发现 2 - 3 树和规范的二叉树的成长是不同的，二叉树的成长是由上向下成长的，而 2 - 3 树的成长是由下向上的。

在上一篇的二叉树中，咱们发现最蹩脚的状况是插入的节点有序，导致二叉树进化成了链表，性能降落，咱们应用 2 - 3 树程序插入看看如何，例如程序插入 1，2，3，4，5，6，7

由此咱们能够看出在最坏的状况下 2 - 3 树仍然完满均衡的，有比拟好的性能。然而这是实践，与真正的实现还是有一段距离

理解了红黑树的实践模型 2 - 3 树之后，那么就能够基于 2 - 3 树来实现咱们的红黑树。

因为 2 - 3 树中存在着双键的节点，因为咱们须要在二叉树中示意出双键的节点，所以咱们须要在节点中增加一个色彩的属性 color，如果节点是红色，那么示意以后节点和父节点独特组成了 2 - 3 树中的双键节点。

对上一篇中二叉树的节点做一些批改，代码如下：

class Node implements TreeNode {
    public static final boolean RED = true;
    public static final boolean BLACK = false;
    public K key;
    public V value;
    public Node left;
    public Node right;
    public boolean color; //RED 或者 BLACK
    public int size = 1;  // 以后节点下节点的总个数

    public Node(K key, V value, boolean color) {
        this.key = key;
        this.value = value;
        this.color = color;
    }

    @Override
    public Node getLeft() {return this.left;}

    @Override
    public Node getRight() {return this.right;}

    @Override
    public Color getColor() {return color ? Color.RED : Color.BLACK;}
}

因为红黑树自身也是二叉树，所以在上一篇中实现的二叉树查找办法能够不必做任何的批改就能够间接利用到红黑树。

本篇中咱们实现的 2 - 3 树红黑树参考算法 4，并且咱们规定红色节点只能呈现在左节点，即左倾红黑树。（为什么规定红色节点只能呈现在左节点？其实左边也是能够的，只容许存在左节点是因为可能缩小可能呈现的状况，实现所需的代码绝对较小）

红黑树作为了 2 - 3 树的实现，基于 2 - 3 树去看红黑树的性质就不在是干瘪瘪的约定，也不须要要强行记忆。

性质 1. 结点是红色或彩色。（why：为什么节点要辨别色彩，红色节点的作用是什么？）
在下面咱们曾经解释过了，要辨别色彩次要是想要在二叉树中来示意出 2 - 3 树的双键节点的状况，如果是红色节点，那么示意以后节点与父节点独特组成了 2 - 3 数的双键；彩色节点示意二叉树中的一般节点
性质 2. 根结点是彩色。（why：为什么根节点必须是彩色）
还是基于红色节点的作用来了解，根节点自身没有父节点，无奈组成 2 - 3 树双键，所以不可能是红色节点。
性质 3. 所有叶子都是彩色。（why）
此处提到的叶子其实是空链接，在下面的图中空连贯未画出。
性质 4. 从每个叶子到根的所有门路上不能有两个间断的红色结点。(why)
此性质还是基于红色节点的作用来了解，如果呈现了两个间断的红色节点，那么与父节点组成了 3 键的节点，然而这在 2 - 3 树实现的左倾红黑树中是不容许的。（在基于 2 -3- 4 树实现的红黑树中容许呈现 3 键，然而只能是左右两边各一个红色节点，也不能间断，在前面扩大局部会有解说）
性质 5. 从任一节结点到其每个叶子的所有门路都蕴含雷同数目的彩色结点。(why)
此性质能够基于 2 - 3 树的实践模型来了解，因为在红色节点示意与父节点同层高，所以在红黑树中只有彩色节点会奉献树的高度，所以从任一节结点到其每个叶子的所有门路都蕴含雷同数目的彩色结点
性质 6. 每次新插入的节点都必须是红色 （why）
此性质在百度百科中未呈现，但在一些国外网站上有看到，集体感觉对于了解红黑树也有帮忙，所以加在了这里；在下面咱们曾经演示过了 2 - 3 树插入键的过程，先插入键值到节点，而后在判断是否须要决裂，因为优先插入建到以后节点组成 2 - 3 树的双键或 3 键，而在红黑树中只有通过应用红色节点与父节点组成 2 - 3 树的双键或 3 键，所以每次新插入的节点都必须是红色。

2- 3 树中单键节点在红黑树中的示意

2- 3 树中双键节点在红黑树中的示意，因为是左倾红黑树，所以只能呈现红色节点在右边

只看节点的变动可能不太直观，咱们能够来看一个 2 - 3 树如何示意成左倾红黑树

当咱们把红色节点拖动到与父节点同一个高度的时候，能够与 2 - 3 树比照来看，发现红黑树很好的示意了 2 - 3 树

我须要定义个办法来判断节点属于什么色彩，如果是红色就返回 true，否则返回 false

protected boolean isRed(Node node) {if (Objects.isNull(node)) {return Node.BLACK;}
    return node.color;
}

在实现红黑树的插入或者删除操作可能会呈现红色节点在左边或者两个间断的红色节点，在呈现这些状况的时候咱们须要通过旋转操作来实现修复。

因为旋转操作实现之后须要批改父节点的链接，所以咱们定义的旋转办法须要返回旋转之后的节点来重置父节点的链接

左旋

左旋代码实现如下：

protected Node rotateLeft(Node h) {
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = Node.RED;

    size(h); // 计算子树节点的个数
    size(x);

    return x;
}

从新指定两个节点的左右子树的链接，并且批改节点的色彩。其次是计算每个子树所蕴含的节点个数，计算的形式与上一篇中二叉树的 size 实现相似，这里就不反复叙述，参考《基于二叉树实现 Map》

右旋

右旋代码实现如下：

protected Node rotateRight(Node h) {
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = Node.RED;

    size(h);
    size(x);

    return x;
}

在 2 - 3 树中，当节点中的 key 值达到了 3 个就须要进行决裂，其中一个节点将会上浮；那在红黑树中应该如何来示意这个操作呢？

在红黑树中要实现节点决裂，其实就是节点色彩的变动；红黑树通过左旋右旋之后最终都会达到父节点是彩色，左右两个子节点是红色（前面再插入操作中能够看到具体的转变过程），这种状态就对应了 2 - 3 树中的三键节点的状况，这时候决裂的操作就是把左右两个子节点的色彩变成彩色，父节点变成红色。

代码实现如下：

/ 转换色彩，对应了 23 树中的节点决裂
protected void upSplit(Node node) {if (Objects.isNull(node)) {return;}
    node.left.color = Node.BLACK;
    node.right.color = Node.BLACK;
    node.color = Node.RED;
}

向单键节点插入

如果插入的键小于以后节点的键值，那么间接新增一个红色左节点

如果插入的键大于以后节点的键值，那么插入一个红色的右节点，因为只容许右边呈现红色节点，所以咱们须要进行左旋一次

向双键节点中插入

向双键节点中插入新的键有三种状况，咱们先来看最简略的状况，插入的键值最大，插入之后只须要变动色彩即可，变动过程如下图

第二种状况是插入的键值最小，插入之后造成了两个红色节点相连，所以须要进行右旋，而后在变色

第三种状况插入的键值在原来两键之间，须要先进行左旋，再右旋，最初在变色

依据以上各种状况的剖析，咱们能够总结出对立的变化规律：

若右子节点是红色，左子节点是黑树，那么就进行左旋
若左子节点是红色且他的左子节点也是红色，那么就进行右旋
若左右子节点都是红色，那么就进行色彩转换

图形变动如下：

通过下面的剖析之后咱们当初能够来代码实现红黑树的插入操作

@Override
public void put(K key, V value) {if (Objects.isNull(key)) {throw new IllegalArgumentException("the key can't null");
    }
    root = put(root, key, value);
    root.color = Node.BLACK; 
}

private Node put(Node node, K key, V value) {if (Objects.isNull(node)) {return new Node(key, value, Node.RED);
    }
    int compare = key.compareTo(node.key);
    if (compare > 0) {node.right = put(node.right, key, value);
    } else if (compare < 0) {node.left = put(node.left, key, value);
    } else {node.value = value;}

    if (isRed(node.right) && !isRed(node.left)) {node = rotateLeft(node);
    }
    if (isRed(node.left) && isRed(node.left.left)) {node = rotateRight(node);
    }
    if (isRed(node.left) && isRed(node.right)) {upSplit(node);
    }

    size(node);
    return node;
}

因为根节点必须为彩色的性质，避免变色操作把根节点变为红色，所以咱们在插入操作之后对立设置一次根节点为彩色；

红黑树的插入操作前半部分和上一篇实现的二叉树的插入操作统一，惟一不同的只有最初三个 if 操作，这三个操作就是下面总结的对立变化规律的代码实现。

第一个 if 判断解决如果右节点是红色，左节点是彩色，那么就进行左旋

第二个 if 判断解决如果左节点时红色且他的左节点也是红色，那么就进行右旋

第三个 if 判断如果左右两个子节点都是红色，那么就进行变色

因为删除操作可能会造成树不均衡，并且可能会毁坏红黑树的性质，所以删除操作会比插入操作更加麻烦。

首先咱们须要先回到 2 - 3 树的实践模型中，如果咱们删除的节点以后是双键节点，那么咱们能够间接进行删除操作，树的高度也不会构造也不会发生变化；所以红黑树的删除操作的要害就是须要保障待删除节点是一个双键的节点。

在执行删除操作时咱们也会实现到变色的操作，这里的变色和插入是的变色操作恰好相反，父节点变为彩色，两个子节点变为红色

protected void flipColors(Node h) {
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
}

在正式实现删除操作之前，咱们先来探讨下红黑树删除最小值和最大值的状况，最初实现的删除操作也会应用到删除最小值和删除最大值

删除最小值

二叉树删除最小值就是始终沿着树的左子树中查找，直到遇到一个节点的左子树为 null，那么就删除该节点

红黑树的删除最小值相似，然而咱们须要保障待删除的节点是一个双键的节点，所以在在递归到每个节点是都须要保住以后节点是双键节点，那么在最初找到的最小值就肯定会在一个双键节点中（因为递归时曾经保住的父节点是双键节点）。

那么如果保障以后递归节点是一个双键节点呢？这里就会有 3 中状况:

以后节点的左子节点是一个双键节点，间接删除

以后节点的左子节点是一个单键节点，但他的兄弟是一个双键节点，那么通过旋转挪动一个节点到左子节点造成双键节点之后，再执行删除操作

以后节点的左子节点和右子节点都是单键节点，那么通过变色与父节点独特造成三键节点之后，再执行删除

以上是红黑树删除最小值会遇到的所有状况，针对最初两种状况，为了代码的实现简略，咱们思考把这两种状况进行合并；

先把初始化根节点为红色，再进行变色，而后判断是否 node.right.left 是红色，如果是就进行旋转操作

删除最小值的代码实现如下：

private Node moveToRedLeft(Node h) {flipColors(h);
    if (isRed(h.right.left)) {h.right = rotateRight(h.right);
        h = rotateLeft(h);
        flipColors(h);
    }
    return h;
}

@Override
public void deleteMin() {if (isEmpty()) {throw new NoSuchElementException("BST underflow");
    }

    if (!isRed(root.left) && !isRed(root.right)) {root.color = Node.RED;}

    root = deleteMin(root);
    if (!isEmpty()) {root.color = Node.BLACK;}
}

private Node deleteMin(Node h) {if (h.left == null) {return null;}

    if (!isRed(h.left) && !isRed(h.left.left)) {h = moveToRedLeft(h);
    }

    h.left = deleteMin(h.left);
    return balance(h);
}

private Node balance(Node h) {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.size = size(h.left) + size(h.right) + 1;
    return h;
}

在删除掉最小值之后，咱们须要从新修复红黑树，因为之前咱们的操作可能会导致 3 键节点的存在，删除之后咱们须要从新合成 3 建节点；下面代码中的 balance 就是从新修复红黑树。

删除最大值

删除最大值思路和删除最小值的思路相似，这里就不具体叙述了，间接上图

删除最大值须要从左节点中借一个节点，代码实现如下：

@Override
public void deleteMax() {if (isEmpty()) {throw new NoSuchElementException("BST underflow");
    }

    if (!isRed(root.left) && !isRed(root.right)) {root.color = Node.RED;}

    root = deleteMax(root);
    if (!isEmpty()) {root.color = Node.BLACK;}

}

private Node deleteMax(Node node) {if (isRed(node.left)) { // 此处与删除最小值不同，如果右边是红色，那么先借一个节点到左边来
        node = rotateRight(node);
    }
    if (Objects.isNull(node.right)) {return null;}
    if (!isRed(node.right) && !isRed(node.right.left)) {node = moveToRedRight(node);
    }
    node.right = deleteMax(node.right);
    return balance(node);
}

private Node moveToRedRight(Node node) {flipColors(node);
    if (isRed(node.left.left)) {node = rotateRight(node);
        flipColors(node);
    }
    return node;
}

在查找门路上进行和删除最小值雷同的变换能够保障在查找过程中任意以后节点不会是双键节点；

如果查找的键值在左节点，那么就执行与删除最小值相似的变动，从左边借节点；

如果查找的键值在右节点，那么就执行与删除最大值相似的变动，从右边借节点。

如果待删除的节点解决叶子节点，那么能够间接删除；如果是非叶子节点，那么左子树不为空就与左子树中最大值进行替换，而后删除左子树中的最大值，左子树为空就与右子树最小值进行替换，而后删除右子树中的最小值。

代码实现如下：

@Override
public void delete(K key) {if (isEmpty()) {throw new NoSuchElementException("BST underflow");
    }

    if (!isRed(root.left) && !isRed(root.right)) {root.color = Node.RED;}

    root = delete(root, key);
    if (!isEmpty()) {root.color = Node.BLACK;}
}


private Node delete(Node node, K key) {int compare = key.compareTo(node.key);
    if (compare < 0) {// 左子树中查找
        if (!isRed(node.left) && !isRed(node.left.left)) {node = moveToRedLeft(node);
        }
        node.left = delete(node.left, key);
    } else if (compare > 0) { // 右子树中查找
        if (isRed(node.left)) {node = rotateRight(node);
        }
        if (!isRed(node.right) && !isRed(node.right.left)) {node = moveToRedRight(node);
        }
        node.right = delete(node.right, key);
    } else {if (Objects.isNull(node.left) && Objects.isNull(node.right)) {return null; // 叶子节点间接完结}

        if (Objects.nonNull(node.left)) { // 左子树不为空
            Node max = max(node.left);
            node.key = max.key;
            node.value = max.value;
            node.left = deleteMax(node.left);
        } else { // 右子树不为空
            Node min = min(node.right);
            node.key = min.key;
            node.value = min.value;
            node.right = deleteMin(node.right);
        }
    }
    return balance(node);
}

下面咱们曾经实现了红黑树的次要代码，然而如何验证咱们的红黑树是不是真正的红黑树，最好的形式就是基于咱们实现的版本画出红黑树，而后通过红黑树的性质来验证

因为如何画出红黑树不是本篇的重点，所以就不贴出代码了，有须要的敌人能够去仓库中查看；

编写单元来测试咱们用红黑树实现的 Map, 并且画出红黑树验证是否正确

@Test
public void testDelete() throws IOException {RedBlack23RedBlackTreeMap<Integer, String> map = new RedBlack23RedBlackTreeMap<>();
    map.put(8, "80");
    map.put(18, "180");
    map.put(5, "50");
    map.put(15, "150");
    map.put(17, "170");
    map.put(25, "250");
    map.put(40, "40");
    map.put(80, "80");
    map.put(30, "30");
    map.put(60, "60");
    map.put(16, "16");

    map.draw("/Users/huaan9527/Desktop/redBlack4.png"); // 画出删除之前的红黑树
    map.delete(40);
    map.delete(17);
    map.delete(25);
    map.nodes().forEach(System.out::println); // 依据 key 从小到大程序打印出节点

    map.draw("/Users/huaan9527/Desktop/redBlack5.png"); // 画出删除之后的红黑树
}

程序打印出 node 的执行的后果：

删除之前的红黑树

删除之后的红黑树

本篇次要探讨的是基于 2 - 3 树实现的红黑树版本，了解并把握了本篇内容也就把握了红黑树，面试时基本不虚。

为了加深对红黑树的了解，大家能够自行基于 2 -3- 4 树去实现红黑树，比照两种红黑树的版本差别，能够参考我的 git 仓库中的代码

文中所有源码已放入到了 github 仓库:
https://github.com/silently9527/JavaCore

给出一个红黑树网站演示，该网站实现红黑树的形式与本篇咱们实现的形式不同，大家能够参考下：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源🙏

程序员罕用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin

微信公众号：贝塔学 Java

关于java:硬核图解红黑树并手写实现

前言

均衡查找树

2- 3 树

查找

插入

基于 2 - 3 树实现的左倾红黑树

红黑树性质解释

2- 3 树在左倾红黑树中示意

判断节点的色彩

旋转

变色

插入

向单键节点插入

向双键节点中插入

删除

删除最小值

删除最大值

删除任意节点

画出红黑树来验证实现

总结

最初（点关注，不迷路）