如何在節點樹中旋轉節點？

我的代碼是如何在節點樹中旋轉節點？

private Node rotateLeftChild(Node n) 
{ 
    Node o = n.left; 
    n.left = o.right; 
    o.right = n; 
    return o; 
}

當我調用它在根旋轉的樹是這樣的：

它刪除4和1，使5/7左根。我試圖讓這個方法成爲一個無效的方法，但似乎也沒有效果。我會以完全錯誤的方式去做這件事嗎？

來源

2012-11-30 Pat Gallagher

通過「旋轉」，你的意思交換4''和'8'相對於'7'（即交換'left'和'right'）？ – 2012-11-30 05:43:29

您是否嘗試過調試？我會在* return o *處設置一個斷點來檢查。我認爲你的左旋轉代碼沒有問題，但問題可能在更高的地方（*可能是你試圖使用你的旋轉代碼*） – Sujay

這是一種支持方法，但現在它不是'當我只是單獨使用它時，我不會工作。 –

首先，我的英語很抱歉。

回答一個問題 - 爲什麼節點4個自敗簡單。 7有父節點（或7是root）。當你調用rotateLeftChild，7母公司仍然是「思考」，他的孩子是7，而不是4：

因此，有樹的解決方案：

製作鏈接到父節點並更新它。在leftRotation的結尾，分別進行賦值，n.Parent.Left = o或n.Parent.Right = o（if（n.Parent.Left == n）或（n.Parent.Right == n））。當然，當你旋轉根的孩子時，你必須更新鏈接到樹的根。

當您添加|插入|找到節點，將所有以前的（父節點）節點保存在堆棧中，然後在輪換之後，您必須將鏈接更新到其子節點。或者像這樣使用遞歸：

private Splay(Node parent, Node cur, Node n, bool canMoveUpTwice = false) { 
    if (cur.Value > n.Value) 
     Splay(cur, cur.Left, n, !canMoveUpTwice); 
    else 
     Splay(cur, cur.Right, n, !canMoveUpTwice); 

    if (canMoveUpTwice) 
     MoveUpTwice(); 
    else 
     MoveUpOnce(); 

    if (parent.Left == cur) 
     parent.Left = n; 
    else 
     parent.Right = n; 

    if (Parent == null) 
     tree.Root = n; 
}

如何使用。添加節點後，您必須運行Splay（root，newNode）。當然，你會得到堆棧溢出。

您必須交換節點的值，然後認爲節點已經交換。在非標準實現旋轉的，我們有這樣的畫面：在旋轉與我們得到這個（= x表示「節點具有值X」）互換：所以，我們有這樣的代碼
```
private rotateLeftChild(Node q) { 
    Node p = q.Left; 

    Swap(q.Value, p.Value); 

    A = p.Left; 
    B = p.Right; 
    C = q.Right; 

    q.Left = A; 
    q.Right = p; 

    p.Left = B; 
    p.Right = C; 
} 
```

小心：代碼尚未經過測試。

來源

2012-11-30 19:51:48

謝謝，我沒有想過檢查父節點的想法。 –

如何在節點樹中旋轉節點？

回答

相關問題