具有给定键的节点数最少的 2,4 树
假设我们有一组键 K = {1, 2, 3, 4, 5, 6,..., 15}，我们需要构建一个二四树，这样：
- CASE1 ：树的节点数最少。
- CASE2：树的节点数达到最大。
我的想法 -
二四树中的一个节点每个节点最多可以有3个键和4个子节点，如果我们需要最小化节点数量，我们需要尽可能保持节点满，但是似乎无法找到保证这一点的策略。
一种似乎有利可图的方法是将数组分成三部分，然后在根处插入中位数，接下来第一个和最后一个子项是预先确定的，并对其余的键重复相同的过程。这种方法似乎也达不到要求。
我们确实知道，这种结构的最坏情况高度需要接近 4，最好情况高度需要接近 2（使用 2、4 树高度属性 h ~ log(n)）
有什么策略可以解决这样的问题（任何提示将不胜感激）？
suppose we have a set of keys K = {1, 2, 3, 4, 5, 6,..., 15} and we need to build a two four tree out of this such that:
- CASE1 : the tree has the minimum number of nodes.
- CASE2 : the tree has the maximum number of nodes.
my idea -
a node in the two four tree can have upto 3 keys and 4 children per node, if we need to minimise the number of nodes we need to keep the nodes full as much as possible, but do not seem to be able to find a strategy that will guarantee this.
one way that seemed lucrative was to split the array into three parts and then insert the medians at the root, next the first and the last child are pre-determined and repeat the same process for the rest of the remaining keys.this method also seems to fall short.
we do know that the worst case height for such a structure needs to be near 4 and the best case height to be near 2 (using the 2, 4 tree height properties h ~ log(n))
is there any strategy to approach such problem (any hint would be appreciated)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
要制作具有最少节点数的 2-4 树：
因此，从 15 个键开始，您在 4 个节点（3 个父节点）中有 12 个叶级键。这三位父母可以追根溯源。
To make a 2-4 tree with the smallest number of nodes:
So starting with 15 keys, you have 12 leaf-level keys in 4 nodes (3 parents). Those 3 parents can go in the root.