Обновление ранга в биноминальной очереди

Question

Я читаю об операциях с биномиальной очередью здесь .

В нижней части ссылки упоминается как

Реализация биномиальной очереди

1. Операция deletemin требует умения найти все поддеревья корня. Таким образом, должны быть доступны дочерние элементы каждого узла (скажем, связанный список)
2. deletemin требует, чтобы дети были упорядочены по размеру их поддеревьев.
3. нам нужно убедиться, что легко слить локон. Два биномиальных дерева могут быть объединены, только если они имеют одинаковый размер, поэтому размер дерева должен храниться в корне. При объединении одно из деревьев становится последним дочерним элементом другого, поэтому мы должны отслеживать последнего дочернего элемента каждого узла. Хорошая структура данных - круговая связанный список, что каждый узел имеет следующую форму:

data | first |left    | right |rank No. of |
--------------------------------------------
       child |sibling |sibling| children 

Выше можно сказать, что означает "звание № из". Кто-нибудь может объяснить это примером.

Answer 1

Обратите внимание на требование «Два биномиальных дерева можно объединить, только если они имеют одинаковый размер, поэтому размер дерева должен храниться в корне».

Кажется, что вместо «размераполе "поддерево", автор поставил поле "количество детей".Это сбивает с толку, но для реализации это хорошо, потому что размер поддерева составляет 2 ^ {# дочерних элементов}.Таким образом, вы можете сравнить количество детей вместо того, чтобы сравнивать размер поддерева.

Answer 2

Насколько я понимаю, он пытается сказать: мы храним rank, что, кстати, совпадает с no. of childen (именно так обычно определяются ранги для таких деревьев).Таким образом, вы просто сохраняете в каждом узле следующее:

• data представляет элемент в дереве
• first представляет указатель на связанный список дочерних элементов (т.е.указатель на первого потомка)
• left - указатель на левого соседа
• right - указатель на правого соседа
• rank - это просторанг биномиального дерева