为什么节点在插入2-3-4树时会分裂？

节点在插入2-3-4树时会分裂是因为2-3-4树是一种自平衡的二叉搜索树，它的特点是每个节点最多只能有4个子节点，分别是左上、左下、右上、右下。当向2-3-4树中插入一个新节点时，如果该节点的父节点已经有4个子节点，那么就需要进行分裂操作。

分裂操作的过程如下：

将父节点的中间子节点提升为新的节点，并将原父节点的中间子节点删除。
将原父节点的左上子节点作为新节点的左子节点，将原父节点的右上子节点作为新节点的右子节点。
将原父节点的左下子节点和右下子节点分别作为新节点的左子节点和右子节点的子节点。
如果新节点的父节点也已经有4个子节点，则递归地进行分裂操作。

通过这种方式，2-3-4树可以保持平衡，从而确保树的高度始终保持在O(log n)的范围内，这有助于提高树的搜索性能。

推荐的腾讯云相关产品：腾讯云的云数据库（TencentDB）提供了多种数据库服务，包括关系型数据库、非关系型数据库和时序数据库等，可以满足不同场景下的数据存储需求。

产品介绍链接地址：腾讯云云数据库

相关·内容

Java数据结构和算法（十二）——2-3-4树

②、如果往下寻找插入位置的途中，节点已经满了，那么插入就变得复杂了。发生这种情况时，节点必须分裂，分裂能保证2-3-4树的平衡。　　...ps：这里讨论的是自顶向下的2-3-4树，因为是在向下找到插入点的路途中节点发生了分裂。...如果直接插入该节点，那么还要进行子节点的增加，因为在2-3-4树中节点的子节点个数要比数据项多1；如果插入的节点满了，那么就要进行节点分裂。...②、操作等价　　不仅红-黑树的结构与2-3-4树对应，而且两种树操作也一样。2-3-4树用节点分裂保持平衡，红-黑树用颜色变换和旋转保持平衡。 ? 　　上图是4-节点分裂。...颜色变换之后，40,60节点都为黑色的，50节点是红色的。因此，节点 50 和它的父节点70 对于3-节点，如上图虚线所示。 6、2-3-4 树的效率　　分析2-3-4树我们可以和红黑树作比较分析。

1.2K7 0

了解红黑树的起源，理解红黑树的本质

2-3树，插入元素后自平衡的过程相对于AVL树就要简单得多了，比如，上面这颗树，再插入一个元素K，它会先找到I J这个节点，插入元素K，形成临时节点I J K，不符合2-3树的规则，所以分裂，J往上移，...2-3-4树 2-3-4树，它的每个非叶子节点，要么是2节点，要么是3节点，要么是4节点，且可以自平衡，所以称作2-3-4树。...当然，2-3-4树插入元素的过程也很好理解，比如，上面这颗树，插入元素M，找到K L这个节点，插入即可，形成4节点，满足规则，不需要自平衡： ? 再插入元素N呢？...同样地，在2-3-4树自平衡的过程中出现了临时的5节点，所以，如果允许5节点的存在呢？嗯，2-3-4-5树由此诞生！...那么，为什么要再造一个红黑树呢？直接用2-3-4树它不香么？

1.4K3 0

掌握了2-3-4树也就掌握了红黑树，不信进来看看，建议收藏！

下图是一个典型的 2-3-4树 ? 2 生成的过程接下来我们通过演示来看看2-3-4树生成的过程第一次插入—2节点 ? 插入第二个节点–3节点合并 ?...插入第三个节点—4节点合并 ? 插入第4个节点—需要分裂 ? 插入6 ? 插入7 ? 插入8 ? 插入9 ? 插入10 ? 插入11 ?...插入12 ? 最后我们插入1来看看效果 ? 到这儿相信大家对于2-3-4树应该有了个直观的认知了。 3 和红黑树的等价关系红黑树起源于2-3-4树，它的本质就是2-3-4树。...3.1 2节点一个2节点对应的红黑树节点就是一个黑色节点 ? 3.2 3节点一个三节点可以有两种情况的红黑树节点，一种是右倾，一种是左倾，所以一个2-3-4树可以有多个红黑树 ?...原则：上黑下红 3.3 4节点一个四节点转换的情况只有一种，中间节点黑色，左右节点红色 ? 3.4 裂变状态还有就是在2-3-4树中存在的裂变状态。

