找到三元树的高度

Question

三元堆就像二叉树，只需每个节点都可以包含 $ 3 $ sons，而不是 $ 2 $ < / span>。

我尝试绑定堆中的节点数， $ n $ ，使用堆 $的高度h $ 。

解决方案到达：

$$ 3 ^ h

尚未：

$$ \ frac {3 ^ ^ h} {2}

简而言之，我所做的是：

$$ \ sum_ {i= 0} ^ {h - 1} 3 ^ i=frac {3 ^ h-1} {2} $$

除最后级别之外的所有级别中的所有节点，因为所有级别都已完整。

如果上次级别已满：

$$ \ frac {3 ^ h - 1} {2} + 3 ^ h $$

如果最后一个级别只有 $ 1 $ 节点，我们得到：

$$ \ frac {3 ^ h - 1} {2} + 1 $$

从这里，我得出了一开始就得出的。

为什么解决方案到达其他东西？

Answer 1

预期的解决方案是错误的。

pick $ h= 0 $ 。具有高度 $ 0 $ 的唯一三元堆仅具有一个节点。然而，预期的解决方案说它需要至少 $ 3 ^ 0 + 1= 2 $

如果您的意思是写入 $ 3 ^ h \ le n \ le 3 ^ {h + 1} $ 而不是 $ 3 ^ h ，预期的解决方案仍然是错误的。 考虑带有 $ n= 2 $ 节点的三元堆。此堆有高度 $ 1 $ ，但根据预期的解决方案，它应该至少至少具有 $ 3 ^ h= 3 $ 节点。