問題タブ [tree-balancing]

そのため、AVL ツリーのバランスをとる方法を理解するのに苦労しています。回転については理解していますが、ノードの高さのバランス係数を見つける方法がわかりません。たとえば、次のようになります。

http://i.imgur.com/yh5zNIl.png

各ノードのバランス係数を実際に見つける方法を誰か説明してもらえますか?

[(左のサブツリー) - (右のサブツリー)] の高さが (-1<= x <= 1) 内にない場合、バランスが取れていないことはわかっていますが、「x」を見つける方法がわかりません。

（編集：コードは必要ありません。BFを見つける方法を理解したいだけです）。

ノードが独自のバランス係数を単一の整数として格納するような AVL ツリーがあるとします。

左右両方の子のバランス係数がわかっている場合、ノード N のバランス係数を計算するにはどうすればよいですか。

rHeight と lHeight がないことに注意してください。そのため、 bal(N) = lHeight - rHeightはオプションではありません。

バランスの取れていない BST があるとします。BST は配列に格納されます。ここで、はインデックス 0 にあり、インデックスkrootのノードの左と右の子は、それぞれインデックス2kと2k + 1にあります。たとえば、ツリー:

配列に格納され[5, 3, nil, 2, 4, nil, nil, 1, nil, ...]、結果検索ツリーの最大高さが最小になるようにバランスを取りたい(=データを格納するのに必要なレベルよりも多くない)。
たとえば、配列内の値の間にギャップがなく、すべての nil 値が後ろに「プッシュ」されるツリーなどです (注: このツリー定義は、前の段落の目標よりも実際には制限的です)。たとえば、上記の[4, 2, 5, 1, 3, nil, ...].
そのようなアルゴリズムはありますか？そうでない場合、少なくとも「良い」ツリーのバランスをとる同様のアルゴリズムはありますか。

追加情報:
- アルゴリズムはインプレースである必要があり、O(1) の追加メモリのみが許可されます -この
質問で 言及されているアルゴリズムがありますが、ポインターの交換に依存しています (配列は 2^n の大きさである必要があります)
- 非常によく似た質問がありましたが、残念ながら受け入れられた答えは、木に関する一般的な話です。(AVL バランス ツリーのメタデータを持っていませんよね? 間違っている場合は、間違っていることを証明してください)
- そのようなアルゴリズムが存在しないという回答も受け入れられます。 /証明または論理的仮定

AVL バランス バイナリ ツリーを作成するコードを作成しようとしています。目的は、新しいノードが挿入されるたびに (AVL) バランスを維持するためにサブツリーを回転させることです。

(ノードの左側のサブツリーのすべての値は、このノードの値より小さくなければなりません。ノードの右側のサブツリーのすべての値は、このノードの値より大きくなければなりません)

私が書いたばかりのコードは、特定の順序で挿入された番号では機能しますが、他の順序では機能しません。たとえば、次の入力は正常に機能します。

これはしません:

なんで？