Как понять сегментированные биномиальные кучи, описанные в

Question

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

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

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

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

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

Answer 1

Мы создаем дерево ранга r. Структура дерева ранга r является корневым узлом с r потомками рангов 0..r-1.

Что означает та часть, которую вы цитировали.

1. Когда мы получаем новый элемент x, мы сравниваем его с элементом в T0
2. Мы создаем новое дерево T0 'ранга 0, содержащее большее из двух сравниваемых элементов
3. Мы создадим новый узел T, содержащий меньшее из двух сравниваемых элементов и с T0 ', T1, T2 ... T (r-1) в качестве дочерних

Теперь T - биномиальное дерево ранга r, и оно в порядке кучи.