乐趣区

关于数据结构:35如果面试让我手写红黑树

jiezi

作者：小傅哥
博客：https://bugstack.cn

积淀、分享、成长，让本人和别人都能有所播种！😄

一、前言：挂在树上！

不晓得你经验过 HashMap 的夺命连环问！

为啥，面试官那么喜爱让你聊聊 HashMap？因为 HashMap 波及的货色广，用到的数据结构多，问题延展性好，一个 HashMap 就能聊下来 80% 的数据结构了。而且面试 HashMap 能通过你对红黑树的理解定位出你哪个级别的研发人员。

而红黑树的知识点能够说是十分宏大，在学习红黑树时也不能一下就能把握，甚至很程序员压根就没搞明确红黑树，只是背下来它的几条限定规定而已。

其实一开始我也是这样！ 不过总感觉这块的知识点不搞个明明白白，就闹心。因为不可能一个文科的货色，是须要死记硬背搞下来的。所以在翻阅材料、文档、历史、典籍，找到红黑树的演化过程，它是从 2 - 3 树演变而来，而 2 - 3 树、AVL 树，这类 B - 树，也就是 BalancedTree 均衡树。它们都是为了解决 BST 二叉搜寻树不自均衡而来的产物。

那么当初分明了，要想搞定红黑树，让懂了就是真的懂，就须要把后面这些常识搞定，并且除了实践还能用落地的案例代码编写进去，才是悟透。好，那么接下来，小傅哥就带着你一起搞定这点事

二、BST 树

Binary Search Tree 历史

二叉搜寻树算法是由包含 PF Windley、Andrew Donald Booth、Andrew Colin、Thomas N. Hibbard 在内的几位钻研人员独立发现的。该算法归功于 Conway Berners-Lee 和 David Wheeler，他们在 1960 年应用它在磁带中存储标记数据。最早和风行的二叉搜寻树算法之一是 Hibbard 算法。

1. 二叉搜寻树数据结构

二叉搜寻树（Binary Search Tree），也称二叉查找树。如果你看见有序二叉树（Ordered Binary tree）、排序二叉树（Sorted Binary Tree）那么说的都是一个货色。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-bst-01.png?raw=true" width="400px">

</div>

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也别离为二叉查找树；

二叉搜寻树在日常开发中应用的场景还是比拟多的，例如基于组合模式实现的规定引擎，它就是一颗二叉搜寻树。但相似这样的开发中用到的二叉树场景，都是基于配置生成，所以组合进去的节点也更加不便管制树高和平衡性。这与 Java API HashMap 中的红黑树这样为了解决插入节点后仍放弃树的平衡性是有所不同的。

所以二叉搜寻树也是一颗没有通过调衡的基础性数据结构，在肯定概率上它实现有可能进化成链表，也就是从近似 O(logn)的工夫复杂度进化到 O(n)。对于二叉搜寻树的均衡解决方案，包含；AVL 树、2- 3 树、红黑树等，小傅哥会在后续的章节持续实现。

2. 二叉搜寻树结构实现

二叉搜寻树是整个树结构中最根本的树，同时也是树这个体系中实现起来最容易的数据结构。但之所以要应用基于二叉搜寻树之上的其余树结构，次要是因为应用数据结构就是对数据的寄存和读取。那么为了进步吞吐效率，则须要尽可能的均衡元素的排序，体现在树上则须要进行一些列操作，所以会有不同的构造树实现。

而实现二叉搜寻树是最好的根底学习，理解根本的数据结构后才更容易扩大学习其余树结构。

  • 源码地址：https://github.com/fuzhengwei/java-algorithms
  • 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

2.1 树枝定义

public Integer value;
public Node parent;
public Node left;
public Node right;
  • 用于组成一颗树的节点，则须要包含；值和与之关联的三角构造，一个父节点、两个孩子节点。如果是 AVL 树还须要树高，红黑树还须要染色标记。

2.2 插入节点

public Node insert(int e) {if (null == root) {root = new Node(e, null, null, null);
        size++;
        return root;
    }
    
    // 索引出待插入元素地位，也就是插入到哪个父元素下
    Node parent = root;
    Node search = root;
    while (search != null && search.value != null) {
        parent = search;
        if (e < search.value) {search = search.left;} else {search = search.right;}
    }
    
    // 插入元素
    Node newNode = new Node(e, parent, null, null);
    if (parent.value > newNode.value) {parent.left = newNode;} else {parent.right = newNode;}
    size++;
    return newNode;
}
  • 首先判断插入元素时候是否有树根，没有则会把以后节点创立出一颗树根来。
  • 如果以后树是有树根的，则对插入元素与以后树进行一个节点遍历操作，找到元素能够插入的索引地位 parent（挂到这个父节点下）。也就是 search 搜寻过程。
  • 最初就是插入元素，通过给插入值创立一个 Node 节点，并绑定它的父元素，以及把新元素挂到索引到的 parent 节点下。

2.3 索引节点

public Node search(int e) {
    Node node = root;
    while (node != null && node.value != null && node.value != e) {if (e < node.value) {node = node.left;} else {node = node.right;}
    }
    return node;
}
  • 值查找的过程，就是对二叉搜寻树的遍历，一直的循环节点，依照节点值的左右匹配，找出最终相当的值节点。

