Перекошенное двоичное дерево против совершенного двоичного дерева - сложность пространства

Question

занимает ли перекошенное двоичное дерево больше места, чем, скажем, идеальное двоичное дерево?

Я решал вопрос # 654 - Максимальное двоичное дерево в Leetcode, где, учитывая массив, нужно создать двоичное деревотаким образом, корень является максимальным числом в массиве, а правое и левое поддерево создаются по тому же принципу подмассивом справа и слева от максимального числа, и там делается вывод, что в среднем и лучшемcase (совершенное двоичное дерево) занимаемое пространство будет O (log (n)), а наихудшим случаем (перекошенное двоичное дерево) будет O (n).

Например, заданные числа = [1,3, 2,7,4,6,5], дерево будет таким,

      7
    /   \
   3     6
  /  \   / \ 
 1   2  4   5

и если задано число = [7,6,5,4,3,2,1],Дерево будет таким:

7
 \
  6
 / \
    5
   / \
      4
     / \
        3
       / \
          2
         / \
            1

. Насколько я понимаю, они оба должны занимать пространство O (n), поскольку у них обоих есть n узлов. Так что я не понимаю, как они пришли к такому выводу. Заранее спасибо.

Answer 1

https://leetcode.com/problems/maximum-binary-tree/solution/

В разделе "Сложность пространства" говорится:

Сложность пространства: O (n). Размер набора может увеличиться до n в худшем случае. В среднем случае размер будет nlogn для n элементов в числах, что дает в среднем сложность для случая O (logn).

Это плохо сформулировано, но верно. Он говорит об объеме памяти, необходимой для построения дерева, а не о количестве памяти, занимаемой самим деревом. Как вы правильно указали, само дерево будет занимать O (n) место, независимо от того, является ли оно сбалансированным или вырожденным.

Рассмотрим массив [1,2,3,4,5,6,7]. Вы хотите, чтобы корень был наибольшим числом, а слева - все, что находится слева от самого большого числа в массиве. Поскольку массив находится в порядке возрастания, происходит то, что вы извлекаете 7 для корня, а затем делаете рекурсивный вызов для создания левого поддерева. Затем вы извлекаете 6 и делаете еще один рекурсивный вызов для создания левого поддерева этого узла. Вы продолжаете делать рекурсивные звонки, пока не введете 1. Всего у вас есть шесть вложенных рекурсивных вызовов: O (n).

Теперь посмотрим, что произойдет, если ваш начальный массив будет [1,3,2,7,5,6,4]. Сначала вы размещаете 7, а затем делаете рекурсивный вызов с подмассивом [1,3,2]. Затем вы помещаете 3 и делаете рекурсивный вызов для размещения 1. Ваше дерево:

             7
         3
       1

На этом этапе глубина вашего вызова равна 2. Вы возвращаетесь и ставите 2. Затем вернитесь из двух рекурсивных вызовов. Дерево теперь выглядит так:

             7
         3
       1   2

Для построения правильного поддерева также требуется глубина вызова, равная 2. Ни в одной точке глубина вызова не превышает двух. Это O (log n).

Оказывается, глубина стека вызовов равна высоте дерева. Высота идеального дерева - O (log n), а высота вырожденного дерева - O (n).