问题标签 [2-3-4-tree]

我现在正在学习数据结构课程，我们学习了 2-3-4 树和展开树。我想知道在什么情况下你会使用 2-3-4 树而不是 splay 树？它们都是自我平衡和排序的，所以我看不出它们之间有太大的区别。

我对2-3-4 树如何在操作后保持高度平衡属性操作有一个基本的了解，以确保即使是最坏情况下的操作也是 O(n logn)。

但我不明白为什么只有2-3-4？

为什么不是 2-3 或 2-3-4-5 等？

我对红黑树和 2-3-4 树以及它们如何保持高度平衡以确保最坏情况下的操作为 O(n logn) 都有基本的了解。

但是，我无法理解来自维基百科的这段文字

2-3-4 树是红黑树的等距，这意味着它们是等效的数据结构。换句话说，对于每棵2-3-4树，至少存在一棵数据元素顺序相同的红黑树。而且，对2-3-4树的插入和删除操作会导致节点扩展、分裂和合并，相当于红黑树中的颜色翻转和旋转。

我看不出这些操作是如何等效的。维基百科上的这句话准确吗？怎么能看出这些操作是等价的呢？

在这段代码中，我将 numitems 声明为静态变量，并初始化了类的超大尺寸。因为我认为这是错误的主要原因，(return (numitems==order-1));但这里也是与相关的问题(childarrray[0]==NULL)，完全这段代码取自 Java 并转换为 C++，所以我添加了指针而不是引用。请帮助修复我的代码中的错误。

我一直在实现一个 LLRB 包，它应该能够在Sedgewick 描述的自下而上 2-3 或自上而下 2-3-4 两种模式中的任何一种模式下运行（代码- 改进的代码，虽然只处理 2-这里有3 棵树，感谢 RS 的指针）。

Sedgewick 对 2-3 模式的树操作提供了非常清晰的描述，尽管他花了很多时间谈论 2-3-4 模式。他还展示了在插入过程中对颜色翻转顺序的简单更改如何改变树的行为（在 2-3-4 中向下拆分或在 2-3 向上拆分）：

然而，他用以下内容掩盖了 2-3-4 LLRB 中的删除：

下一页的代码是 LLRB 2-3 树的 delete() 的完整实现。它基于在自顶向下的 2-3-4 树中插入方法的逆向：我们在沿着搜索路径向下的途中执行旋转和颜色翻转，以确保搜索不会在 2 节点上结束，这样我们就可以删除底部的节点。我们使用方法 fixUp() 在 insert() 代码中的递归调用之后共享颜色翻转和旋转的代码。使用 fixUp()，我们可以在搜索路径上留下右倾的红色链接和不平衡的 4 节点，确保这些条件在向上树的过程中得到修复。（该方法对 2-3-4 树也是有效的，但是当搜索路径之外的右节点是 4 节点时需要额外的旋转。）

他的 delete() 函数：

我的实现为 2-3 树上的所有树操作正确维护 LLRB 2-3 不变量，但对于 2-3-4 树上的右侧删除子类失败（这些失败的删除导致右倾斜的红色节点，但滚雪球到树不平衡，最后是空指针取消引用）。从对讨论 LLRB 树并包括在任一模式下构建树的选项的示例代码的调查来看，似乎没有一个正确实现从 2-3-4 LLRB 中删除（即没有一个提到额外的旋转，例如 Sedgewick 的 java上面和这里）。

我很难弄清楚他所说的“当搜索路径之外的正确节点是 4 节点时额外旋转”是什么意思；大概这是向左旋转，但是在何时何地？

如果我在调用 fixUp() 之前或在 fixUp 函数结束时向左旋转通过 4 节点等效项（即 RR 节点）或右倾斜 3 节点等效项（BR 节点），我仍然会得到相同的不变矛盾.

这是我发现的最小失败示例的树状态（通过从 0 到相应最大值的顺序插入元素生成）。

第一对树显示了从删除元素 15 之前的不变一致性状态到之后的明显破坏状态的转换。

第二个与上面基本相同，但删除了 0..16 的 16 个（删除 15 个导致相同的拓扑）。请注意，不变矛盾设法跨越根节点。

关键是要了解如何将在树向下遍历到目标节点期间产生的违规恢复。以下两棵树分别显示了上面的第一棵树在分别向左和向右走之后的样子（没有删除，在使用 fixUp() 向上走之前）。

尝试在不使用 fixUp 的情况下删除“-1”后：

尝试在不使用 fixUp 的情况下删除“16”后：

当节点只有一个红色的右孩子时，尝试向左旋转似乎是解决方案的一部分，但它不能正确处理连续的两个红色右孩子，当两个孩子都是红色时，在此之前使用 FlipColor似乎进一步改善了这种情况，但仍然违反了一些不变量。

如果我进一步检查右孩子的右孩子在其兄弟姐妹为黑色时是否为红色，如果这是真的，我只失败一次，但此时我觉得我需要一个新的理论而不是一个新的本轮.

有任何想法吗？

作为参考，我的实现在这里可用（不，它不是 Java）。

跟进：

我对此感兴趣的部分原因是为了证实许多人声称 2-3 LLRB 树比 2-3-4 LLRB 树更有效。我的基准测试已经证实了插入和删除的这一点（2-3 大约快 9%），但我发现 2-3-4 树的检索速度要快得多。

以下时间在运行中具有代表性且一致：

第一列是工作台名称，第二列是操作数，第三列是结果。i5M 2.27 上的基准测试。

我已经查看了 2-3 树和 2-3-4 树的分支长度，其中几乎没有解释检索差异（从根到节点的平均距离和 1000 棵树的 SD，每棵树都有 10000 个随机插入）：

根据我的书，在 AVL 树中从偶数高度的节点到奇数高度的节点的红色链接着色给出了（完全平衡的）2-3-4 树，其中红色链接不一定是左倾的。但我不知道具体如何。当我尝试一些例子时，我一直卡住。有人可以为我说明一下吗？

在下面描绘的2-3-4 树中（来自Java 中的数据结构和算法，第 2 版），为什么插入99会导致节点分裂，83/92/104因为它似乎99可以插入到正确的孩子（C孩子，进入紧接在97) 之后没有任何拆分？

我正在尝试在节点类中初始化一个节点数组，它们是私有成员：

但不幸的是它没有编译，错误是：

从下面的java代码。

请帮我轻松转换代码，我必须将订单声明为公开吗？我试过了但是没用，我也试过在类外声明顺序，比如 const int node::order=4 但还没有成功，有什么问题？我需要一个包含成员的数组，大小应该是 order 或 4。当我看书时，作者说你在本书中用 C++ 编写 java 代码时需要什么，它说指针，所以我添加了指针，但还没有成功。

这是原始的 phpmyadmin 错误消息，当我输入上面显示的代码 sql 创建表时：

我想了解这段代码应该如何正确编写以及有什么问题！

我正在尝试在 python 中构建一个 2-3-4 树。到目前为止，插入似乎工作到高度为 3 左右的节点。在那之后，数据似乎被丢弃而不是被插入到树中。我不确定为什么会发生这种情况，并多次检查了我的代码。我已经在我得到插入算法的插入代码附近发表了评论。提前感谢您对我的问题的任何见解。