Высота кучи против высоты BST

Question

Мне задали в курсе следующий вопрос.«(A) Учитывая дерево кучи с 12 элементами, какова его высота? (B) Если бы это было BST (Binary-Search-Tree), какой была бы его высота?»

Теперь я понимаюэта куча является полным двоичным деревом и согласно 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

И это:

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