2.4 删除节点

public Node delete(int e) {Node delNode = search(e);
    if (null == delNode) return null;
    return delete(delNode);
}

private Node delete(Node delNode) {if (delNode == null) return null;
    Node result = null;
    if (delNode.left == null) {result = transplant(delNode, delNode.right);
    } else if (delNode.right == null) {result = transplant(delNode, delNode.left);
    } else {
        // 因为删除的节点，有 2 个孩子节点，这个时候找到这条分支下，最左侧做小的节点。用它来替换删除的节点
        Node miniNode = getMiniNode(delNode.right);
        if (miniNode.parent != delNode) {
            // 替换地位，用 miniNode 右节点，替换 miniNode
            transplant(miniNode, miniNode.right);
            // 把 miniNode 晋升父节点，设置右子树并进行挂链。代替待删节点
            miniNode.right = delNode.right;
            miniNode.right.parent = miniNode;
        }
        // 替换地位，删除节点和 miniNode 可打印测试察看；System.out.println(this);
        transplant(delNode, miniNode);
        // 把 miniNode 晋升到父节点，设置左子树并挂链
        miniNode.left = delNode.left;
        miniNode.left.parent = miniNode;
        result = miniNode;
    }
    size--;
    return result;
}
private Node getMinimum(Node node) {while (node.left != null) {node = node.left;}
    return node;
}

private Node transplant(Node delNode, Node addNode) {if (delNode.parent == null) {this.root = addNode;}
    // 判断删除元素是左 / 右节点
    else if (delNode.parent.left == delNode) {delNode.parent.left = addNode;} else {delNode.parent.right = addNode;}
    // 设置父节点
    if (null != addNode) {addNode.parent = delNode.parent;}
    return addNode;
}
2.4.1 删除单节点

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-bst-02.png?raw=true" width="400px">

</div>

  • 待删除节点 14，判断此节点的父节点的孩子节点，哪个等于 14，找出左右
  • 把待删节点的右孩子节点，挂到删除节点的右节点
  • 给待删节点的右孩子节点，设置上父节点
2.4.2 删除双节点

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-bst-03.png?raw=true" width="400px">

</div>

  • 待删除节点 64，含有双子节点，则须要依据第一个右子节点查找最小左子节点。从 89 到 72，如果有比 72 还小的左子节点，持续排查。
  • 排查到节点 72，将 72 这个筹备替换待删元素的节点，与右子节点 73 进行地位替换，过程与 4.1 雷同。应用替换函数 transplant
  • 最初是进行节点 72 与待删节点 64 的替换过程，更换三角关系，父节点、左子节点、右子节点。

3. 二叉搜寻树功能测试

为了不便察看树结构的变动，这里小傅哥找了一些材料材料，一种是咱们能够通过程序来打印（相似大家之前打印 99 乘法表，另外是应用线上的可视化图：https://visualgo.net/zh/bst?slide=1）

3.1 随机插入元素

@Test
public void test_binary_search_tree() {BinarySearchTree tree = new BinarySearchTree();
    for (int i = 0; i < 10; i++) {tree.insert(new Random().nextInt(100));
    }
    System.out.println(tree);
}

测试后果

         /----- 91
         |       \----- 78
 /----- 74
 |       \----- 67
61
 |       /----- 51
 \----- 40
         |       /----- 28
         \----- 14
                 \----- 7
                 
Process finished with exit code 0
  • 因为你测试时的随机数不同，可能会呈现很多不同构造的二叉搜寻树，也可能是一个相似链表构造的进化树。

3.2 插入并且删除

@Test
public void test_insert_delete(){BinarySearchTree tree = new BinarySearchTree();
    tree.insert(32);
    tree.insert(7);
    tree.insert(64);
    tree.insert(63);
    tree.insert(89);
    tree.insert(72);
    tree.insert(94);
    tree.insert(6);
    tree.insert(14);
    tree.insert(18);
    tree.insert(73);
    System.out.println(tree);
    
    // 删除单节点，只有一个孩子的父节点
    // tree.delete(14);
    
    // 删除双节点，领有二个孩子的父节点
    tree.delete(64);
    System.out.println(tree);
}

测试后果

                 /----- 94
         /----- 89
         |       |       /----- 73
         |       \----- 72
 /----- 64
 |       \----- 63
32
 |               /----- 18
 |       /----- 14
 \----- 7
         \----- 6

                 /----- 94
         /----- 89
         |       \----- 73
 /----- 72
 |       \----- 63
32
 |               /----- 18
 |       /----- 14
 \----- 7
         \----- 6


Process finished with exit code 0
  • 这个案例就是 删除双节点 的案例，删除了节点 64 当前，节点 72 被提取上来应用。读者搭档也能够尝试删除其余节点测试验证

三、AVL 树

AVL 树历史

在计算机科学中，AVL 树以其两位苏联发明家 Georgy Adelson-Velsky 和 Evgenii Landis 的名字命名，他们在 1962 年的论文“信息组织算法”中发表了它。它是一种自均衡二叉搜寻树(BST)，这是创造的第一个这样的数据结构。

1. AVL 树数据结构

