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

问：

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

这意味着该算法声称采用任何霍夫曼树 T 并将其高度限制在 L 级（T 最多有 L^2 个节点）。我在这里的问题是，因为霍夫曼树理论上可以具有类似 的形状，因此在步骤 1 之后，T1 中可能只剩下 L-1 节点，而 T2 包含叶子。然而，如果 ，这意味着 ，这意味着要构建一个具有所有叶子的 T2，它的高度必须为 L。这反过来意味着你不能将 T2 添加到 T1 中，而不会产生至少 L+1 高的树。(1 (2 (3 (4))))2^L - (L-1)2^(L-1) > (L - 1)2^L - (L - 1) > 2^(L - 1)2^L - (L - 1)

是我在这里弄错了什么，还是单侧霍夫曼树的 BRCI 算法被破坏了？

举个例子，我拿了一个 T ，理论上你应该能够将其限制在 3 的高度。(1 ((2 3) (4 (5 (6 7)))))

完成 BRCI 算法的步骤后，将生成类似于 的 T1 和 T2。T2 的高度已经为 3（因为它包含 6 个元素，您无法在高度为 2 的树中描绘这些元素），因此在步骤 3 中计算的级别为 。即使忽略该级别，您也无法将 T2 附加到 T1 中的任何位置（甚至创建一个以 T1 和 T2 为子节点的新根节点），除非高度至少为 4。(1 ([empty] [empty]))((2 3) ((4 5) (6 7))L - h(T2) - 1 = 3 - 3 - 1 = -1