節點密鑰更改後多路樹成堆？

Question

該樹具有不變性，即父節點必須始終小於其子級，如上圖所示。現在假設一些節點的密鑰已經改變並且破壞了不變性，我想保持不變性。我認爲它基本上是比較交換父節點的每個孩子，但我不知道如何編寫遞歸來遍歷樹。它似乎不同於我之前瞭解到的二叉樹...

Btw每個節點都沒有索引，但只有三個指針：parent，leftChild，rightSibling。如果節點是root，則它的父節點指向NULL;如果該節點是最右邊的節點，則其右邊的節點指向NULL ... 任何人都可以對此有所瞭解嗎？ Thx提前！

Answer 1

對於初學者來說，這個多路樹表示爲二叉樹稱爲left-child/right-sibling representation，並且與正常的多路樹表示有一些折衷。這個較老的問題/答案可能會給出一些關於如何遞歸遍歷這些樹的背景知識。

至於你的問題：有一個節點的值更改兩種可能的結果：

• 如果節點的值已經下，那麼你可能需要向上交換它，直到它的價值不再少於其父母。
• 如果節點的值已經變爲以上，那麼您可能需要將其與最小的孩子交換，直到該值不再大於其任何孩子。

編寫此遞歸的一種方法是在兩遍中處理樹，在每次遍歷中檢查這兩種情況之一。沒有根本的原因，這些通行證不能組合在一起，但爲了解釋簡單，我會獨立處理每個通行證。

在第一種情況下，我們可能需要將節點與其父節點交換，因爲其值已降低。在這種情況下，我們需要模擬某種樹遍歷，其中我們首先處理所有子節點，然後處理節點本身。這樣，如果一個值需要在多個層次上交換到根目錄，我們可以遞歸地將其提升到可能的最高層次，而不會跨越根目錄，然後將其提升一個級別。如果我們有一個標準的多路樹，遞歸應該是這樣的：

void FixTreeUpward(TreeNode curr) { 
    /* If the current node is null, we're done. */ 
    if (curr == null) return; 

    /* Process each child. */ 
    for (TreeNode child that is a child of curr) { 
     FixTreeUpwardRec(child); 
    } 

    /* If we need to swap values with our parent, do so here. */ 
    if (curr.parent != null && curr.value < curr.parent.value) { 
     swap(curr.value, parent.value); 
    } 
} 

由於我們使用的是左孩子，多路樹的右兄弟表示，將在環路中間會看有點奇怪。我們先下降到左邊的孩子，然後繼續往右走，直到節點用完。在僞代碼：

void FixTreeUpward(TreeNode curr) { 
    /* If the current node is null, we're done. */ 
    if (curr == null) return; 

    /* Process each child. */ 
    for (TreeNode child = curr.left; child != null; child = child.right) { 
     FixTreeUpwardRec(child); 
    } 

    /* If we need to swap values with our parent, do so here. */ 
    if (curr.parent != null && curr.value < curr.parent.value) { 
     swap(curr.value, parent.value); 
    } 
} 

這就是它的全部！從概念上講，遞歸不是那麼困難，關於它的唯一奇怪的部分是我們如何訪問孩子。

讓我們來思考算法的第二部分，我們必須在必要時將氣泡向下展開。爲此，我們將執行以下操作：對於每個節點，查看其所有子節點並查找具有最小值的子節點。如果該值小於根節點的值，則將樹的根與該子進行交換，然後重複。在僞伊斯蘭代碼：

void FixTreeDownward(TreeNode root) { 
    /* If the root is null, we have nothing to do. */ 
    if (root == null) return; 

    /* Find the smallest child. */ 
    TreeNode smallChild = (root's first child, or null if none exists); 

    for (TreeNode child in the children of the root) { 
     if (child.value < smallChild.value) { 
      smallChild = child.value; 
     } 
    } 

    /* If we have a smallest child and it's smaller than our value, 
    * swap values and recursively repeat this. 
    */ 
    if (smallChild != null && smallChild.value < root.value) { 
     swap(smallChild.value, root.value); 
     FixTreeDownward(smallChild); 
    } 
} 

所以現在唯一的問題是迭代所有的孩子，幸運的是，這並不難！和以前一樣，我們下降到左邊的子樹，然後繼續往右走，直到節點耗盡。這顯示在這裏：

void FixTreeDownward(TreeNode root) { 
    /* If the root is null, we have nothing to do. */ 
    if (root == null) return; 

    /* Find the smallest child. */ 
    TreeNode smallChild = root.left; 

    for (TreeNode child = root.left; child != null; child = child.right) { 
     if (child.value < smallChild.value) { 
      smallChild = child; 
     } 
    } 

    /* If we have a smallest child and it's smaller than our value, 
    * swap values and recursively repeat this. 
    */ 
    if (smallChild != null && smallChild.value < root.value) { 
     swap(smallChild.value, root.value); 
     FixTreeDownward(smallChild); 
    } 
} 

而且我們應該全部設置！

希望這會有所幫助！