バランスの取れていない BST があるとします。BST は配列に格納されます。ここで、はインデックス 0 にあり、インデックスkrootのノードの左と右の子は、それぞれインデックス2kと2k + 1にあります。たとえば、ツリー:
5 4
/ / \
3 --balancing--> 2 5
/\ / \
2 4 1 3
/
1
配列に格納され[5, 3, nil, 2, 4, nil, nil, 1, nil, ...]、結果検索ツリーの最大高さが最小になるようにバランスを取りたい(=データを格納するのに必要なレベルよりも多くない)。
たとえば、配列内の値の間にギャップがなく、すべての nil 値が後ろに「プッシュ」されるツリーなどです (注: このツリー定義は、前の段落の目標よりも実際には制限的です)。たとえば、上記の[4, 2, 5, 1, 3, nil, ...].
そのようなアルゴリズムはありますか？そうでない場合、少なくとも「良い」ツリーのバランスをとる同様のアルゴリズムはありますか。
追加情報:
- アルゴリズムはインプレースである必要があり、O(1) の追加メモリのみが許可されます -この
質問で
言及されているアルゴリズムがありますが、ポインターの交換に依存しています (配列は 2^n の大きさである必要があります)
- 非常によく似た質問がありましたが、残念ながら受け入れられた答えは、木に関する一般的な話です。(AVL バランス ツリーのメタデータを持っていませんよね? 間違っている場合は、間違っていることを証明してください)
- そのようなアルゴリズムが存在しないという回答も受け入れられます。 /証明または論理的仮定