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

Ответ 1

В дереве, где каждый node имеет ровно 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.

Ответ 2

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 легко получить.

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

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

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

Число узлов в левой части Subtree = 1 + 2 + 4 + 8.... 2 ^ (h + 1) = 2 ^ (h + 2) -1..... (i)

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

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

Число узлов в дереве = 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.

Ответ 3

Для полного бинарного дерева с высотой 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)

Ответ 4

Чтобы добавить к swen-ответу. Как (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

Ответ 5

Число узлов при -

• уровень 0, то есть корень равен 2 ^ 0
• Уровень 1 равен 2 ^ 1
• уровень 2 равен 2 ^ 2
• ...
• Уровень n равен 2 ^ n

Суммирование всех узлов от уровня 0 до уровня n,

• S = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 +... + 2 ^ n

Из правила суммирования геометрических рядов мы знаем, что

• x ^ 0 + x ^ 1 + x ^ 2 +... + x ^ (n) = (x ^ (n + 1) - 1)/(x-1)

Подставляя x = 2, получим

• S = 2 ^ (n + 1) - 1. i.e. 2 ^ (n + 1) = S + 1

Поскольку 2 ^ (n + 1) - это суммарные узлы на уровне n + 1, можно сказать, что число узлов с 0 детьми больше числа узлов с 2 детьми.

Теперь давайте рассчитать количество узлов в левом поддереве, дереве справа и сумме.

• Предположим, что число нелистных узлов в левом поддереве root = k.

• По приведенным выше рассуждениям количество листовых узлов в левом поддереве или root = k + 1. Число нелистных узлов в правом поддереве root = k, поскольку дерево называется наполовину полным.

• Общее количество узлов в левом поддереве root = k + k + 1 = 2k +

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

В этом причина того, что поддеревья для детей имеют размер не более 2n/3.