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

Question

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

"the worst case occurs when the bottom level of the tree is exactly half full"  

Полагаю, причина в том, что в этом случае Max-Heapify должен "проплыть" через левое поддерево.
Но я не смог понять, почему он наполовину полон?
Max-Heapify также может плавать вниз, если у левого поддерева есть только один лист. Так почему бы не рассмотреть это как наихудший случай?

Answer 1

Прочитать весь контекст:

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

Поскольку время выполнения T(n) анализируется по количеству элементов в дереве (n), а рекурсия переходит в одно из поддеревьев, нам нужно найти верхнюю границу для числа узлов вподдерево относительно n, и это приведет к тому, что T(n) = T(max num. nodes in subtree) + O(1)

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

Если вы предлагаете случай только с несколькими узлами, то это не имеет значения, поскольку все базовые случаи могут рассматриваться как O(1) и игнорироваться.