具有给定键的节点数最少的 2,4 树
2,4 tree with the fewest number of nodes with the given keys
假设我们有一组键 K = {1, 2, 3, 4, 5, 6,..., 15} 我们需要从中构建一个二四树，这样：
- CASE1 : 树的节点数最少。
- CASE2 : 树的节点数达到最大值。
我的想法 -
二四树中的一个节点最多可以有3个键，每个节点有4个children，如果我们需要最小化节点数我们需要尽可能的保持节点满，但是似乎找不到可以保证这一点的策略。
一种似乎有利可图的方法是将数组分成三部分，然后在根部插入中位数，接下来第一个和最后一个 child 是 pre-determined 并重复相同的过程剩下的 keys.this 方法似乎也不尽如人意。
我们确实知道这种结构的最坏情况高度需要接近 4，最佳情况高度需要接近 2（使用 2、4 树高度属性 h ~ log(n)）
是否有解决此类问题的策略（任何提示将不胜感激）？
制作节点数最少的2-4树：
- 从N个keys开始，floor(N/4) of then需要parents。选择这些键，尽量均匀分布，保证两边各有2-3个键。
- 对 parents 重复此过程，直到您最多拥有 3 个键。那些在根部。
所以从 15 个密钥开始，您在 4 个节点（3 parents）中有 12 个 leaf-level 个密钥。那 3 parents 可以进入根目录。
假设我们有一组键 K = {1, 2, 3, 4, 5, 6,..., 15} 我们需要从中构建一个二四树，这样：
- CASE1 : 树的节点数最少。
- CASE2 : 树的节点数达到最大值。
我的想法 -
二四树中的一个节点最多可以有3个键，每个节点有4个children，如果我们需要最小化节点数我们需要尽可能的保持节点满，但是似乎找不到可以保证这一点的策略。
一种似乎有利可图的方法是将数组分成三部分，然后在根部插入中位数，接下来第一个和最后一个 child 是 pre-determined 并重复相同的过程剩下的 keys.this 方法似乎也不尽如人意。
我们确实知道这种结构的最坏情况高度需要接近 4，最佳情况高度需要接近 2（使用 2、4 树高度属性 h ~ log(n)）
是否有解决此类问题的策略（任何提示将不胜感激）？
制作节点数最少的2-4树：
- 从N个keys开始，floor(N/4) of then需要parents。选择这些键，尽量均匀分布，保证两边各有2-3个键。
- 对 parents 重复此过程，直到您最多拥有 3 个键。那些在根部。
所以从 15 个密钥开始，您在 4 个节点（3 parents）中有 12 个 leaf-level 个密钥。那 3 parents 可以进入根目录。