文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载本文是 CodeGuide 数据结构系列中承上启下的一篇。在掌握 AVL 树左旋、右旋的基础上本文基于小傅哥《倚天村 · 图解数据结构》中 2-3 树 章节配套图片见 算法图片目录从零用 Java 实现一颗 2-3 树讲透 2 节点、3 节点、节点拆分与递归插入的全部细节并顺带梳理删除、索引操作以及它与 红黑树 的演变关系。读完你将能够独立手写 2-3 树为学习红黑树建立扎实的抓手。一、前言不讲红黑树先讲 2-3 树原本的思路是既然 AVL 树 已经讲解了左旋、右旋的操作有了这样的基础就可以直接进入红黑树的讲解——因为它们都是依靠旋转来调衡树高的。但红黑树的五条限定规则来得那么突然没有原因没有道理。这时候大部分资料会用2-3 树来讲解红黑树不过又不去实现一个2-3 树只是用一个理论去套另外一个理论。虽然能从理解上多一些参考但始终感觉没有抓手。对于理科思维来说得拿到实物才行。所以本文先用 Java 实现一个 2-3 树有了基础再学习红黑树。二、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 树的插入过程与 BST 树类似会通过树的左右节点大小找到自己的插入位置。一个节点可以有 1-2 个元素注意不是 1-3 个但当元素个数为 3 时则需要调衡——把三个节点的中间节点晋升上来其余两个节点作为子节点。如果进行一次调衡后上一层父节点达到 3 个元素则需要第 2 次调衡来满足 2-3 树的规则。注意2-3 树的定义是每个节点可以有 1-2 个元素当插入导致节点有 3 个元素时需要立即调衡。例如在插入节点 9 之前的树结构中父节点 6 应该只有一个元素其左子树为节点 5。这样的结构符合 2-3 树的定义也便于后续插入节点 9 时的调衡操作。三、2-3 树结构实现2-3 树的实现并不复杂但在实现前要思考以下几个问题Node 节点属性信息都包括什么插入值是否需要创建新的 Node插入后节点内有 3 个元素后怎么迁移元素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来处理新增元素。这个方法会从数组尾部向前扫描找到正确位置后把比e大的元素依次后移再放入新值类似插入排序的单步操作。另外 2-3 树的节点类还提供了一些方便查询的方法包括获取左边元素、中间元素、右边元素以及最小值、最大值和判断是否有孩子节点isLeaf()等。这些内容可以在源码中查看。2. 拆分节点当一个节点内有 3 个元素的时候就要发起拆分拆分的过程分为对 3 个节点的中间节点插入到父节点上。剩余 2 个节点创建出新的节点。建立父节点和新创建的 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-3 树拆分的过程就是在split这个方法里。第一步解决了是否有父节点的问题当parent null时说明当前拆分的是根节点需要以原节点为基础创建一个新的父节点否则直接复用传入的父节点。之后将原节点的中间值getMiddleItem()插入到父节点中。接下来的操作就是拆分新节点和更换孩子节点、建立新连接。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; }基于传递进来的节点将节点的左右两个孩子即items[0]和items[2]分别创建为新节点。如果这个节点还有分支节点非叶子节点则把原节点对应的 4 个孩子指针一并分配前两个孩子挂到新左节点下后两个孩子挂到新右节点下保持二叉搜索树的大小关系。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这个节点是父节点的左、中、右哪一个孩子然后依次进行更换如果拆分的节点是父节点的第一个孩子需要先把后面的孩子整体后移再插入两个新节点到第 0、1 位如果是第二个孩子则把第 2 位及之后的孩子后移新节点占据第 1、2 位如果是第三个孩子直接把两个新节点放到第 2、3 位即可。如拆分节点的介绍图中所示最典型的场景就是用到的parent.children[1] child02; parent.children[0] child01;两步操作过程。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; }新增节点的过程并不复杂一种是使用递归找到可以插入的位置另外一种是 while 循环在前面的 BST、AVL 两种数据结构中都用到了 while 循环。在 2-3 树中insert方法递归到对应的插入位置叶子节点后开始插入元素当插入元素结束后判断这个节点是否已经达到了 3 个元素如果是则进行拆分——拆分就调用了上面split的完整步骤。这里有一个递归回溯的精妙之处child.number 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 树的两类关键节点形态像[2,4]这种是3 节点含 2 个元素、3 个分支像[2]、[4]这种是2 节点含 1 个元素、2 个分支。插入 3、5、7、9 时分别触发了节点拆分中间元素逐层上移树始终保持着从根到所有叶子节点等高的平衡状态——同样的顺序数据如果插入 BST早就退化成了链表。五、2-3 树的性质总结与延伸1. 结构特点与性质面经手册《看图说话讲解2-3平衡树「红黑树的前身」》docs/md/java/interview/2020-08-16-面经手册 · 第5篇《看图说话讲解2-3平衡树「红黑树的前身」》.md对 2-3 树的性质做了如下总结序号描述12-1 个数据节点、2 个树杈23-2 个数据节点、3 个树杈3三叉与两叉的不同点在于除了两边的节点中间还有一个节点这个节点是介于两个数据之间的值4当随着插入数据会出现临时的节点中有三个元素这时会被调整成二叉树由此归纳出 2-3 树的四条核心性质2-3 树所有叶子节点都在同一层1 个节点可以有 1 到 2 个数据如果有三个数据需要调整树结构1 个节点 1 个数据时则有两个子节点1 个节点 2 个数据时则有三个子节点且中间子节点是介于两个节点间的值。2. 数据删除与索引删除是插入的逆向过程主要分两种情况删除 3-节点包含两个数据元素的节点直接删除即可不会破坏树平衡删除 2-节点此时会破坏树平衡需要将树高缩短或者元素合并恢复树平衡。例如将插入的数据按7、6、5、4、3、2、1顺序删除时删除 7 会导致节点5、6合并并缩短树高删除 63-节点不破坏平衡保持不变删除 5 则需要把根节点 4 下放与 3 合并……整体是一个不断合并、降高的过程。如果不好理解删除可以试想一下这个要删除的节点在插入的时候是一个什么效果删除就是它的逆操作。索引查找则比插入、删除简单得多不需要调整数据结构。基本原则是小于当前节点值左侧寻找大于当前节点值右侧寻找一直到找到索引值停止。由于 2-3 树是平衡的索引的时间复杂度为 O(logn)而链表的索引时间复杂度是 O(n)——这正是使用树结构的根本原因提升插入、删除、查找尤其是索引的整体效率。3. 与红黑树的演变关系在 红黑树 Red Black Tree 章节中红黑树被明确描述为一棵在 2-3 树基础上的左倾红黑树把红色节点与对应的父节点拉平再把两个拉平的节点放到一个节点中就是熟悉的 2-3 树。红黑树的五条定义也可以一一对应到 2-3 树的语义上每个节点不是红色就是黑色黑色决定平衡红色不决定平衡对应 2-3 树中一个节点内可以存放 1~2 个节点如果一个节点是红色的那么它的两个子节点都是黑色的不会有连续红色节点对应 2-3 树中一个节点最多临时会有 3 个节点中间是黑色节点左右是红色节点出现后会进行节点迁移从给定节点到其任何后代 NIL 节点的每条路径都包含相同数量的黑色节点对应 2-3 树中每一层只有一个节点贡献了树高决定平衡性也就是红黑树中的黑色节点。所以理解了 2-3 树的节点拆分与插入调衡红黑树的染色、左旋、右旋就不再是需要死记硬背的规则而是 2-3 树平衡思想在二叉树形态下的自然映射。六、常见面试问题学完本文可以用下面这些问题自测也可以作为面试准备的提纲2-3 树的数据结构如何描述2-3 树一个节点最多可以存放几个元素2-3 树插入节点的时间复杂度是多少2-3 树一个节点有 3 个元素如何迁移需要旋转吗2-3 树你能手写一下吗其中有 3 个元素如何迁移正是本文第三节的核心不需要旋转而是把中间元素上提到父节点、剩余两个元素拆成两个子节点再重建连接关系——这种上提 拆分的调衡方式正是 2-3 树区别于 AVL 树旋转调衡、并演化出红黑树染色与旋转组合操作的关键所在。赞分享文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载相关推荐wvp-GB28181-pro 完整教程把国标摄像头、RTSP 流和多平台视频免费接入一个开箱即用的平台wvp GB28181 pro 完整教程把国标摄像头、RTSP 流和多平台视频免费接入一个开箱即用的平台 想象这样一个场景你接手了一个园区项目现场有海康的后端音视频前端深入理解Java算法库中的树结构AVL、红黑树、B树实战解析深入理解Java算法库中的树结构AVL、红黑树、B树实战解析 在Java算法和数据结构的实现中 树结构 是构建高效存储和检索系统的核心组件。本文将通过Jav开发工具图计算DBAPI深度解析MyBatis风格动态SQL如何实现API自动生成DBAPI深度解析MyBatis风格动态SQL如何实现API自动生成 只需编写SQL1分钟生成生产级API接口 DBAPI作为一款革命性的低代码数据后端低代码API网关上一篇SwinIR智能图像拼接实现无缝融合的终极图像增强方案下一篇零失败指南Prefect多环境配置从开发到生产全流程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 2-3 树深入解析：用 Java 手写红黑树前身，从节点拆分到插入调衡
文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载本文是 CodeGuide 数据结构系列中承上启下的一篇。在掌握 AVL 树左旋、右旋的基础上本文基于小傅哥《倚天村 · 图解数据结构》中 2-3 树 章节配套图片见 算法图片目录从零用 Java 实现一颗 2-3 树讲透 2 节点、3 节点、节点拆分与递归插入的全部细节并顺带梳理删除、索引操作以及它与 红黑树 的演变关系。读完你将能够独立手写 2-3 树为学习红黑树建立扎实的抓手。一、前言不讲红黑树先讲 2-3 树原本的思路是既然 AVL 树 已经讲解了左旋、右旋的操作有了这样的基础就可以直接进入红黑树的讲解——因为它们都是依靠旋转来调衡树高的。但红黑树的五条限定规则来得那么突然没有原因没有道理。这时候大部分资料会用2-3 树来讲解红黑树不过又不去实现一个2-3 树只是用一个理论去套另外一个理论。虽然能从理解上多一些参考但始终感觉没有抓手。对于理科思维来说得拿到实物才行。所以本文先用 Java 实现一个 2-3 树有了基础再学习红黑树。二、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 树的插入过程与 BST 树类似会通过树的左右节点大小找到自己的插入位置。一个节点可以有 1-2 个元素注意不是 1-3 个但当元素个数为 3 时则需要调衡——把三个节点的中间节点晋升上来其余两个节点作为子节点。如果进行一次调衡后上一层父节点达到 3 个元素则需要第 2 次调衡来满足 2-3 树的规则。注意2-3 树的定义是每个节点可以有 1-2 个元素当插入导致节点有 3 个元素时需要立即调衡。例如在插入节点 9 之前的树结构中父节点 6 应该只有一个元素其左子树为节点 5。这样的结构符合 2-3 树的定义也便于后续插入节点 9 时的调衡操作。三、2-3 树结构实现2-3 树的实现并不复杂但在实现前要思考以下几个问题Node 节点属性信息都包括什么插入值是否需要创建新的 Node插入后节点内有 3 个元素后怎么迁移元素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来处理新增元素。这个方法会从数组尾部向前扫描找到正确位置后把比e大的元素依次后移再放入新值类似插入排序的单步操作。另外 2-3 树的节点类还提供了一些方便查询的方法包括获取左边元素、中间元素、右边元素以及最小值、最大值和判断是否有孩子节点isLeaf()等。这些内容可以在源码中查看。2. 拆分节点当一个节点内有 3 个元素的时候就要发起拆分拆分的过程分为对 3 个节点的中间节点插入到父节点上。剩余 2 个节点创建出新的节点。建立父节点和新创建的 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-3 树拆分的过程就是在split这个方法里。第一步解决了是否有父节点的问题当parent null时说明当前拆分的是根节点需要以原节点为基础创建一个新的父节点否则直接复用传入的父节点。之后将原节点的中间值getMiddleItem()插入到父节点中。接下来的操作就是拆分新节点和更换孩子节点、建立新连接。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; }基于传递进来的节点将节点的左右两个孩子即items[0]和items[2]分别创建为新节点。如果这个节点还有分支节点非叶子节点则把原节点对应的 4 个孩子指针一并分配前两个孩子挂到新左节点下后两个孩子挂到新右节点下保持二叉搜索树的大小关系。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这个节点是父节点的左、中、右哪一个孩子然后依次进行更换如果拆分的节点是父节点的第一个孩子需要先把后面的孩子整体后移再插入两个新节点到第 0、1 位如果是第二个孩子则把第 2 位及之后的孩子后移新节点占据第 1、2 位如果是第三个孩子直接把两个新节点放到第 2、3 位即可。如拆分节点的介绍图中所示最典型的场景就是用到的parent.children[1] child02; parent.children[0] child01;两步操作过程。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; }新增节点的过程并不复杂一种是使用递归找到可以插入的位置另外一种是 while 循环在前面的 BST、AVL 两种数据结构中都用到了 while 循环。在 2-3 树中insert方法递归到对应的插入位置叶子节点后开始插入元素当插入元素结束后判断这个节点是否已经达到了 3 个元素如果是则进行拆分——拆分就调用了上面split的完整步骤。这里有一个递归回溯的精妙之处child.number 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 树的两类关键节点形态像[2,4]这种是3 节点含 2 个元素、3 个分支像[2]、[4]这种是2 节点含 1 个元素、2 个分支。插入 3、5、7、9 时分别触发了节点拆分中间元素逐层上移树始终保持着从根到所有叶子节点等高的平衡状态——同样的顺序数据如果插入 BST早就退化成了链表。五、2-3 树的性质总结与延伸1. 结构特点与性质面经手册《看图说话讲解2-3平衡树「红黑树的前身」》docs/md/java/interview/2020-08-16-面经手册 · 第5篇《看图说话讲解2-3平衡树「红黑树的前身」》.md对 2-3 树的性质做了如下总结序号描述12-1 个数据节点、2 个树杈23-2 个数据节点、3 个树杈3三叉与两叉的不同点在于除了两边的节点中间还有一个节点这个节点是介于两个数据之间的值4当随着插入数据会出现临时的节点中有三个元素这时会被调整成二叉树由此归纳出 2-3 树的四条核心性质2-3 树所有叶子节点都在同一层1 个节点可以有 1 到 2 个数据如果有三个数据需要调整树结构1 个节点 1 个数据时则有两个子节点1 个节点 2 个数据时则有三个子节点且中间子节点是介于两个节点间的值。2. 数据删除与索引删除是插入的逆向过程主要分两种情况删除 3-节点包含两个数据元素的节点直接删除即可不会破坏树平衡删除 2-节点此时会破坏树平衡需要将树高缩短或者元素合并恢复树平衡。例如将插入的数据按7、6、5、4、3、2、1顺序删除时删除 7 会导致节点5、6合并并缩短树高删除 63-节点不破坏平衡保持不变删除 5 则需要把根节点 4 下放与 3 合并……整体是一个不断合并、降高的过程。如果不好理解删除可以试想一下这个要删除的节点在插入的时候是一个什么效果删除就是它的逆操作。索引查找则比插入、删除简单得多不需要调整数据结构。基本原则是小于当前节点值左侧寻找大于当前节点值右侧寻找一直到找到索引值停止。由于 2-3 树是平衡的索引的时间复杂度为 O(logn)而链表的索引时间复杂度是 O(n)——这正是使用树结构的根本原因提升插入、删除、查找尤其是索引的整体效率。3. 与红黑树的演变关系在 红黑树 Red Black Tree 章节中红黑树被明确描述为一棵在 2-3 树基础上的左倾红黑树把红色节点与对应的父节点拉平再把两个拉平的节点放到一个节点中就是熟悉的 2-3 树。红黑树的五条定义也可以一一对应到 2-3 树的语义上每个节点不是红色就是黑色黑色决定平衡红色不决定平衡对应 2-3 树中一个节点内可以存放 1~2 个节点如果一个节点是红色的那么它的两个子节点都是黑色的不会有连续红色节点对应 2-3 树中一个节点最多临时会有 3 个节点中间是黑色节点左右是红色节点出现后会进行节点迁移从给定节点到其任何后代 NIL 节点的每条路径都包含相同数量的黑色节点对应 2-3 树中每一层只有一个节点贡献了树高决定平衡性也就是红黑树中的黑色节点。所以理解了 2-3 树的节点拆分与插入调衡红黑树的染色、左旋、右旋就不再是需要死记硬背的规则而是 2-3 树平衡思想在二叉树形态下的自然映射。六、常见面试问题学完本文可以用下面这些问题自测也可以作为面试准备的提纲2-3 树的数据结构如何描述2-3 树一个节点最多可以存放几个元素2-3 树插入节点的时间复杂度是多少2-3 树一个节点有 3 个元素如何迁移需要旋转吗2-3 树你能手写一下吗其中有 3 个元素如何迁移正是本文第三节的核心不需要旋转而是把中间元素上提到父节点、剩余两个元素拆成两个子节点再重建连接关系——这种上提 拆分的调衡方式正是 2-3 树区别于 AVL 树旋转调衡、并演化出红黑树染色与旋转组合操作的关键所在。赞分享文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载相关推荐wvp-GB28181-pro 完整教程把国标摄像头、RTSP 流和多平台视频免费接入一个开箱即用的平台wvp GB28181 pro 完整教程把国标摄像头、RTSP 流和多平台视频免费接入一个开箱即用的平台 想象这样一个场景你接手了一个园区项目现场有海康的后端音视频前端深入理解Java算法库中的树结构AVL、红黑树、B树实战解析深入理解Java算法库中的树结构AVL、红黑树、B树实战解析 在Java算法和数据结构的实现中 树结构 是构建高效存储和检索系统的核心组件。本文将通过Jav开发工具图计算DBAPI深度解析MyBatis风格动态SQL如何实现API自动生成DBAPI深度解析MyBatis风格动态SQL如何实现API自动生成 只需编写SQL1分钟生成生产级API接口 DBAPI作为一款革命性的低代码数据后端低代码API网关上一篇SwinIR智能图像拼接实现无缝融合的终极图像增强方案下一篇零失败指南Prefect多环境配置从开发到生产全流程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考