堆树高度 vs BST 高度

Question

我在课程中被问到以下问题。 “(A) 给定一个包含 12 个元素的堆树，它的高度是多少？(B) 如果它是 BST（二叉搜索树），它的高度是多少？”

现在，我明白堆是一个完全二叉树并且根据GFG：https://www.geeksforgeeks.org/height-complete-binary-tree-heap-n-nodes/，（A）的答案是：3

我在书上查到二叉树的高度是：log2(N + 1)，所以如果我把上面代码中的这个公式换掉，答案变成： 4. 这是 (B) 的答案吗？

Answer 1

一个12个元素的二叉堆会有四层，例如：

         1
    2         3
  4   5     6   7
 8 9 A B  C

。如果你称其高度为 3，那么你的答案是正确的。

具有 12 个元素的二叉搜索树可以有 4 到 12 个级别，具体取决于它是否平衡。例如，上面的堆是一个有效的 BST，如下所示：

        4
    2        8
  1   3   6     A
         5 7   9 B
                  C

还有这个：

Heap tree height vs BST height