5

私はこれをいくつかの論文で見ましたが、AVLツリーのノードを削除すると最大でlog（n）回のローテーションが発生する可能性があると誰かが主張しました。これは、可能な限り偏ったAVLツリーを生成することで実現できると思います。問題はこれをどのように行うかです。これは、除去ローテーションのことを研究するのに大いに役立ちます。どうもありがとう！

4

1 に答える 1

9

最大に偏ったAVLツリーを作成する場合は、次のように帰納的に定義されるフィボナッチツリーを探します。

  • 次数0のフィボナッチツリーは空です。
  • 次数1のフィボナッチツリーは単一ノードです。
  • 次数n+2のフィボナッチツリーは、左の子が次数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-25T05:05:59.657 に答える