AVL 自均衡二叉树的呈现，其目标在于解决二叉搜寻树进化成链表的问题。当咱们向 BST 二叉搜寻树程序存入 1、2、3、4、5、6、7 个元素时，它会进化成一条链表，因此失去树查问的工夫复杂度，所以咱们须要 AVL 树均衡树高。如图所示

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-avl-01.png?raw=true" width="500px">

</div>

那么 AVL 树是怎么均衡树高的呢？

当二叉树的左右分支树高差不为 1 时，须要进行左旋或者右旋，来调衡树高。这有点像开车的时候，如果车头偏左就往右打方向盘，车头偏右就往左打方向盘是一个情理。那这个方向盘 (左旋、右旋) 是怎么打的呢，次要分以下四种状况；

左旋（新增节点 6） 右旋（新增节点 1） 左旋 + 右旋（新增节点 4） 右旋 + 左旋（新增节点 3）
条件：节点 4，均衡因子为 -2，左旋 条件：节点 3，均衡因子为 2，右旋 条件：节点 3，均衡因子为 2，右旋。但当节点 2 均衡因子 - 1 先左旋。 条件：节点 2，均衡因子为 -2，左旋。但当节点 5 均衡因子 1 先右旋。
  • 节点树高：以节点 4 为阐明，最长的左右分支节点个数，就是节点 4 的最大树高。这里节点 4 左右孩子节点最长门路都为 2，所以它的树高为 2。同理可计算其余节点树高。
  • 均衡因子：通过以后节点的左右子节点作差计算均衡因子，之后 AVL 树通过均衡因子，定义了什么时候进行左旋和右旋。
  • 源码地址：https://github.com/fuzhengwei/java-algorithms
  • 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

2. AVL 树代码实现

对于 AVL 树的实现与 BST 二叉搜寻树相比，在树的节点定义上多了一个树高的属性。也有些 AVL 树应用的是均衡因子的属性，就是通过树高计算后的后果。树节点代码构造如下；

public class Node {

    public Class<?> clazz;
    public Integer value;
    public Node parent;
    public Node left;
    public Node right;
    // AVL 树所需属性
    public int height;
    
}

接下来小傅哥就别离通过代码解说下一颗 AVL 树的左旋、右旋、左旋 + 右旋、右旋 + 左旋的代码操作。不要放心这没有多简单，只有你能搞清楚左旋，就能搞清楚右旋。两旋弄懂组合就没啥难度了。

  • 源码地址：https://github.com/fuzhengwei/java-algorithms
  • 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/stack
  • 动画演示：https://visualgo.net/zh/bst?slide=1 —— AVL 树首次了解还是比拟艰难的，能够联合学习内容的同时做一些动画演示。

2.1 左旋

图解左旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它合成展现，整个过程如下；

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-avl-06.png?raw=true" width="500px">

</div>

代码实现

protected Node rotateLeft(Node node) {
    Node temp = node.right;
    temp.parent = node.parent;
  
    node.right = temp.left;
    if (node.right != null) {node.right.parent = node;}
  
    temp.left = node;
    node.parent = temp;
  
    if (temp.parent == null) {root = temp;} else {if (temp.parent.left == node) {temp.parent.left = temp;} else {temp.parent.right = temp;}
    }
    return temp;
}
  1. 左旋的作用，相当于通过向上迁徙树高差大于 1 的右子节点来升高树高的操作。
  2. 通过节点 4 拿到父节点 2 和右子节点 5，把父节点 2 和右子节点 5 建设关联
  3. 节点 5 的左子节点，相当于是大于 4 小于 4 的那么一个值，只不过这里不体现。那么这个节点 4 的左子节点，应该被迁徙到节点 3 的右子节点上。
  4. 整顿节点 5 的关系，左子节点为 4。左子节点 4 的父节点为 5
  5. 如果说迁徙上来的节点 5 无父节点，那么它就是父节点 root = temp
  6. 迁徙上来的节点 5，找到原节点 4 是对应父节点的左子节点还是右子节点，对应的设置节点 5 的左右地位

2.2 右旋

图解右旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它合成展现，整个过程如下；

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-avl-07.png?raw=true" width="500px">

</div>

代码实现

protected Node rotateRight(Node node) {
    Node temp = node.left;
    temp.parent = node.parent;
    node.left = temp.right;
    if (node.left != null) {node.left.parent = node;}
    temp.right = node;
    node.parent = temp;
    if (temp.parent == null) {root = temp;} else {if (temp.parent.left == node) {temp.parent.left = temp;} else {temp.parent.right = temp;}
    }
    return temp;
}
  1. 右旋的作用，相当于通过向上迁徙树高差大于 1 的右子节点来升高树高的操作。
  2. 通过节点 3 拿到父节点 4 和左子节点 2，把父节点 7 和左子节点 2 建设关联
  3. 节点 2 的右子节点，相当于是大于 2 小于 3 的那么一个值，只不过这里不体现。那么这个节点 2 的右子节点，应该被迁徙到节点 3 的左子节点上。
  4. 整顿节点 2 的关系，右子节点为 3。右子节点 3 的父节点为 2
  5. 如果说迁徙上来的节点 2 无父节点，那么它就是父节点 root = temp
  6. 迁徙上来的节点 2，找到原节点 3 是对应父节点的左子节点还是右子节点，对应的设置节点 2 的左右地位

