如何旋轉樹木或AVL樹？

Question

對不起再次打擾你們，但我有一個問題，我還沒有想出我自己的好幾天。 這是關於一個樹木的旋轉，例如，在正確的位置旋轉樹木。 問題是如何鏈接（或連接）pos->left到pos的原始父親？ 我在網上發現了這個代碼，這可行，但我沒看到它是如何解決我的問題的，是因爲使用*&？如果是這樣，你能幫我解釋一下嗎？ pos=b的功能是什麼？

void Treap::right_rotate(Node *&pos) { 
    Node *b = pos->left; 
    pos->left = b->right; 
    b->right = pos; 
    pos  = b; 
} 

在此先感謝！

Answer 1

棘手的部分確實是*&部分。它聲明它是指向一個指針（這裏是一個link或two對一些相似的示例代碼，但我擔心它們可能比有用的更混亂）。

通過將指針指向的節點更改爲pos = b，可以將內容交換到不同的節點，而無需知道父級。原始參考被更新爲新的旋轉節點。

下面是一個圖表，以防萬一你需要對旋轉看起來有點矯枉過正（儘管聽起來像你理解那個部分）。

初始條件：

Node *&pos; 

     | 
     [P] 
    / \ 
    L  R 
    /\ /\ 
    w x y z 

然後，您可以存儲左孩子，因爲你要儘可能爲P而言覆蓋它。

Node *b = pos->left; 
pos->left = b->right; 

      | 
    L  [P] 
/\ / \ 
w  x  R 
      /\ 
      y z 

現在我們完成旋轉自從L的浮動空間，打破了正確的樹結構：

b->right = pos; 

     L  
    /\ | 
    w [P] 
     / \ 
     x  R 
      /\ 
      y z 

然後，我們通過更新參考節點指針完成保養是新節點替換那個地方的內容存儲：

pos = b; 

     | 
     [L]  
    / \ 
    w  P 
     / \ 
     x  R 
      /\ 
      y z 

任何人以前指向pos（pos的原稿inal父母）現在指向內存中的相同位置，但該值現在已被替換爲已旋轉的孩子。