В CLRS, третье издание, на стр. 155, указано, что в MAX-HEAPIFY ,
Каждое дочернее дерево имеет размер не более 2n / 3 - худший случай. происходит, когда нижний уровень дерева заполнен ровно наполовину.
Я понимаю, почему хуже всего, когда нижний уровень дерева заполнен ровно наполовину. И в этом вопросе наихудший случай в MAX-HEAPIFY также дается ответ: «худший случай возникает, когда нижний уровень дерева заполнен ровно наполовину»
Мой вопрос - как получить 2n / 3?
Почему, если нижний уровень заполнен наполовину, тогда размер дочернего дерева достигает 2n / 3?
Как это вычислить?
Спасибо