Как рассчитать высоту сбалансированного дерева двоичного поиска в O (log n) раз сложности?

Question

Я понимаю, что для вычисления высоты дерева двоичного поиска в O (n) мы можем использовать следующую функцию

public static int treeHeight(Node root) {
      if (root == null) {
         return -1;
      }

      int left = treeHeight(root.left) + 1;
      int right = treeHeight(root.right) + 1;

      return Math.max(left, right);
   }  

Однако, учитывая тот факт, что дерево [сбалансировано] [ 2] как мы можем вычислить высоту дерева двоичного поиска в O (log n).

Данная проблема:

Answer 1

Это невозможно.

Если нижний ряд заполнен предсказуемым образом, это можно сделать. Например, если последний ряд всегда был заполнен слева направо, вы могли бы спуститься вниз по левой стороне за время O (log n), поскольку левая сторона гарантированно будет иметь максимальную высоту.

В Постановка задачи: узлы в нижнем ряду могут быть где угодно. Точная высота не может быть вычислена за O (log n). Вы можете получить в пределах 1 от высоты за O (log n) шагов, но чтобы получить точную высоту, вам, возможно, придется исследовать до n / 2 узлов в нижней части дерева, чтобы найти отставших (если таковые имеются).

Худший случай - это когда последний уровень полностью заполнен и каждый узел на последнем уровне должен быть проверен на наличие детей. Было бы n / 2 узлов и две проверки на узел, таким образом, всего n проверок. В этом случае не было бы детей, но все равно потребовалось бы O (n) проверок, чтобы проверить это.