2.3 左旋 + 右旋

之所以会有左旋 + 右旋，是因为一次右旋操作没法均衡树高，而这种树的不均衡节点的左子节点的右子节点过长，所以要把不均衡节点的左子节点向左旋转一次，之后再进行右旋操作。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-avl-08.png?raw=true" width="800px">

</div>

代码实现

if (factor(node.left) >= 0) {Node temp = super.rotateRight(node);
    refreshHeight(temp.right);
    refreshHeight(temp);
} else {Node temp = super.rotateLeft(node.left);
    refreshHeight(temp.left);
    refreshHeight(temp);
    node.left = temp;
    
    temp = super.rotateRight(node);
    refreshHeight(temp.right);
    refreshHeight(temp);
}

2.4 右旋 + 左旋

之所以会有右旋 + 左旋，是因为一次左旋操作没法均衡树高，而这种树的不均衡节点的右子节点的左子节点过长，所以要把不均衡节点的右子节点向右旋转一次，之后再进行左旋操作。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-avl-09.png?raw=true" width="800px">

</div>

代码实现

if (factor(node.right) <= 0) {Node temp = super.rotateLeft(node);
    refreshHeight(temp.left);
    refreshHeight(temp);
} else {Node temp = super.rotateRight(node.right);
    refreshHeight(temp.right);
    refreshHeight(temp);
    node.right = temp;
    
    temp = super.rotateLeft(node);
    refreshHeight(temp.left);
    refreshHeight(temp);
}

3. AVL 树功能测试

为了验证 AVL 树的实现正确与否，这里咱们做一下随机节点的插入，如果它能始终保持平衡，那么它就是一颗牢靠 AVL 均衡树。

单元测试

@Test
public void test_random() {AVLTree tree = new AVLTree();
    for (int i = 0; i < 30; i++) {tree.insert(new Random().nextInt(100));
    }
    System.out.println(tree);
}

测试后果

输出节点：61,3,34,82,1,75,56,65,87,18,3,96,53,50,42,24,69,11,95,69,1,1,84,22,5,70,28,55,38,92

                         /----- 96(0)
                 /----- 95(1)
                 |       \----- 92(0)
         /----- 87(2)
         |       |       /----- 84(0)
         |       \----- 82(1)
 /----- 75(3)
 |       |               /----- 70(0)
 |       |       /----- 69(1)
 |       \----- 69(2)
 |               \----- 65(0)
61(5)
 |               /----- 56(1)
 |               |       \----- 55(0)
 |       /----- 53(2)
 |       |       |       /----- 50(0)
 |       |       \----- 42(1)
 |       |               \----- 38(0)
 \----- 34(4)
         |                       /----- 28(0)
         |               /----- 24(1)
         |               |       \----- 22(0)
         |       /----- 18(2)
         |       |       \----- 11(1)
         |       |               \----- 5(0)
         \----- 3(3)
                 |       /----- 3(1)
                 |       |       \----- 1(0)
                 \----- 1(2)
                         \----- 1(0)


Process finished with exit code 0
  • 随机插入 30 个节点，每个节点的程序曾经打印，通过 AVL 左右旋调衡后，二叉构造始终保持树高均衡因子不超过 1，那么验证通过。

四、2- 3 树

这时候大部分材料会用 2- 3 树 来解说 红黑树 ，不过又不去实现一个2- 3 树，只是用了一个实践套另外一个实践。尽管能从了解上多一些参考，但始终感觉没有抓手呀。对于文科思维来说，你得给我货色呀。老是整这悬得楞的🥶谁能受了。 所以这里咱们先来用 Java 实现一个 2 - 3 树，有了根底再学习红黑树

1. 2- 3 树数据结构

2–3 树是一种树型数据结构，由约翰·霍普克洛夫特于 1970 年创造。它通过在一个节点寄存 1 - 2 个元素来均衡树高。从而也使 2 - 3 树存在 2 叉节点和 3 叉节点。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-23-01.png?raw=true" width="400px">

</div>

这里要提到一点，在 BST 二叉搜寻树可能进化成链表的根底上。引出了自均衡二叉树，也就是包含上一章实现的 AVL 树和 Java API HashMap 中用到的红黑树，它们都属于 BalancedTree，也统称为 B 树，均衡的意思。

而本章实现的 2 - 3 树也是一种简略的均衡树，其中每个具备子节点（外部节点）的节点要么有两个子节点（2 节点）和一个数据元素，要么有三个子节点（3 节点）和两个数据元素。另外 2-3 树是 3 阶 B 树，2-3-4 树是 4 阶 B 树。

在实现 2 - 3 树之前，先通过图稿演示下在 2 - 3 树中程序插入 1、2、3、4、5、6、7，七个元素时，2- 3 树的调衡解决。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-23-02.png?raw=true" width="600px">

</div>

  • 2-3 树的插入过程与 BST 树相似，会通过树的左右节点大小，找到本人的插入地位。
  • 一个节点能够右 1 - 3 个元素，但当元素个数为 3 时，则须要调衡。把三个节点的两头节点降职上来，其余两个节点为子节点。
  • 如果进行一次调衡后，上一层父节点达到 3 个元素，则须要 2 次调衡，来满足 2 - 3 树的规定。

