できるだけlopsidedとしてAVLツリーを生成するには？

Question

私はこれをいくつかの論文で見て、誰かが、AVLツリーのノードを削除するときに最大でlog（n）回回転することができると主張しました。私たちはAVLツリーを可能な限り片寄って生成することでこれを実現できると信じています。問題はこれを行う方法です。これは、取り外し回転のことを調べるのに役立ちます。どうもありがとう！

Answer 1

あなたが最大限に偏っAVLツリーを作りたい場合は、次のように帰納的に定義されてFibonacci tree、探している：

• オーダー0のフィボナッチツリーが空です。
• オーダー1のフィボナッチツリーは単一ノードです。次数n + 2の
• Aフィボナッチ・ツリーは、その左の子次数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." 

は、この情報がお役に立てば幸い！