代码之家 › 专栏 › 技术社区 › tony19 RuNpiXelruN

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

2-3-4-tree algorithm

tony19 RuNpiXelruN · 技术社区 · 12 年前

在所描绘的 2-3-4 tree 以下(来自 Data Structures & Algorithm in Java, 2nd ed ),为什么插入 99 导致的节点拆分 83/92/104 当它看起来像 99 可以插入到正确的孩子( C 孩子,之后立即进入现场 97 )而不进行任何拆分?

enter image description here

2 回复 | 直到 12 年前

xan 12 年前

在C中插入99是可以的,因为它可以保持所有的不变量,但如果插入总是在向下扩展4个节点,那么算法通常会更简单。然后,总会有空间进行任何必要的提升和旋转。比较C本身已经是4节点的情况可能会有所帮助。

Markus Mikkolainen 12 年前

保持树的平衡,保证性能。插入是递归的,它会碰到一个4节点(具有3个值和4个子节点),这将导致进行拆分。

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前