咋样，是不看过这个图之后对于 2 - 3 树的实现曾经有感觉了，想入手写写试试了？

  • 源码地址：https://github.com/fuzhengwei/java-algorithms
  • 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

2. 2- 3 树结构实现

2-3 树的实现并不简单，但在实现前要思考🤔以下几个问题；

  • Node 节点属性信息都包含什么？
  • 插入值，是否须要创立新的 Node？
  • 插入后，节点内有 3 个元素后，怎么迁徙元素？

2.1 节点定义

public class Node_2_3 {

    // 元素
    public int[] items;
    // 序号
    public int number;
    // 孩子
    public Node_2_3[] children;
    // 父亲【非必须】public Node_2_3 parent;

    public Node_2_3() {this.items = new int[3];
        this.number = 0;
        this.children = new Node_2_3[4];
        this.parent = null;
    }
    
    public void insert(int e) {
        int idx = this.number - 1;
        while (idx >= 0) {if (this.items[idx] < e) break;
            this.items[idx + 1] = this.items[idx];
            --idx;
        }
        this.items[idx + 1] = e;
        ++this.number;
    }
    
    // ... 省略局部代码
}
  • 2- 3 树的几点元素须要包含；一个数组的元素汇合、元素的序号、孩子元素。因为一个节点最多可长期放入 3 个元素，那么就会最多有 4 个孩子元素，所以孩子元素也是一个数组并且在构造函数中依照 4 个元素进行初始化。
  • 因为自身 2 - 3 树插入元素的开始阶段，并不是间接创立一个新的节点，而是在初始化的数组空间中存入元素。所以在节点中提供了一个插入元素的办法 insert 来解决新增元素。
  • 另外 2 - 3 树的节点类，还提供了一个不便查问的办法。包含：获取右边元素、两头元素、左边元素，以及最小值、最大值和判断是否有孩子节点。这些内容能够源码。

2.2 拆分节点

当一个节点内有 3 个元素的时候，就要发动拆分货色，拆分的过程分为；

  1. 对 3 个节点的两头节点，插入到父节点上。
  2. 残余 2 个节点创立出新的节点。
  3. 建设父节点和新创建的 2 个节点间关系。

整个操作流程如图所示

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-23-03.png?raw=true" width="480px">

</div>

2.1 插入父节点
private Node_2_3 split(Node_2_3 node, Node_2_3 parent) {if (parent == null) {parent = new Node_2_3(node);
    }
    
    parent.insert(node.getMiddleItem());
    
    Node_2_3[] newNodes = this.triangle(node);
    this.replaceChild(parent, node, newNodes[0], newNodes[1]);
    return parent;
}
  • 整个 2 - 3 树拆分的过程就是在 split 这个办法里，第一步解决了是否有父节点，没有则创立。
  • 之后将原节点的两头值插入到父节点中。接下来的操作就是拆分新节点和更换孩子节点建设新连贯。
2.2 拆分新节点
private Node_2_3[] triangle(Node_2_3 node) {Node_2_3[] newNodes = new Node_2_3[2];
    newNodes[0] = new Node_2_3(node.items[0]);
    newNodes[1] = new Node_2_3(node.items[2]);
    if (!node.isLeaf()) {
        // 左孩子
        newNodes[0].children[0] = node.children[0];
        newNodes[0].children[1] = node.children[1];
        // 右孩子
        newNodes[1].children[0] = node.children[2];
        newNodes[1].children[1] = node.children[3];
    }
    return newNodes;
}
  • 基于传递进来的节点，将节点的左右孩子创立新节点，如果这个孩子节点还有分支节点，则一并更新。
2.3 建设新连贯
private void replaceChild(Node_2_3 parent, Node_2_3 oldChild, Node_2_3 child01, Node_2_3 child02) {if (oldChild == parent.children[0]) {parent.children[3] = parent.children[2];
        parent.children[2] = parent.children[1];
        parent.children[1] = child02;
        parent.children[0] = child01;
    } else if (oldChild == parent.children[1]) {parent.children[3] = parent.children[2];
        parent.children[2] = child02;
        parent.children[1] = child01;
    } else {parent.children[3] = child02;
        parent.children[2] = child01;
    }
}
  • 建设新连贯须要判断这个节点 oldChild 是父节点的左、中、右，之后进行顺次的更换。
  • 如拆分节点的介绍图中，用到的就是 parent.children[1] = child02;parent.children[0] = child01; 两步操作过程。

2.3 新增节点

public void insert(int e) {
    // 记录元素
    elementList.add(e);
    // 插入元素
    if (root == null) {root = new Node_2_3(e);
    } else {root = insert(e, root);
        if (root.number == 3) {root = split(root, null);
        }
    }
}