3431 0

敖丙带你杀死面试梦魇-红黑树【图解】

算法4中给出的红黑树是基于2-3树实现，而且这种实现的红黑树十分特殊，它要求概念模型中的3节点在红黑树中必须用左倾的红色节点来表示。...首先，算法4中的红黑树基于2-3树概念模型，不用考虑2-3-4树中复杂的4节点分裂；第二，算法4中的红黑树是左倾红黑树，进一步降低了调平的难度；第三，算法导论中对于红黑树删除场景的阐述并不够具体，许多关键环节都用...然后，我们对可能生成的临时4节点进行分裂处理，使得临时4节点消失。 ? 如果需要在2-3-4树中向4节点内插入元素，那么会引发如下图所示的分裂过程 ?...2-3-4树的插入事实上，这正对应了红黑树在插入的时候一定会把待插入节点涂成红色，因为红色节点的意义是与父节点进行关联，形成概念模型2-3树中的3节点或者临时4节点。...如果细心的话，你可以回想一下本文是按照怎样的顺序介绍左倾红黑树的插入的，为什么是这样的顺序？

1.1K3 1

三分钟基础：什么是 2-3-4 树

5）插入如果 2-3-4 树中已存在当前插入的 key ，则插入失败，否则最终一定是在叶子节点中进行插入操作，因为查找过程的结束位置在叶子节点。...5.2 4- 节点插入如果待插入的节点是个 4- 节点，那么应该先分裂该节点然后再插入。...一个 4- 节点可以分裂成一个根节点和两个子节点（这三个节点各含一个 key ）然后在子节点中插入，我们把分裂形成的根节点中的 key 看成向上层插入的 key ，然后重复 5.1 和 5.2 。...5.3 根节点分裂如果是在 4 节点中进行插入，每次插入会多出一个分支，如果插入操作导致根节点分裂，则 2-3-4 树会生长一层。图解： ? ? ? ? ? ?...7）结语本篇文章主要介绍了 2-3-4 树的性质，以及插入删除等操作。介绍 2-3-4 树的目的主要是为了为后续学习红黑树和B- 树打下一个基础。

7081 0

数据结构与算法——2-3-4树

1.3K2 0

左倾红黑树、右倾红黑树、AA树，你不知道的还有很多！

再忆2-3-4树我们给出一张图简单地回顾一下上一节关于2-3-4树插入元素N的过程： ? 关注公众号彤哥读源码，查看上一节的内容。...所以，你看，结合2-3-4树来理解红黑树是不是就特别简单了，对于2-3-4树就是一个普通的3节点，而对于红黑树相当于插入一个右子节点，再做一次左旋变色即可。...插入元素G，对于2-3-4树，只是形成一个普通的4节点，而对于红黑树，需要先以F左旋，变成与情况（1）相同的状态，再以G右旋，然后变色，最终再平衡成红黑树。...好了，通过上面的分析，连续插入三个元素，可以看到，对于2-3-4，都是形成一个4节点，而对于红黑树，最终都变成了下面这个样子： ? 所以，我们再插入第四个元素看看。...好了，插入四个元素的各种情况到此结束，可以看到，插入第四个元素时，对于2-3-4树，会形成一个5节点，然后再分裂，而对于红黑树，要经过一系列的左旋、右旋、变色，最终转变成跟2-3-4树对应的形态，是不是很好玩儿

2.8K4 3

面经手册 · 第6篇《带着面试题学习红黑树操作原理，解析什么时候染色、怎么进行旋转、与2-3树有什么关联》

