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

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

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

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

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

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

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

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


data-structures tree binary-tree space-complexity
person Anand Shivalkar    schedule 17.10.2019    source источник
comment
Как насчет того, чтобы показать нам, как определяется ваше дерево (покажите код). А затем расскажите нам, как вы думаете об ответе, и объясните, как вы пришли к такому выводу.   -  person Jim Mischel    schedule 17.10.2019
comment
Я только что добавил объяснение, пожалуйста, посмотрите.   -  person Anand Shivalkar    schedule 17.10.2019

Ответы (1)


arrow_upward
0
arrow_downward

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

В разделе «Сложность космоса» говорится:

Сложность пространства: O (n). В худшем случае размер набора может вырасти до n. В среднем случае размер будет nlogn для n элементов в nums, что дает среднюю сложность случая 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).

person Jim Mischel    schedule 17.10.2019