0

有谁知道插入顺序对 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，并插入它，然后再重复冲洗子列表中位数的任一侧。这是真的？如果是这样，什么序列使高度最大化？

4

1 回答 1

1

是的，插入的顺序很重要。显然，如果更多节点是 1 节点，则对于相同数量的键，树会更高。他们最大化树中 1 节点数量的方法是将树的一个分支不断扩展为 4 节点，增加树的高度，同时将许多节点保留为 1 节点。本质上，插入预先排序的键。1,2,3,..,k. 对于最小高度的树，您希望在所有分支中均匀扩展，以填满树的每一层。因此，您插入键的中值，在此键处拆分插入列表，然后从列表的两半中插入中值，依此类推..

于 2014-05-13T15:36:59.190 回答