❞ 目录一、前言二、面试题三、2-3树与红黑树的等价性 1. 为什么既有2-3树要有红黑树 2. 简单2-3树转红黑树 3. 复杂2-3树转红黑树四、红黑树 1. 平衡操作 2....为什么既有2-3树要有红黑树首先2-3树(读法：二三树)就是一个节点有1个或者2个元素，而实际上2-3树转红黑树是由概念模型2-3-4树转换而来的。...平衡操作通过在上一章节2-3树的学习，在插入节点时并不会插到空位置，而是与现有节点融合以及调整，保持整个树的平衡。...而红黑树是2-3-4树的一种概念模型转换而来，在插入节点时通过红色链接相连，也就是插入红色节点。插入完成后进行调整，以保持树接近平衡。...五、总结从2-3树到解释2-3-4树概念推导出红黑树，从元素的在2-3树中的插入删除对照到红黑树中保持平衡操作，从原理解析到各项情况实际操作等，以及把绝大部分红黑树内容全部介绍完成。

8912 1

什么是2-3树

，还可以降低树的高度，从而让搜索，插入，删除的性能有所提升，但与此对应的是程序的编码会变得更加复杂，这也是2-3树或者2-3-4树，在开源框架或日常开发中并不如AVL树和红黑树使用频繁的原因，但B+树除外...2-3树的插入为了保持平衡性，2-3树的插入如果破坏了平衡性，那么树本身会产生分裂和合并，然后调整结构以维持平衡性，这一点和AVL树为了保持平衡而产生的节点旋转的作用一样，2-3树的插入分裂有几种情况如下...：（1）情况一：叶子节点的插入调整，规律是叶子的中间值上升，然后左右值分裂，如下图： ?...关于2-3-4树 2-3-4树与2-3树类似，只不过当父节点的值是3的时候，节点的孩子个数可以有4个，如下： ?...2-3-4树可以再次降低的树的高度，但是对应的编码会更加复杂，尤其是在插入和删除之后，所以常常会被容易实现和理解的红黑树代替，这里不再过多介绍。感兴趣的朋友可以自行查询资料学习。

1.8K2 0

红黑树硬核讲解

2-3-4节点 2.2 查找要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。...插入4 插入总结：先找插入结点，若结点是2结点，则直接插入。如结点3结点，则插入使其临时容纳这个元素，然后分裂此结点，把中间元素移到其父结点中。对父结点亦如此处理。...（中键一直往上移，直到找到空位，在此过程中没有空位就先搞个临时的，再分裂。） 2-3树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。...在算法导论中红黑树树基于2-3-4树实现的。在算法4中红黑树树基于2-3树实现的，并且要求3节点在红黑树中必须以左倾红色节点来表示。 2-3树肯定比2-3-4树简单，所以接下来主要基于2-3树说。...不会有连续的红色节点：2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点。

4623 0

数据结构之2-3-4树

2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构，可以在O(lgn)的时间内查找、插入和删除，这里的n是树中元素的数目。...2-3-4树和红黑树是等价的，也就是每个红黑树都可以转化为一颗2-3-4树，每个选择操作也和2-3-4树中的分裂操作对应。 ...2-3-4树是这样一种数据结构，满足如下性质: 1) 每个节点每个节点有1、2或3个key，分别称为2-node，3-node，4-node。 ...要证明2-3-4上面的出入算法一定形成一个平衡树，即从root开始往下到任一个叶子的长度都是相等。用数学归纳法： 1. 只有一个节点的树当然是平衡的 2....假设插入了n个元素，树还是平衡的，现在插入一个新元素，要证明不会破坏平衡性：算法会改变tree的是1.1, 1.2, 3.1, 3.2。

4199 0

3分钟速读原著《Java数据结构与算法》(四)

2.2-3-4树转变为红-黑树 2.1 把2-3-4树中的每个2-节点转化成为红-黑树的黑色节点 2.2 把每个3-节点转化成一个子节点和一个父节点,哪个节点变成了子节点或者父节点都无所谓,子节点涂成红色...,父节点涂成黑色 3.小结 3.1 多叉树比二叉树又更多的管家in自和子节点 3.2 2-3-4树是多叉树,每个节点最多有三个关键字和4个子节点 3.3 多叉树中,节点中数据项按照关键字升序排列 3.4...分裂根需要创建两个新节点,分裂出另一个节点,创建出一个新的节点 3.5 只有分裂根时2-3-4树的高度才会增长 3.6 2-3-4树和红黑树之间存在一对一的对应关系 3.7 2-3-4树当中分裂节点和在红黑树中进行颜色变幻时一样的...3.8 2-3-4树的高度是log2N 3.9 查找的时间和高度成正比 3.10 2-3-4树很浪费空间,因为很多节点还不满一半 3.11 外部储存的意思是在主存外面保存数据,通常是在磁盘上 3.12...由树来进行实现优先级的插入和删除的时间复杂度都是O(logN),尽管这样删除的时间变慢了一些,但是插入时间快得多了备注:这里的堆并不是Java或者C++党章的堆,后者是程序员用new 能得到哦的计算机内存的可用部分