private Node_2_3 insert(int e, Node_2_3 parent) {if (parent.isLeaf()) {parent.insert(e);
        return parent;
    }
    
    Node_2_3 child = null;
    if (parent.number == 1) {if (e < parent.getMinItem()) {child = insert(e, parent.getLeft());
        } else {child = insert(e, parent.getMiddle());
        }
    } else {if (e < parent.getMinItem()) {child = insert(e, parent.getLeft());
        } else if (e > parent.getMiddleItem()) {child = insert(e, parent.getRight());
        } else {child = insert(e, parent.getMiddle());
        }
    }
    
    if (child.number == 3) {return this.split(child, parent);
    }
    
    return parent;
}
  • 新增节点的过程就比较简单了，一种是应用递归找到能够插入的地位，另外一种就是 where 循环。咱们再 BST、AVL 两种数据结构种都是用了 where 循环。
  • 在 2 - 3 树中 insert 办法递归到对应的插入地位后，开始插入元素。当插入元素完结后判断这个节点是否曾经达到了 3 个节点，如果是则进行拆分。拆分就调用了下面的步骤

3. 2- 3 树结构测试

为了让读者更好的了解 2 - 3 树的构造，小傅哥在程序的控制台打印了插入的过程。网上没有 2 - 3 树在线的动画演示，如果读者看到也能够留言给小傅哥

@Test
public void test_insert_incr() {Tree_2_3 tree = new Tree_2_3();
    for (int i = 1; i <= 10; i++) {tree.insert(i);
        System.out.println(tree);
    }
}
  • 程序插入 10 个节点，如果这是一颗 BST 树，它将会进化成链表。那么咱们应用自均衡的 2 - 3 树，来看看它的插入成果。

测试成果

输出节点(1 个)：1
 
[1]

输出节点(2 个)：1,2
 
[1,2]

输出节点(3 个)：1,2,3
 
 /----- [3]
[2]
 \----- [1]

输出节点(4 个)：1,2,3,4
 
 /----- [3,4]
[2]
 \----- [1]

输出节点(5 个)：1,2,3,4,5
 
 /----- [5]
[2,4]---- [3]
 \----- [1]

输出节点(6 个)：1,2,3,4,5,6
 
 /----- [5,6]
[2,4]---- [3]
 \----- [1]

输出节点(7 个)：1,2,3,4,5,6,7
 
         /----- [7]
 /----- [6]
 |       \----- [5]
[4]
 |       /----- [3]
 \----- [2]
         \----- [1]

输出节点(8 个)：1,2,3,4,5,6,7,8
 
         /----- [7,8]
 /----- [6]
 |       \----- [5]
[4]
 |       /----- [3]
 \----- [2]
         \----- [1]

输出节点(9 个)：1,2,3,4,5,6,7,8,9
 
         /----- [9]
 /----- [6,8]---- [7]
 |       \----- [5]
[4]
 |       /----- [3]
 \----- [2]
         \----- [1]

输出节点(10 个)：1,2,3,4,5,6,7,8,9,10
 
         /----- [9,10]
 /----- [6,8]---- [7]
 |       \----- [5]
[4]
 |       /----- [3]
 \----- [2]
         \----- [1]


Process finished with exit code 0
  • 有了这样的数据结构示意，是不是再来看 2 - 3 树就十分清晰了。—— 我说过，理科生 + 技术，不要只抛实践，要看成果的！货色到手了，能拿捏了，再补充实践。

五、红黑树

红黑树的历史

红黑树（Red Black Tree）是一种自均衡二叉查找树，于 1972 年由 Rudolf Bayer 创造的对称二叉 B 树演变而来，并以 2 -3- 4 树、2- 3 树风行。最终在 1978 年由 Leonidas J. Guibas 和 Robert Sedgewick 从对称二叉 B 树中推导出红黑树。PS：之所以抉择“红色”，是因为它是作者在 Xerox PARC 工作时可用的黑白激光打印机产生的最难看的色彩。

1. 红黑树数据结构

建设在 BST 二叉搜寻树的根底上，AVL、2- 3 树、红黑树都是自均衡二叉树（统称 B - 树）。但相比于 AVL 树，高度均衡所带来的工夫复杂度，红黑树对均衡的管制要宽松一些，红黑树只须要保障彩色节点均衡即可。也正因红黑树在插入和删除时不须要太多的均衡操作，也让它成为；Java 中 HashMap 的元素碰撞后的转换、Linux 的 CFS 进行调度算法、多路复用技术的 Epoll 等各类底层的数据结构实现。

但红黑树并不是一个那么容易了解的知识点，甚至很多材料都只是给出红黑树的实践，但为什么要染色、为什么要左旋、为什么还要左旋接右旋。这样的知识点本就不应该是考死记硬背来学习的，这基本不是学习编程的”套路“。—— 你背的再溜，也没法了解外围实质，忘也只是工夫的问题！

其实依据红黑树的历史来看，最早红黑树就是来自于 2 - 3 树的构造，所以要学习分明的构造就要学习 2- 3 树。但同时对于 2- 3 树的学习也不能只是依附一份实践，否则对于红黑的学习来看，就是用不太了解的 2- 3 树实践套红黑树实践，仍旧没法了解。所以小傅哥在上一章专门解说了 2- 3 树，并做了具体的代码实现。

当初来本章，咱们在来看看红黑树与 2 - 3 树的关系；

红黑树 红黑树 2- 3 树
一棵规范二叉红黑树 红黑树演变（红色节点拉平） 最终复原到 2 - 3 树

