Как понимать сегментированные биномиальные кучи, описанные в <Чисто функциональные структуры данных>

В главе 6.3.1 диссертации Чисто функциональные структуры данных , говорит:

Затем, когда мы создаем новое дерево из нового элемента и сегмента деревьев рангов 0 ... r-1, мы просто сравниваем новый элемент с {{1 }} первый корень в сегменте (т. е. корень дерева ранга 0). Меньший элемент становится новым корнем, а более крупный элемент становится дочерним элементом корня ранга 0.

  1. T0 '- новое дерево имеет ранг 0
  2. T0..T (r-1) - исходные деревья ранга от 0 до r-1
  3. Меньший элемент становится новым корнем, а больший элемент становится рангом 0 дочерний элемент корня

Вопрос в том, что в результате шага 3 будут получены два дерева ранга 1, что противоречит биномиальным кучам.

Я неправильно понял?

8
задан wenlong 23 November 2011 в 10:27
поделиться