AVL ツリーの再調整に根本的な問題があるかどうか疑問に思っています。いくつかのチュートリアルによると、AVL 挿入の場合、最大 2 回転でバランスを取ることができます。ただし、バランスと呼ばれるものに依存する場合があります。ツリーを見るにはリンクをたどってください。
もともとは6つの要素を持っています。最後の値を 3 または 4.5 または 5.5 または 6.5 として挿入したとします。とにかく、下の左側に挿入されます。合計 7 要素ツリーなので、バランスをとるために 3 行のみと見なします。
これにより、新しいルートが強制的に 6 または 6.5 になります (6.5 を挿入した場合)。2回転以内にバランスを取り戻す方法が本当にわかりません。「バランス」の定義のみに依存する場合、4 行は依然としてバランスが取れていると呼ばれますが、検索時間が長くなります。
何か不足していますか？
写真が削除された場合に備えて、以下はテキスト バージョンです。
7
5 9
4 6 8 Empty_slot
3 または 4.5 または 5.5 または 6.5