在複雜性隊列隊列中調整排名

Question

我正在閱讀有關生物統計排隊操作here。

在鏈路的底部它被提及作爲一個二項式隊列

1. deletemin操作

   實現需要的能力來找到根的所有子樹。因此，每個節點的子節點應該可用（比如鏈表）

2. deletemin要求孩子按其子樹大小排序。
3. 我們需要確保合併髮束很容易。兩個二叉樹只有具有相同的大小時纔可以合併，因此樹的大小必須存儲在根中。在合併時，其中一棵樹成爲另一棵的最後一個孩子，所以我們應該跟蹤每個節點的最後一個孩子。用好數據結構是循環雙向 鏈表的每個節點具有以下形式的內容：

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

在上面是什麼意思作家「排名號可以在任何一個請與例子解釋一下嗎？

Answer 1

據我所知，他試圖說：我們存儲了rank，這與no. of childen顯然是相同的（這就是通常定義的樹的排名），因此，您只需在每個節點中存儲以下：

• data表示樹中的元素
• first表示指向兒童鏈接列表的指針（即，一個指向第一個孩子）
• left是一個指向左邊的鄰居
• right是一個指針向右鄰居
• rank是二叉樹

Answer 2

注的要求僅僅排名「兩個二叉樹只有在它們具有相同的大小時纔可以合併，因此樹的大小必須存儲在根中。」

看來，作爲一個「大小的子樹」字段，作者把一個「數字的孩子」字段。這很令人困惑，但是對於實現來說，這很好，因爲子樹的大小是2^{children`}。因此，您可以比較＃個孩子，而不是比較子樹的大小。