问题标签 [2-3-4-tree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 删除 2-3-4 树中的内部节点
我想从下面的 2-3-4 树中删除 15。我想简单地将 17 向上移动，但我不知道这是否正确，因为它必须是完整的。
从以下树中删除 15：
删除后的 2-3-4 树会是什么样子？我认为在这种情况下简单地向上移动 17 是不正确的。但我不太确定。
graph - BST 和 2-3-4 树高
我有以下问题：
假设 T1 是一棵二叉搜索树，T2 是一棵 2-3-4 树，它们都是由相同数量的键 S 形成的。设 H1 为 T1 的高度，H2 为 T2 的高度。
一世。简述为什么任何 S 的 H1 小于或等于 H2
ii. 描述 H1 等于 H2 时 T1 和 T2 的性质
但我不明白，不是反过来吗？二分查找的高度不是大于2-3-4树的高度吗？例如，如果我有以下键序列：1,2,3,4,5,6,7,9,10 并且我构造了树：
二叉搜索树：
2-3-4 树：
下面这个例子不是 H1=3 和 H2=2 并且 H1 不小于 H2
data-structures - 2-3-4 从数字列表生成树
我有数字 50,40,60,30,70 的列表。假设我想将这些插入到空的 2-3-4 树中。这些数字中的哪一个将是树的父根，为什么？是广告单吗，数字有多大？当我给出数字列表时，我希望能够绘制 234Tree。我似乎不能这样做，因为我不知道从哪一个作为父根开始。简单地说，是什么因素指定了这棵树的父根。
java - 将 2-3-4 树转换为红黑树
我正在尝试将 2-3-4 树转换为 Java 中的红黑树，但无法弄清楚。
我编写了这两个基本类如下，以使问题简单明了，但无法弄清楚从这里去哪里。
我假设 2-3-4 树是有效的，并且希望在调用该方法时返回一棵红黑树。
我也尝试过以下代码，但没有成功：
等为 keys.size() == 2, 1....
我知道它在理论上必须是递归的，但是很难弄清楚。有什么想法吗？
data-structures - 在 2,3,4 树中，您是否仅在叶节点中插入第三个元素？
- 假设我将 3 个元素输入到自上而下的 2、3、4 树中。这三个元素都会进入根目录吗？
- 对于后续插入，只有当它是叶节点时才会将第 3 个元素插入节点（或者当您遇到 3 个键节点时，当键启动时插入节点）
java - 2-3-4 树什么时候不会有相同的结构？
我刚刚在我正在使用的数据结构教科书中看到这个问题被问到了，问题就出来了
举一个例子来说明以下声明是错误的：“存储一组条目的 2-3-4 树将始终具有相同的结构，无论条目插入的顺序如何。”
我知道最好的情况是 O(log n)，它比使用 BST 更好，但仅此而已，我似乎找不到合理的解释。如何证明这种说法是错误的？
algorithm - 插入2-3-4树时如何拆分节点？
是否有关于如何在 2-3-4 树中拆分节点的规则？
例如，如果我将 3、7、4、9 插入到 2-3-4 树中：
它会像这样（黄色）还是那样（绿色）被拆分，如下所示：
两者都有效吗？
python - 2-3-4 树的分析和复杂性
我被要求以自上而下和自下而上的方法从一系列元素构建一棵 2-3-4 树。我能够做到这一点，因为它非常直截了当。
接下来，我被要求分析算法的运行时间，并找出问题的复杂性，即从给定的元素序列构建 2-3-4 树的速度有多快？这是让我感到困惑的地方，到目前为止，我理解复杂度为 O(logn)，因为该算法不需要遍历整个树来插入新元素。但是，我该如何分析算法的运行时间呢？我一直认为运行时间和复杂性是一回事。
java - 234-树插入方法问题
我在添加值时遇到问题，这些值会在我的 234 树中创建超出第一级的新级别。我的方法在根对象上创建子对象，但无法为任何其他节点创建子对象。我能够创建和插入给定数量的数据对象，只要它们不填充导致它创建子节点的节点......我已经认真梳理了好几天。
我的问题基本上是基于我的代码。我的方法（特别是插入方法）是否允许在根目录下创建子节点？
树类
通常我只会发布我要查询的特定代码。但是，此特定方法也跳到其他两个类中。所以我认为看看我如何设置它们会有所帮助。
节点类
我现在将所有内容都设置为公开，因为我只是在测试代码的结构。
数据项类
这是我将 DataItem 对象添加到树的方法。
输出
树“似乎”可以工作，但是添加超过 10 个名称开始使其不稳定。它根本无法处理 15 个或更多。
输出 15 或更多
我对算法还是很陌生，所以我可能完全错过了一些简单的东西。我开始认为插入方法很好，但我可能没有正确拆分。这就是为什么我现在可以插入到第 2 级而不是更远的原因。感谢您提供的任何见解。
data-structures - 红黑与 2-3-4 树的实际性能，特别是考虑缓存性能？
2-3-4 树的单个节点可以用 8 个指针构造：指向最多四个子节点的指针，指向最多 3 个实际记录的指针，这些记录包含与搜索键匹配或将确定 4 个子节点中的哪一个的键递归到，和一个父节点指针。
今天常见的硬件有 8 字节的指针，给出一个 64 字节的节点。此外，现代 CPU 具有 64 字节的高速缓存行。如果节点与缓存线对齐，那么每个节点只需要一个缓存线命中：在引用七个指针中的第一个之后，其余的都将在您的 L1 缓存中。
虽然红黑树实现起来要简单得多，而且小代码应该是快速代码，但树中的每一级下降都有 L1 缓存未命中的风险。对于 1023 个对象，2-3-4 树需要 5 个节点的最坏情况才能加载到缓存中。完美平衡的二叉树需要 10，但由于不平衡，红黑可能需要更多（不确定最坏的情况：20？）
简单地敲击一个数据结构的小型测试工具可能会将其全部保存在缓存中，因此可能会报告红黑树与 2-3-4 的性能相似。但我有一种感觉，一个复杂的现实世界的应用程序可能会看到更少的挂钟时间和更低的延迟与 2-3-4 树。
对此是否有任何共识或研究？