AVL樹中的額外情況

AVL樹似乎有四種轉換：左 - 左，左 - 右，右 - 左和右 - 右。但是，似乎也可能有其他情況。我提出這個爲左均衡：AVL樹中的額外情況

沒有留下也不是，右旋轉可以平衡這棵樹。用什麼算法來平衡它？

2015-12-22 Mark Karavan

AV＆L did not Not a procedure to balance to _any_ ordered binary tree into a AVL tree with「maximum one double rotation」。他們介紹瞭如何使用三個狀態/每個節點兩個額外比特中的一個插入單個節點之後重新平衡二叉樹。這被擴展到其他操作。上面顯示的三棵「左」樹中沒有一棵可以是將單個節點添加到有效AVL樹的結果，每個樹可能因刪除一個值得標籤大於50的節點而產生。這就是說，什麼（就高度而言）_is_在「最後兩棵左樹」之間標有40和45的節點中不同？ – greybeard

兩個LL和LR可以在這裏

 50 
    /\ 
    40 55 
    /\ 
    35 45 
/\ /\ 
34 36 44 46

應用後第一LR依次爲：

後第二LR依次爲：

 45 
    /\ 
    40 50 
    /\ /\ 
    35 44 46 55 
/\ 
34 36

這是有效的AVL樹。需要注意的是

在AVL樹，任何節點的兩個子子樹的高度最多由一個

你也可以做LL又將有所不同：

 40 
    /\ 
    35 50 
/\ /\ 
34 36 45 55 
     /\ 
    44 46

這又是一個有效的AVL樹。

來源

2015-12-22 06:08:51

我認爲你不能得到左平衡的情況。因爲如果你建立了左邊平衡點，你可能會先左右或左右，然後樹會旋轉並保持平衡。

來源

2015-12-22 04:46:28 lancelot

您可以得到每個所描述的情況，從有效AVL樹的右子樹中刪除單個節點。 – greybeard

AVL樹中的額外情況

回答

相關問題