Доказательство двоичной кучи имеет

16

Я пытаюсь доказать, что двоичная куча с узлами имеет точно exactly nnвыходит, учитывая, что куча строится следующим образом:n2

Каждый новый узел вставляется через percolate up . Это означает, что каждый новый узел должен быть создан на следующем доступном дочернем узле. Под этим я подразумеваю, что дети заполнены вниз и слева направо. Например, следующая куча:

    0
   / \
  1   2

должен был бы быть построен в следующем порядке: 0, 1, 2. (числа являются просто индексами, они не дают указания на фактические данные, хранящиеся в этом узле.)

Это имеет два важных значения:

  1. На уровне не может быть узла, если уровень k не заполнен полностьюk+1k

  2. Поскольку дочерние элементы создаются слева направо, между узлами на уровне не может быть «пустых мест» или ситуаций, подобных следующим: k+1

        0
       / \
      1   2
     / \   \
    3  4    6
    

(По моему определению это была бы недопустимая куча.) Таким образом, хороший способ думать об этой куче - реализация массива кучи, где не может быть никаких «переходов» в значениях массива.

Итак, я думал, что индукция, вероятно, будет хорошим способом сделать это ... Возможно, что-то, имеющее дело с даже нечетными случаями для n. Например, некоторая индукция использует тот факт, что четные кучи, построенные таким образом, должны иметь внутренний узел с одним дочерним элементом для четного n, и не иметь таких узлов для нечетного n. Идеи?

varatis
источник
@DaveClarke: не совсем; связанный вопрос является результатом недоразумения в части редакторов, оставленных там для справки.
Рафаэль
Вы пробовали индукцию по номеру узла соответственно? количество вставок?
Рафаэль
@DaveClarke: почему? Это действительный вопрос сам по себе, имхо.
Рафаэль
Кстати, вопрос не имеет ничего общего с кучами. Требование справедливо для любого полного двоичного дерева
Ран Г.

Ответы:

8

Если я правильно понял ваш вопрос, полученная куча - это просто упорядоченное бинарное дерево, где в упорядоченном я имею в виду, что й уровень может быть занят только после того, как уровень k - 1 полностью заполнен, а каждый уровень занят слева. направо, не пропуская.kk1

Тогда доказательство идет так.

  1. Идеальное дерево глубины имеет ровно 2 k + 1 - 1 вершин.k2k+11
  2. Предположим, что куча достигает глубины . таким образом k
    1. до уровня дерево идеально (и имеет 2 k - 1 узлов там)k12k1
    2. на последнем уровне есть ровно узлов, которые все являются листьями.n2k+1
  3. У каждого листа на м уровне есть родитель. Более того, каждые два последовательных листа имеют одного и того же отца (возможно, за исключением последнего узла, у отца которого только один ребенок)k
  4. Таким образом, из узлов на уровне k - 1 , n - 2 k + 12k1k1родители, а остальные2k-1-n-2 k +1n2k+12это листья.2k1n2k+12
  5. Общее количество листьев составляет Что дает вам то, что вам нужно.
    n2k+1+2k1n2k+12
Ран Г.
источник
1
Обратите внимание, что полные отличаются от полных отличаются от совершенных бинарных деревьев. Неудачный, неоднозначный и непоследовательный выбор слов там, но что поделаешь. Я полагаю, что придерживаться определения Википедии имеет смысл, как большинство будет смотреть там в первую очередь?
Рафаэль
Ого, я даже не знал этих терминов. Спасибо за указание на это.
Ран Г.
«до уровня k − 1 дерево является совершенным (и имеет 2 ^ k - 1 узлов там)» и «Таким образом, из 2 ^ (k − 1) узлов на уровне k − 1» кажутся противоречивыми утверждениями, или я что-то упустил?
Адриан Х.
2k12k12k1+2k2+...
Ах, вы совершенно правы, большое спасибо за разъяснения!
Адриан Х.
11

Вот более простое логическое доказательство.

nthn/2n/2+1)thn/2

(n/2)(n/2)

Зубин Пахуджа
источник
1
Довольно интуитивное и понятное объяснение. Благодарю.
whitehat