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

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

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

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

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

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

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

Спасибо

69
задан Community 23 May 2017 в 12:26
поделиться