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

Question

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

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

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

Мой вопрос: как получить2n / 3?

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

Как рассчитать это?

Спасибо

Answer 1

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

Answer 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 + (Количество узлов в левом поддереве) + (Количество узлов в правом поддереве)

Для нашего случая, когда дерево имеет последний наполовину заполненный уровень, если мы предполагаем, что правое поддерево имеет высоту 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 ..... (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.

Answer 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)

Answer 4

Количество узлов на -

• уровень 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. т.е. 2 ^ (n + 1) = S + 1

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

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

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

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

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

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

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

Answer 5

Добавить к ответу Свена.Как (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