红黑树一棵在 2 - 3 树根底上的左倾红黑树，这样就能够把红色节点与对应的父节点拉平，再把两个拉平的节点放到一个节点中。就是咱们相熟的 2 - 3 树了。如果你还没有学习过 2 - 3 树，最好先看下小傅哥的 2 - 3 树，否则你会看的很吃力

当初再来看下红黑树的五条定义；

  1. 每个节点不是红色就是彩色。

    • 彩色决定均衡，红色不决定均衡。这对应了 2 - 3 树中一个节点内能够寄存 1~2 个节点。

  2. 根是彩色的。

    • 这条规定有时会被省略。因为根总是能够从红色变为彩色，但不肯定相同，因而该规定对剖析简直没有影响。

  3. 所有叶子 (NIL) 都是彩色的。

    • 这里指的是红黑树都会有一个空的叶子节点，是红黑树本人的规定。

  4. 如果一个节点是红色的，那么它的两个子节点都是彩色的。

    • 通常这条规定也叫不会有间断的红色节点。这体现在 2 - 3 树中，一个节点最多长期会有 3 个节点，两头是彩色节点，左右是红色节点。2- 3 树中呈现这样的状况后，会进行节点迁徙，两头节点成为父节点，左右节点成为子节点。

  5. 从给定节点到其任何后辈 NIL 节点的每条门路都蕴含雷同数量的彩色节点。

    • 对应 2 - 3 树中，每一层都只是有一个节点奉献了树高决定平衡性，也就是对应红黑树中的彩色节点。

好啦，当初再看这 5 条实践是不就不须要再死记硬背了。因为编程本就是对数学逻辑的具体实现，只有把外围逻辑理顺其实很好了解。接下来小傅哥就带着大家入手实现一下红黑树。

2. 红黑树结构实现

基于 BST 二叉搜寻树的根底上，AVL 树增加了树高作为计算均衡因子的条件，那么红黑树也须要增加一个新的色彩属性，用于解决均衡操作。

public class Node {

    public Class<?> clazz;
    public Integer value;
    public Node parent;
    public Node left;
    public Node right;

    // AVL 树所需属性
    public int height;
    // 红黑树所需属性
    public Color color = Color.RED;
    
}

相比于 AVL 树通过左右旋转均衡树高，红黑树则是在 2 - 3 树的根底上，只对彩色节点保护树高，所以它会应用到染色和左右旋来对树高调衡。染色与左右旋相比，缩小了均衡操作

  • 源码地址：https://github.com/fuzhengwei/java-algorithms
  • 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree
  • 动画演示：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html—— 红黑树首次了解还是比拟艰难的，能够联合学习内容的同时做一些动画演示。

2.1 左倾染色

新增节点 1，相当于 2 - 3 树中在节点 2 上增加了一个节点，这个时候并不影响树高，只须要染色放弃红黑树的规定即可。染色过程如图所示。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-rbt-04.png?raw=true" width="750px">

</div>

Node uncle = grandParent.right;
// 染色
if (uncle.color == Node.Color.RED){
    parent.color = Node.Color.BLACK;
    uncle.color = Node.Color.BLACK;
    grandParent.color = Node.Color.RED;
    current = grandParent;
}
  • 染色时依据以后节点的爷爷节点，找到以后节点的叔叔节点。
  • 再把父节点染黑、叔叔节点染黑，爷爷节点染红。但爷爷节点染红是长期的，当均衡树高操作后会把根节点染黑。具体参考源码

2.2 右倾染色

新增节点 4，相当于 2 - 3 树中在节点 3 上增加了一个节点，这个时候并不影响树高，只须要染色放弃红黑树的规定即可。染色过程如图所示。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-rbt-05.png?raw=true" width="750px">

</div>

Node uncle = grandParent.left;
// 染色
if(uncle.color == Node.Color.RED){
    parent.color = Node.Color.BLACK;
    uncle.color = Node.Color.BLACK;
    grandParent.color = Node.Color.RED;
    current= grandParent;
}
  • 染色时依据以后节点的爷爷节点，找到以后节点的叔叔节点。
  • 再把父节点染黑、叔叔节点染黑，爷爷节点染红。但爷爷节点染红是长期的，当均衡树高操作后会把根节点染黑。具体参考源码

2.3 左旋调衡

2.3.1 一次左旋

对照 2 - 3 树，只有当一个节点内有 3 个节点的时候，才须要调衡。那么红黑树则是判断以后节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是须要抉择进行调衡。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-rbt-06.png?raw=true" width="750px">

</div>

parent.color = Node.Color.BLACK;
grandParent.color = Node.Color.RED;
super.rotateLeft(grandParent);
  • 当你把红黑树对照了解成 2 - 3 树，如图中第 1 步骤下的左侧小图，新增的节点 5 倒置 2 - 3 树不均衡。
  • 那么这个时候须要把 2 - 3 树中节点 4 提起来，而对应红黑树则须要先进行染色，待操作的节点 4 为彩色，两个孩子节点为红色。
  • 最初是把节点 3 进行一次左旋操作，实现树的均衡。对应步骤 3 中的左侧小图是 2 - 3 树调衡后的后果。
