如何，如果你需要一個右右旋轉或向右向左旋轉

我想實現的AVL樹，我有一個很難知道什麼時候我需要一個RR或RL旋轉（同爲LL和LR）確定的。如何，如果你需要一個右右旋轉或向右向左旋轉

什麼是每一個先決條件和他們如何不同。我知道我什麼時候看到樹的圖片（直觀地），但是實際情況如何？

這是一個邏輯問題，沒有必要的代碼，謝謝。

我所知道的是它涉及到樹被留下重或右重。但你如何確定？

來源

2012-07-01 Kalec

你具有一定的操作，例如考慮向樹添加一個節點，然後保持平衡屬性？ – niklon

無論是在添加還是刪除，但如果我理解了其中一個，我可以想象其他人也同樣容易。我希望樹在任何時候都能保持平衡，但是由於它唯一修改的時間是通過添加或移除元素，所以我看不到任何其他必要的時刻。 **但我寧願專注於現在添加元素** – Kalec

可能有不同的解決方案，但一個是如下：

當添加的項目遞歸，在每次遞歸調用你應該保持的該呼叫是否添加的節點向左或右子樹的軌道（通過讓例如，add函數返回它）。遞歸調用後，檢查高度不變。如果您發現插入後該節點已被違反，您將知道失衡的路徑。

一些（不完全）的僞代碼：

add(item, node): 
    if item < node.value //should add to left subtree 
    if node.left is empty 
     //add item here 
    else 
     addedLeft := add(item, node.left) 
     if node.left.height - node.right.height > 1 
     if addedLeft 
      //you know the path to the subtree causing the imbalance is LL, do a RR (single-right) rotation 
     else 
      //path is LR, do a LR (double-right) rotation 
    ...

的遞歸調用將從添加的節點展開自下而上和總體思路是，以檢查在哪個節點不變的侵犯（如果有的話）。當發現該節點時，您需要知道導致不平衡的子樹的路徑。我們必須以某種方式解決這個問題，這是一個解決方案。

來源

2012-07-01 09:50:55 niklon

，所以我必須跟蹤添加節點時所走的路徑。這是否意味着我需要記住最後2條路徑？（LL或LR等）？ – Kalec

嗯，是的，沒有。是的，因爲它是必要的，以便確定要執行什麼旋轉，不因爲你並不需要「記住」它比上面pseude碼 - 邏輯是這裏要說的是，如果我們決定將節點添加到左子樹並且添加的遞歸調用也決定將該項添加到其左側子樹，導致不平衡的子樹必須從當前節點左移左側。這有幫助嗎？ – niklon

是的，我想我明白了。我需要首先實現這一點，但如果它確實有效（意思是我明白了你的意思），我會選擇你的答案，否則我會更新這個問題。無論如何，謝謝。 – Kalec

如何，如果你需要一個右右旋轉或向右向左旋轉

回答

相關問題