如何生成儘可能不平衡的AVL樹？

我在一些論文中看到了這一點，有人認爲我們刪除AVL樹的節點時最多可以有log（n）次旋轉。我相信我們可以通過生成儘可能不平衡的AVL樹來實現這一點。問題是如何做到這一點。這將有助於我研究移除旋轉事物。非常感謝！如何生成儘可能不平衡的AVL樹？

來源

2012-01-25 Yuming Cao

另請參閱：http://stackoverflow.com/questions/19622572/how-to-generate-maximally-unbalanced-avl-trees –

如果你想一個最大不平衡的AVL樹，你正在尋找一個Fibonacci tree，這是歸納定義如下：

的0階斐波那契樹是空的。
1階的斐波那契樹是單個節點。
斐波那契樹是其左孩子的n階，其右子斐波那契樹是爲了斐波那契樹N + 1

例如一個節點，這裏有一個斐波那契的順序5樹：

斐波那契樹表示AVL樹可以具有歪斜的最大量，因爲如果平衡因子是任何更多的不平衡每個節點的平衡係數將超過限制放置由AVL樹木。

你可以使用這個定義很容易產生一邊倒最大AVL樹：

function FibonacciTree(int order) { 
    if order = 0, return the empty tree. 
    if order = 1, create a single node and return it. 
    otherwise: 
     let left = FibonacciTree(order - 2) 
     let right = FibonacciTree(order - 1) 
     return a tree whose left child is "left" and whose right child is "right."

希望這有助於！

來源

2012-01-25 05:05:59 templatetypedef

好的答案。如果只是有一個圖像去與它。 – 2012-01-25 05:23:26

（特別注意，每個非葉子具有不同於0的平衡「因子」）。 –

如何生成儘可能不平衡的AVL樹？

回答

相關問題