Являются ли кучи полными бинарными деревьями?

Question

Я прочитал много определений «кучи» онлайн, и я также прочитал определение в CLRS. Большинство онлайн-определений говорят, что кучи - это полные двоичные деревья; однако CLRS начинает главу кучи следующим предложением:

(двоичная) структура данных кучи - это объект массива, который мы можем рассматривать как почти полное двоичное дерево ...

Я не уверен, почему, но меня действительно беспокоит, что CLRS называет кучи "почти завершенными", тогда как почти любое другое определение "кучи", которое я прочитал, вызывает кучи "завершено".

Это приводит меня к следующему вопросу: возможно ли иметь кучу, которая не является полным двоичным деревом?

Answer 1

Что именно означает complete? У людей разные мнения. В контексте кучи, complete двоичное дерево должно означать, что последний уровень дерева имеет максимальное количество узлов.

Любая куча, не имеющая максимальных листьев на своем последнем уровне, не является complete или nearly complete.

Например, куча с 7 элементами будет complete двоичным деревом. Но в куче с 4, 5 или 6 элементами последний уровень не будет заполнен полностью, т.е. nearly complete.

Куча с Nearly complete двоичным деревом глубины три (при условии, что глубина узла root равна быть 1) выглядит следующим образом:

Answer 2

Вы абсолютно правы, когда вас беспокоит выражение "почти завершено". Куча - это полное двоичное дерево, согласно наиболее распространенной терминологии:

• полное двоичное дерево: все, кроме последнего уровня, полностью заняты, и листья в последний уровень отображается слева от этого уровня.

• совершенное двоичное дерево: полное двоичное дерево, в котором последний уровень также полностью занят.

• полное двоичное дерево: двоичное дерево, в котором ни один из узлов не имеет только одного дочернего элемента. Иногда этот термин используется для обозначения идеального бинарного дерева, добавляя путаницу.

Идеальное бинарное дерево также полное и полное двоичное дерево, но полное двоичное дерево может быть или не быть полным двоичным деревом.

Но статья в Википедии о Двоичное дерево предупреждает:

Некоторые авторы используют термин complete для обозначения вместо совершенное двоичное дерево [...] и в этом случае они называют этот тип дерева (с, возможно, не заполненным последним уровнем) почти полным двоичным деревом или почти полным двоичным деревом .

Так что, по-видимому, автор текста, на который вы ссылаетесь, попадает в эту категорию.