3741 0

一篇文章搞懂红黑树的原理及实现2-3-4 Tree(2-3-4树)红黑树左倾红黑树的删除操作删除红黑树最小节点删除任意节点总结

image.png 2-3-4的插入（Insertion in a 2-3-4 Tree） 2-3-4的插入有几种情况，下面我们会一一的讨论。...image.png 我们看一下如何从空开始插入建立一个2-3-4树下面，我们通过动态添加一个完整的2-3-4的过程，说明2-3-4树的插入和构建过程 ? image.png ?...亿的节点，2-3-4树的高度会在15~30之间由此来看，2-3-4树的效率比平衡二叉树要好，但是问题在于，2-3-4树并不好实现首先，我们需要用三种不同类型的节点代表2-3-4node 然后，在插入节点的时候...image.png 我们可以看到这种情况对应于2-3-4树就是想2-node插入变成3-node 下面一种情况，就是我们向3-node插入一个节点，那么我们就需要将它变成2-3-4树中对应的树节点这也是为什么我们之前定义的不允许的情况中的第二种...image.png 总结至此，我们就基本讲完了红黑树的基本原理和实现。我们首先从2-3-4树开始讲起，然后引出红黑树其实就是2-3-4树的BST的表示。接着介绍插入和删除算法。

4.2K3 1

数据结构与算法（十一）B树

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现 •1个节点可以存储超过2个元素、可以拥有超过2个子节点•拥有二叉搜索树的一些特质（小的子节点在左面大的子节点在右面）•平衡，每个节点的所有子树高度一致...•如果要是m = 4•他的子节点个数为2 <= y <= 4，因此可称为（2，4）树、2-3-4树。...（最多添加两个）叫上溢假设B树的阶级为m，上溢节点最中间的节点为k •上溢的节点元素必然等于m 解决上溢 •将k位置的元素向上与父节点合并•将[0,k - 1]和[k + 1,m - 1]位置的元素分裂成两个子节点...•这两个子节点的元素个数，必然都不会低于最低限制（ceiling(m/2) - 1）•一次分裂完毕后，可能导致父节点上溢，重复上述方法•最极端的情况是，一直上溢到根节点。...(m/2) - 1 个•如果下溢的节点的临近兄弟节点至少有(ceiling(m/2))个元素，可以向其借一个元素（最后一个元素）•将父节点最后一个元素插入到下节点的最小位置•将借来的元素插入到父节点最小位置

4693 0

树（8）

（2）后面我们讲解的2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。...（2）树度：所有节点里面，节点度最大的为树度。 2-3树除了2-3树，还有2-3-4树等。概念和2-3树类似，也是一种B树。...1.B树介绍前面以及介绍了2-3树和2-3-4树，他们就是B树（B-Tree也写成B-树），这里我们在做一个说明，我们在学习Mysql时，经常听说某种数据类型的索引是基于B树或者B+树的，如图：说明...比如2-3树的阶是3，2-3-4树的阶是4. （2）B-树的搜索，从根节点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子节点；重复，直到所对应的子指针为空...第一个箭头指向的5是索引并不是数据，而真正的数据5节点是通过下面路径找到的。（4）非叶子节点相当于是叶子节点的索引（稀疏索引），叶子系欸DNA相当于是存储（关键字）数据的数据层。

1871 0

一波动图探究红黑树的本质

