<返回更多

面试让我手写红黑树

2022-10-10    小傅哥
加入收藏

作者：小傅哥
博客：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）那么说的都是一个东西。


 

 

 

二叉搜索树在日常开发中使用的场景还是比较多的，例如基于组合模式实现的规则引擎，它就是一颗二叉搜索树。但类似这样的开发中用到的二叉树场景，都是基于配置生成，所以组合出来的节点也更加方便控制树高和平衡性。这与 JAVA API HashMap 中的红黑树这样为了解决插入节点后仍保持树的平衡性是有所不同的。

所以二叉搜索树也是一颗没有经过调衡的基础性数据结构，在一定概率上它完成有可能退化成链表，也就是从近似O(logn)的时间复杂度退化到O(n)。关于二叉搜索树的平衡解决方案，包括；AVL树、2-3树、红黑树等，小傅哥会在后续的章节继续实现。

2. 二叉搜索树结构实现

二叉搜索树是整个树结构中最基本的树，同时也是树这个体系中实现起来最容易的数据结构。但之所以要使用基于二叉搜索树之上的其他树结构，主要是因为使用数据结构就是对数据的存放和读取。那么为了提高吞吐效率，则需要尽可能的平衡元素的排序，体现在树上则需要进行一些列操作，所以会有不同的结构树实现。

而实现二叉搜索树是最好的基础学习，了解基本的数据结构后才更容易扩展学习其他树结构。

2.1 树枝定义 public Integer value; public Node parent; public Node left; public Node right; 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; } 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 删除单节点

 


 

 

2.4.2 删除双节点

 


 

 

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

三、AVL 树

 

AVL树历史

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

1. AVL树数据结构

AVL 自平衡二叉树的出现，其目的在于解决二叉搜索树退化成链表的问题。当我们向BST二叉搜索树顺序存入1、2、3、4、5、6、7个元素时，它会退化成一条链表，因而失去树查询的时间复杂度，所以我们需要AVL树平衡树高。如图所示


 

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

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

左旋（新增节点6） 右旋（新增节点1） 左旋+右旋（新增节点4） 右旋+左旋（新增节点3）


 


 


 


 

条件：节点4，平衡因子为-2，左旋 条件：节点3，平衡因子为2，右旋 条件：节点3，平衡因子为2，右旋。但当节点2平衡因子-1先左旋。 条件：节点2，平衡因子为-2，左旋。但当节点5平衡因子1先右旋。

 

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树的左旋、右旋、左旋+右旋、右旋+左旋的代码操作。不要担心这没有多复杂，只要你能搞清楚左旋，就能搞清楚右旋。两旋弄懂组合就没啥难度了。

 

2.1 左旋

 

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


 

代码实现

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 右旋

 

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


 

代码实现

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 左旋 + 右旋

 

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


 

代码实现

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 右旋 + 左旋

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


 

代码实现

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

四、2-3树

 

这时候大部分资料会用2-3树来讲解红黑树，不过又不去实现一个2-3树，只是用了一个理论套另外一个理论。虽然能从理解上多一些参考，但始终感觉没有抓手呀。对于理科思维来说，你得给我东西呀。老是整这悬得楞的谁能受了。所以这里我们先来用Java实现一个2-3树，有了基础再学习红黑树

1. 2-3树数据结构

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


 

这里要提到一点，在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树的调衡处理。


 

 

 

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

 

2. 2-3树结构实现

 

2-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.2 拆分节点

 

当一个节点内有3个元素的时候，就要发起拆分东西，拆分的过程分为；

 

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

 

整个操作流程如图所示


 

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.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; } } 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; } 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); } }

 

测试效果

输入节点(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

五、红黑树

 

红黑树的历史

红黑树（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树的基础上，只对黑色节点维护树高，所以它会使用到染色和左右旋来对树高调衡。染色与左右旋相比，减少了平衡操作

 

2.1 左倾染色

 

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


 

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上添加了一个节点，这个时候并不影响树高，只需要染色保持红黑树的规则即可。染色过程如图所示。


 

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个节点的时候，才需要调衡。那么红黑树则是判断当前节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是需要选择进行调衡。


 

parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateLeft(grandParent);

2.3.2 右旋 + 左旋

 

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


 

// 偏左↙，先右旋一次调衡 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. 右旋调衡 2.4.1 一次右旋

 

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


 

parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateRight(grandParent);

2.4.2 左旋 + 右旋

 

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


 

// 偏右↘，先左旋一次调衡 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);

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 /----- /----- 98(红) | ----- /----- 92(黑) | | /----- | ----- 80(红) | ----- /----- 79(黑) | | /----- | | /----- 72(黑) | | | ----- | ----- 66(红) | | /----- | | /----- 56(红) | | | ----- | ----- 39(黑) | ----- 36(黑) | /----- | /----- 35(黑) | | | /----- | | ----- 33(红) | | ----- | /----- 30(红) | | | /----- | | ----- 28(黑) | | ----- ----- 26(黑) | /----- | /----- 25(红) | | ----- | /----- 23(黑) | | | /----- | | ----- 22(红) | | ----- ----- 22(红) | /----- ----- 11(黑) | /----- ----- 1(红) ----- 对照2-3树结构 /----- [98] /----- [92] | ----- [80] /----- [79] | | /----- [72] | ----- [66] | ----- [39,56] [36] | /----- [33,35] | /----- [30] | | ----- [28] ----- [26] | | /----- [25] ----- [22,23]----- [22] ----- [1,11]

声明：本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系，我们将立即删除或处理。
▍相关推荐
更多资讯 >>>
Copyright @ 简易百科 V 2.0 京ICP备14042104号