algorithm - AVL ツリー バランス

Question

AVL ツリーを実装しましたが、問題があります。

次のツリーがあるとします。

そして、別のノードを追加した後:

ここで、node5 を左に回転させる必要があります。

しかし、回転後はまだアンバランスです。

どこで間違いを犯していますか？

Answer 1

より包括的に分析してみましょう。二分木が avl 木であるためには、左端の葉から右端の葉までの各ノードの高さの差が {-1, 0, 1} 以内でなければなりません。

AVL の挿入:

AVL 挿入には、L - L L - R R - R R - L の 4 つのケースがあります。

さて、ケース (a)。[if balance > 1] LL(left - left) ノード X は {-1, 0, 1} 制約に違反し、左の高さが右よりも大きい - L の最初の左を与える 左の高さがより大きい左サブ子 Y を持つ右より.. 再び L アクション - Y を中心に時計回りに回転します。すなわち。右一回転。

ケース (b) (L -R ケース) いくつかの Z ノードが挿入されると仮定します。Z については、最初に評価され、左または右の葉に配置されます。重量が多い場合は右、重量が少ない場合は左。たとえば、Z'、新しいノード、wt(Z') > wt(Z)、つまり、Z' は Z の右の子として挿入されます。L - R の場合、リンク ZZ' 全体が反時計回りに回転します。 LL ケースであるため、上記のケース (a) を使用して解決されます。すなわち。左に 1 回、次に右に 1 回回転します。

ケース (c) [残高 < -1 の場合] (R - R ケース) 同様に、R - R ケースは、単純に二分探索法を調整に適用すると、このケースが機能します。すなわち。左一回転。

ケース (d) (R - L ケース) 最初に RR ケースに変換されるため、上記のケース (c) を使用して解決されます。すなわち。右に 1 回、次に左に 1 回回転します。