创建 2-3 树的规则插入操作如下：向 2-节点中插入元素： ? 向一颗只含有一个 3-节点的树中插入元素： ? 2-3-4 树含义如下： **2 节点：**包含两个子节点和一个数据元素。...**规则 2：**四节点可以被分解三个 2-节点组成的树，并且分解后新树的根节点需要向上和父节点融合。插入操作原本的 2-3-4 树，如下图： ?...对于上图的 2-3-4 树，插入一个节点 17，由于规则 1，节点 17 不会加入节点 [16,18,20] 的子树，而是与该节点融合。 ?...总结了下插入节点的过程，无非也就为了符合两条规则，那么，2-3 树，2-3-4 树都有了，那是不是也有 2-3-4-5 树，2-3-4-5--...-n 树的存在呢？...**原因：**红黑树这些黑色节点在 2-3-4 树中代表的是由 1 节点的一个 2-3-4 树，而 2-3-4 树是同一个子树的深度是相同的，平衡的，所以从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

3991 0

动图演示：如何彻底理解红黑树？

创建 2-3 树的规则插入操作如下：向 2-节点中插入元素： ? 向一颗只含有一个 3-节点的树中插入元素： ? 2-3-4 树含义如下： 2 节点：包含两个子节点和一个数据元素。...规则 2：四节点可以被分解三个 2-节点组成的树，并且分解后新树的根节点需要向上和父节点融合。插入操作原本的 2-3-4 树，如下图： ?...对于上图的 2-3-4 树，插入一个节点 17，由于规则 1，节点 17 不会加入节点 [16,18,20] 的子树，而是与该节点融合。 ?...总结了下插入节点的过程，无非也就为了符合两条规则，那么，2-3 树，2-3-4 树都有了，那是不是也有 2-3-4-5 树，2-3-4-5--...-n 树的存在呢？...原因：红黑树这些黑色节点在 2-3-4 树中代表的是由 1 节点的一个 2-3-4 树，而 2-3-4 树是同一个子树的深度是相同的，平衡的，所以从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

3754 0

动图展示，让你彻底理解红黑树！

5585 0

B树、B+树、B*树——简单介绍

IDEA 注册码，2020.2 IDEA 激活码一、为什么是有B树 ---- 二叉树存在的问题：二叉树的构建是在内存中执行的，需要将磁盘中的文件通过 IO操作进行读取。...如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树；【2】2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。如下图就是一个2-3树； ?...； ■ 有三个子节点的叫三节点，三节点要么没有子节点，要么有三个子节点； ■ 2-3 树是由二节点和三节点构成的树； ■ 当按照规则插入一个数到某个节点时，不能满足上述要求时，就需要拆分...拆后仍需要满足上述条件； ■ 对于三节点的子树的值的大小仍然遵循（BST：二叉排序树）的规则； 2-3 树的插入和删除节点案例：链接 B-Tree树即B（Balanced：平衡）树，有人将B-Tree...三、B树、B+树、B*树 ---- 【1】B树介绍：前面介绍的2-3、2-3-4树就是 B树，在 MySql 中经常听说某种索引是基于 B树、B+树的，如下图： ?

1.2K2 0

通过2-3-4树理解红黑树

从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。下图就是一个典型的红黑树： ? 但实现上我省略了其中的 Nil 结点，一般如下图，大家理解时也可以忽略它们。 ?...对应红黑树至于为什么说红黑树是 2-3-4树的一种等同呢，这是因为 2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵 2-3-4树也都对应一棵红黑树，下图是 2-3-4树不同结点与红黑树子树的对应...红黑树和 2-3-4树的结点添加和删除都有一个基本规则：避免子树高度变化，因为无论是 2-3-4树还是红黑树，一旦子树高度有变动，势必会影响其他子树进行调整，所以我们在插入和删除结点时尽量通过子树内部调整来达到平衡...下面来对照着 2-3-4树说一下红黑树结点的添加和删除： ---- 结点插入 2-3-4树中结点添加需要遵守以下规则：插入都是向最下面一层插入；升元：将插入结点由 2-结点升级成 3-结点，或由 3...---- 删除结点红黑树的删除要比插入要复杂一些，我们还是类比 2-3-4树来讲：查找最近的叶子结点中的元素替代被删除元素，删除替代元素后，从替代元素所处叶子结点开始处理；降元：4-结点变 3-结点

1.5K8 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云