2.3.2 右旋 + 左旋

当一次左旋没法调衡，须要右旋 + 左旋的状况，在 AVL 树中有同样的场景。自身树须要左旋操作，但整体分支树节点偏左，此时须要右旋调整树结构再左旋。此处可参考小傅哥编写的 AVL 树

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-rbt-07.png?raw=true" width="750px">

</div>

// 偏左↙，先右旋一次调衡
if (current == parent.left){
    current = parent;
    super.rotateRight(current);
    parent = current.parent;
}
parent.color = Node.Color.BLACK;
grandParent.color = Node.Color.RED;
super.rotateLeft(grandParent);
  • 红黑树新增节点 4 当前，4↙5 构造偏左，须要先进行右旋调衡树结构，再进行左旋。其实这个时候再进行的左旋就和下面一次左旋操作统一了。

4. 右旋调衡

2.4.1 一次右旋

对照 2 - 3 树，只有当一个节点内有 3 个节点的时候，才须要调衡。那么红黑树则是判断以后节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是须要抉择进行调衡。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-rbt-08.png?raw=true" width="750px">

</div>

parent.color = Node.Color.BLACK;
grandParent.color = Node.Color.RED;
super.rotateRight(grandParent);
  • 当你把红黑树对照了解成 2 - 3 树，如图中第 1 步骤下的右侧小图，新增的节点 1 倒置 2 - 3 树不均衡。
  • 那么这个时候须要把 2 - 3 树中节点 2 提起来，而对应红黑树则须要先进行染色，待操作的节点 2 为彩色，两个孩子节点为红色。
  • 最初是把节点 2 进行一次右旋操作，实现树的均衡。对应步骤 3 中的右侧小图是 2 - 3 树调衡后的后果。
2.4.2 左旋 + 右旋

当一次左旋没法调衡，须要左旋 + 右旋的状况，在 AVL 树中有同样的场景。自身树须要右旋操作，但整体分支树节点偏右，此时须要左旋调整树结构再右旋。

<div align=”center”>

<img src="https://bugstack.cn/images/article/algorithm/tree-rbt-09.png?raw=true" width="650px">

</div>

// 偏右↘，先左旋一次调衡
if (current == parent.right){
    current = parent;
    super.rotateLeft(current);
    parent = current.parent;
}
parent.color = Node.Color.BLACK;
grandParent.color = Node.Color.RED;
super.rotateRight(grandParent);
  • 红黑树新增节点 2 当前，1↘2 构造偏右，须要先进行左旋调衡树结构，再进行右旋。其实这个时候再进行的右旋就和下面一次右旋操作统一了。

3. 红黑树实现测试

为了验证红黑树的实现正确与否，这里咱们做一下随机节点的插入，如果它能始终保持平衡，那么它就是一颗牢靠红黑均衡树。

@Test
public void test_binary_search_tree() {Tree tree = new RedBlackTree();
    for (int i = 0; i < 20; i++) {tree.insert(new Random().nextInt(100));
    }
    System.out.println(tree);
}

测试后果

RedBlackTree，输出节点：79,92,36,35,72,22,11,66,98,28,30,39,56,26,1,25,33,80,22,23

                         /----- <NIL>
                 /----- 98(红)
                 |       \----- <NIL>
         /----- 92(黑)
         |       |       /----- <NIL>
         |       \----- 80(红)
         |               \----- <NIL>
 /----- 79(黑)
 |       |               /----- <NIL>
 |       |       /----- 72(黑)
 |       |       |       \----- <NIL>
 |       \----- 66(红)
 |               |               /----- <NIL>
 |               |       /----- 56(红)
 |               |       |       \----- <NIL>
 |               \----- 39(黑)
 |                       \----- <NIL>
36(黑)
 |                       /----- <NIL>
 |               /----- 35(黑)
 |               |       |       /----- <NIL>
 |               |       \----- 33(红)
 |               |               \----- <NIL>
 |       /----- 30(红)
 |       |       |       /----- <NIL>
 |       |       \----- 28(黑)
 |       |               \----- <NIL>
 \----- 26(黑)
         |                       /----- <NIL>
         |               /----- 25(红)
         |               |       \----- <NIL>
         |       /----- 23(黑)
         |       |       |       /----- <NIL>
         |       |       \----- 22(红)
         |       |               \----- <NIL>
         \----- 22(红)
                 |       /----- <NIL>
                 \----- 11(黑)
                         |       /----- <NIL>
                         \----- 1(红)
                                 \----- <NIL>

对照 2 - 3 树结构
                 /----- [98]
         /----- [92]
         |       \----- [80]
 /----- [79]
 |       |       /----- [72]
 |       \----- [66]
 |               \----- [39,56]
[36]
 |               /----- [33,35]
 |       /----- [30]
 |       |       \----- [28]
 \----- [26]
         |       
         |       /----- [25]
         \----- [22,23]----- [22]
                 \----- [1,11]
  • 随机插入 20 个节点，每个节点的程序曾经打印，通过红黑树的染色和左右旋调衡后，二叉构造始终保持树保持平衡，那么验证通过。
  • 另外本文呈现的案例曾经在单元测试中都有编写，读者能够在源码中进行测试。
退出移动版