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

如果我没记错的话，在销毁 a 时，2-3-4 tree它应该类似于二叉树，只有 4 个孩子（递归）。下面我有我的析构函数特定代码，带有一个简单的递归删除。

问题是我仍然有泄漏。该文件仅包含我的 2-3-4 树。

我相信这是为2-3-4 trees 实现析构函数的正确方法，但我的实现似乎不正确。谁能指出我的逻辑错误？我做过图表，看起来很合理。

我的节点设计：

我的插入代码。我目前还没有实现删除功能。

---

瓦尔格林：

我观察到 2-3-4 树的高度可能会根据节点的插入顺序而有所不同。

例如 1,2,3,4,5,6,7,8,9,10 将产生高度为 2 的树

按此顺序插入时：

例如 1, 5, 10, 2, 3, 8, 9, 4, 7, 8 将产生高度为 1 的树

这是 2-3-4 树的正常属性吗？在这种情况下，按顺序插入节点将产生一棵非常不平衡的树。我认为2-3-4树应该是平衡树？

谢谢。

我在 CSC 330 中，我们有一个创建 234 或 2-3-4 树的大项目。我目前正在研究我的插入方法。我有我的 while 循环，它在树中移动，但遇到了一个简单的问题。当我分解一个 4 节点时，如何访问父节点，给它我的中间元素？我有一个 234 节点，它是一个接收元素的数组，我的元素接收一个整数和一个字符串。我知道访问父级的最佳方法是在我的节点类中创建一个方法，但这让我对如何在链表中向后移动感到困惑。

我正在为某种内存管理实现 2-3-4 树。在我的应用程序初始化期间，我想在那里插入一些整数（将其作为输入 - 比如说 n）这种插入的复杂性是什么？O（nloglog（n））？

我目前正在尝试编写一个使用 2-3-4 树的程序，但我遇到了插入函数的问题。这是相关代码..

它总是在第 19 行因内存地址错误而中断。我试过调试它，它在字符串文件的第 2245 行中断（如果有帮助的话）。这些信息并没有真正帮助我，所以也许有人可以帮助我解决这里到底出了什么问题？

我正在查看我的数据结构课程中的材料，我对这三种树的使用感到困惑。那么分别在哪些情况下我们应该更好地使用二叉搜索树、2-3树和B-树呢？有什么优点和缺点？

太感谢了！我对数据结构的东西很陌生...

我有 2-3-4 树，但修改后只有叶子有值。我不确定叶子是否是确切的词。叶子（在我的描述中）是树底部具有最大深度的节点（这些是树末端的节点）。每个假期都有一个值。其他节点（不是叶子）具有其子节点中最小值的“值”。所以这是有效的树：

我需要编写一些具有最大复杂度 O(log n) 的伪代码。我必须写最小值（从树返回最小值），插入（k）（插入具有 k 值的新休假），减少键（x，k）（将列表 x 中的键更改为 k），删除（x）从树中删除休假并提取 min （删除最小值）。

我试图自己写一些东西，但我不确定我是否做得对，以及我是否满足复杂性条件。

我希望最小功能可以，但是插入功能可以吗？是不是太复杂了？你能帮我满足复杂性条件吗？你能帮我处理其他功能吗（文字算法就足够了:)）。

有谁知道插入顺序对 2-3-4 树有什么影响？还是 B 树？

似乎最小高度的公式是 log _m (k+1)，其中 m 是最大高度。孩子的数量，k 是键的数量

最大高度的公式是：log _n ((k+1)/2) 其中 n 是最小高度。一个内部节点可以拥有的子节点数。

但是什么插入序列实际上得到了这些结果？！我不知道。

有人建议最小化 2-3-4 树的高度，你可以取线性序列的中值，例如。1,2,3,4,5,6,7,8 它是 4，并插入它，然后再重复冲洗子列表中位数的任一侧。这是真的？如果是这样，什么序列使高度最大化？

我真的很感激 2-3-4 树的澄清......假设你有这样定义的树：

我的问题实际上是当它的变量（firstData，secondData，thirdData）已经有一些值时，我怎么知道节点是否已满（其中包含所有三个值）？

例如：
根：|4| 根的左孩子：|1,2|
根的右孩子 |7,9|

这里 root 有一个值 (4)。我的问题是我们怎么知道它实际上有一个值，因为他所有的其他变量（secondData，thirdData）都有一些价值（即使它是垃圾）..提前谢谢！

首先，这个问题不是家庭作业。我目前正在阅读 Robert Lafore 的《Data Structures and Algorithms 2nd Edition》一书。在第 10 章中，我们学习了 2-3-4 树，然后被要求编写一个方法来找到该树中的最小值。

从概念的角度来看，我了解最小值在哪里。它只是叶子中最左边的数据项。

从编程的角度来看，我对如何实现查找此数据项的方法有点困惑。我有一个布尔值，可以判断节点是否是叶子。所以我最初做的是这样的：

这是做什么的（至少我认为它应该做的，是创建一个从根节点开始的 curNode。然后创建一个存储 curNode.getMin 的最小值。getMin() 只获取索引 0 处数组的值（其中应该保持最小值）。然后，当当前节点不是叶子时，我们应该从最小值点遍历到下一个孩子。一旦当前节点是叶子，它应该返回最小值。

但这不起作用。有谁知道如何实现这一点？提示或建议或其他任何东西？

编辑：要查看每个类以及它们如何交互，这里是每个单独类的链接。我把最小值方法放在我的 Tree234 类中

DataItem、Node、Tree234以及运行程序的位置Tree234App