BRCI 算法适用于*所有*霍夫曼树吗？

Question

我正在尝试创建一个高度有限的霍夫曼树。为此提出的一种算法是BRCI算法，它提供了一种相对快速且易于实施的解决方案。

这意味着该算法声称采用任何哈夫曼树 T 并将其高度限制为 L 级（T 最多具有 L^2 个节点）。我的问题是，因为哈夫曼树理论上可以具有像

(1 (2 (3 (4))))

这样的形状，所以在步骤 1 之后，T1 中可能只剩下 L-1 个节点，而 T2 包含

2^L - (L-1)

叶子。如果

2^(L-1) > (L - 1)

，则意味着

2^L - (L - 1) > 2^(L - 1)

，这意味着要构建包含所有

2^L - (L - 1)

叶子的 T2，它的高度必须为 L。这又意味着您无法将 T2 添加到 T1 中，而不导致一棵至少 L+1 高的树。

我在这里遇到了问题吗？或者 BRCI 算法是否因单边哈夫曼树而被破坏？

举个例子，我拿了一个 T

(1 ((2 3) (4 (5 (6 7)))))

，理论上你应该能够限制高度为 3。

完成 BRCI 算法的步骤会产生 T1

(1 ([empty] [empty]))

和看起来像

((2 3) ((4 5) (6 7))

的 T2。 T2 的高度已经为 3（因为它包含 6 个元素，无法在高度为 2 的树中描绘），因此步骤 3 中计算的级别为

L - h(T2) - 1 = 3 - 3 - 1 = -1

。即使忽略级别，如果高度不至少为 4，您也无法将 T2 添加到 T1 中的任何位置（甚至创建一个以 T1 和 T2 作为子节点的新根节点）。

Answer 1

自我回答：这实际上是一种边缘情况，运行一次 BRCI 算法不会得到所需的高度。

使其正常工作的解决方案相当简单：如果步骤 3 中计算的级别为负，请将其设置为 0 并继续算法。然后再次运行算法。

随着算法的每次重复，树都会变平，您最终会得到所需高度的树。