Худший случай в Max-Heapify-как вы получаете 2n/3?

в CLRS, третье издание, на стр. 155, указано, что в MAX-HEAPIFY,

дочерние поддеревья имеют размер не более 2n / 3-в худшем случае возникает, когда нижний уровень дерева ровно наполовину.

Я понимаю, почему это хуже всего, когда нижний уровень дерева ровно наполовину заполнен. И он также ответил на этот вопрос в худшем случае в MAX-HEAPIFY: "худший случай происходит, когда нижний уровень дерева ровно наполовину полный"

мой вопрос, Как получить 2n / 3?

Почему если нижний уровень наполовину заполнен, то размер дочернего дерева составляет до 2n / 3?

Как это вычислить?

спасибо

5 58
algorithm treeview heap time-complexity

5 ответов:

в дереве, где каждый узел имеет ровно 0 или 2 дочерних узла, число узлов с 0 дочерними узлами на один больше, чем число узлов с 2 дочерними узлами.{Пояснение: число узлов на высоте h равно 2^h, которое по формуле суммирования геометрического ряда равно (сумма узлов с высоты 0 до h-1) + 1; и все узлы с высоты 0 до h-1 являются узлами с ровно 2 детьми}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

пусть k-число узлов в R. число узлов в L равно k + (k + 1) = 2k + 1. Общее число узлов равно n = 1 + (2k + 1) + k = 3k + 2 (корень плюс L плюс R). Соотношение (2k + 1)/(3k + 2), которое ограничено выше на 2/3. Никакая константа меньше 2/3 не работает, потому что предел, когда k переходит в бесконечность, равен 2/3.

42

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

как только это ясно, граница 2N/3 легко получить.

давайте предположим, что общее число узлов в дереве Н.

количество узлов в дереве = 1 + (количество узлов в левом поддереве) + (количество узлов в правом поддереве)

для нашего случая, когда дерево имеет последний уровень наполовину полный, если мы предположим, что правое поддерево имеет высоту h, то левое поддерево, если высота (h+1):

количество узлов в левом поддереве =1+2+4+8....2^(h+1)=2^(h+2)-1 .....(i)

количество узлов в правом поддереве =1+2+4+8....2^(h) =2^(h+1) -1 .....(второй)

таким образом, подключаясь к:

количество узлов в дереве = 1 + (количество узлов в левом поддереве) + (количество узлов в правом поддереве)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

подключение это значение в уравнение (i) мы получаем:

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

следовательно, верхняя граница максимального числа узлов в поддереве для дерева с N узлами равна 2N / 3.

30

для полного бинарного дерева высоты h, количество узлов составляет f(h) = 2^h - 1. В приведенном выше случае мы имеем почти полное двоичное дерево с нижней половиной полной. Мы можем визуализировать это как коллекцию root + left complete tree + right complete tree. Если высота исходного дерева h, то высота слева h - 1 и справа h - 2. Так уравнение становится

n = 1 + f(h-1) + f(h-2) (1)

мы хотим решить выше f(h-1) выражается в терминах n

f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2 (2)

используя выше в (1) мы имеем

n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2

=> f(h-1) = 2*(n-1/2)/3

отсюда O (2n / 3)

14

чтобы добавить к ответу Свена. Как (2k + 1) / (3k + 2) стремится к 2/3, когда k стремится к бесконечности,

Lim_(k - > inf) (2k + 1) / (3k + 2) = Lim_(k -> inf) k(2 + 1 / k) / k(3 + 2 / k) = Lim_(k -> inf) (2 + 1 / k) / (3 + 2 / k)

примените ограничение, и вы получите 2/3

1

количество узлов по -

    1