Почему этот код для проверки сбалансированности двоичного дерева занимает время O (n log n), когда он многократно пересчитывает глубины?

Question

Этот код предназначен для проверки, является ли двоичное дерево сбалансированным (сбалансированное, определяемое как дерево таким образом, что высоты двух поддеревьев любого узла никогда не отличаются более чем на один.

Я понимаю N часть времени выполнения O (NlogN). Значение N связано с тем, что каждый узел дерева посещается хотя бы один раз.

int getHeight(TreeNode root){
    if(root==null) return -1; //Base case
    return Math.max(getHeight(root.left), getHeight(root.right))+1; 
}

boolean isBalanced(TreeNode root){
    if(root == null) return true; //Base case

    int heightDiff = getHeight(root.left) - getHeight(root.right);

    if(Math.abs(heightDiff) > 1){
        return false;
    } else{ //Recurse
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

Что я не понимаю, так это logN-часть времени выполнения O (NlogN). Код будет отслеживать каждый возможный путь от узла до нижней части дерева. Поэтому код должен быть больше похож на N2 ^ N или что-то? Как шаг за шагом прийти к выводу, что время выполнения равно O (NlogN)?

Answer 1

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

                  *
                 /
                *
               /
              *

Здесь вычисление глубины левого и правого поддеревьев действительно приведет к посещению каждого узла один раз. Однако, поскольку между левым и правым поддеревьями обнаружен дисбаланс, рекурсия останавливается без рекурсивного исследования левого поддерева. Другими словами, для поиска примера, когда рекурсия должна выполнять большую работу, потребуется творческий подход.

Вы правы, что проверка базовой линии для разницы высот займет время & Theta; (n), потому что каждый узел должен быть отсканирован. Проблема с этим кодом заключается в том, что он может повторно сканировать узлы много, много раз, поскольку он пересчитывает разницу высот во время рекурсии. Если мы хотим, чтобы эта функция выполнялась очень долго - не обязательно как можно дольше, но долгое время - мы бы хотели сделать так, чтобы

• левое и правое поддеревья имеют примерно одинаковую высоту, так что рекурсия переходит к левому поддереву, но
• дерево крайне неуравновешено, помещая большинство узлов в левое поддерево.

Один из способов сделать это - создать деревья, в которых правое поддерево - это просто длинный позвоночник, высота которого равна высоте левого поддерева, но с меньшим количеством узлов. Вот одна из возможных последовательностей деревьев с этим свойством:

                              *
                             / \
                *           *   *
               / \         / \   \
      *       *   *       *   *   *
     / \     / \   \     / \   \   \
*   *   *   *   *   *   *   *   *   *

Механически каждое дерево формируется путем взятия предыдущего дерева и размещения на нем правого корешка. Оперативно эти деревья определяются рекурсивно следующим образом:

• Дерево порядка 0 - это один узел.
• Дерево порядка - (k + 1) - это узел, левый дочерний элемент которого является деревом порядка k, а правый дочерний элемент которого представляет собой связанный список высоты k.

Обратите внимание, что число узлов в дереве порядка k равно & Theta; (k ² ). Вы можете увидеть это, заметив, что деревья имеют красивую треугольную форму, где каждый слой имеет на один узел больше, чем предыдущий. Суммы вида 1 + 2 + 3 + ... + k работают на & Theta; (k ² ), и хотя мы можем быть более точными, это действительно не нужно делать поэтому.

Теперь, что произойдет, если мы запустим эту рекурсию в корне любого из этих деревьев? Что ж, рекурсия начнется с вычисления высоты левого и правого поддеревьев, которая сообщит, что они имеют одинаковую высоту. Затем он рекурсивно исследует левое поддерево, чтобы увидеть, сбалансировано ли оно. После выполнения некоторого (большого) объема работы обнаружится, что левое поддерево не сбалансировано, и в этот момент рекурсия не будет переходить к правому поддереву. Другими словами, объем работы, выполненной на дереве порядка k, ограничен снизу

• W (0) = 1 (один узел посещается один раз) и
• W (k + 1) = W (k) + & Theta; (k ² ).

Чтобы увидеть, откуда взялся термин W (k + 1), обратите внимание, что мы начинаем со сканирования каждого узла в дереве, и есть узлы & theta; (k ² ) для сканирования, а затем рекурсивно применяем процедура на левое поддерево. Расширяя это повторение, мы видим, что в дереве порядка-k общая выполненная работа составляет

W (k) = & Theta; (k ² ) + W (k-1)

= & Theta; (k ² + (k - 1) ² ) + W (k - 2)

= & Theta; (k ² + (k - 1) ² + (k - 2) ² ) + W (k - 3)

...

= & Theta; (k ² + (k - 1) ² + ... + 2 ² + 1 ² )

= & Theta; (k ³ ).

Этот последний шаг следует из того факта, что сумма первых k кубов вычисляется до & Theta; (k ³ ).

Чтобы закончить, у нас есть еще один шаг.Мы показали, что деревья порядка-k требуют всего Θ (k ³ ) для работы с этим рекурсивным алгоритмом.Однако нам бы хотелось, чтобы время выполнения ограничивалось в терминах n, общего числа узлов в дереве, а не k, порядка дерева.Используя тот факт, что число узлов в дереве порядка k равно Θ (k ² ), мы видим, что дерево с n узлами имеет порядок Θ (k ^1/2 ),Подставляя это, мы видим, что для произвольно большого n мы можем сделать общую работу равной equal ((n ^1/2 ) ³ ) = Θ (n ^3/2 ) , что превышает предложенную вами оценку O (n log n).Я не уверен, является ли это наихудшим случаем для этого алгоритма, но он определенно не очень хороший.

Так что да, вы правы - время выполнения вообще не равно O (n log n),Однако - это случай, когда дерево идеально сбалансировано, и время выполнения действительно равно O (n log n).Чтобы понять почему, обратите внимание, что если дерево идеально сбалансировано, каждый рекурсивный вызов будет

• выполнять O (n) работу сканирования каждого узла в дереве, тогда
• сделает два рекурсивных вызована меньших деревьях, каждое из которых приблизительно вдвое больше предыдущего.

Это дает рекуррентность T (n) = 2T (n / 2) + O (n), которая решаетO (n log n).Но это только один конкретный случай, а не общий случай.

Заключительное примечание - с незначительной модификацией этот код может быть выполнен для выполнения за время O (n) во всех случаях.Вместо того, чтобы пересчитывать глубину каждого узла, сделайте начальный проход по дереву и аннотируйте каждый узел его глубиной (либо установив некоторое внутреннее поле, равное глубине, либо добавив вспомогательное HashMap, сопоставляющее каждый узел его глубине).Это можно сделать за время O (n).Оттуда для рекурсивного обхода дерева и проверки того, имеют ли левое и правое поддеревья высоту, различающиеся не более чем на один, требуется O (1) работа на узел по n общим узлам для общего времени выполнения O (n).

Надеюсь, это поможет!