問題タブ [tree-balancing]

それはO(1)またはO(logN)ですが、係数は小さいですか?

これが指定されていない場合は、マップ/セットが赤黒または AVL ツリーを使用して実装されているという合理的な仮定に基づいて、少なくとも答えを知りたいと思います。要素を挿入する一般的なアルゴリズムは、次のようなものだと思います。

• 適切な場所を見つける - O(logN)
• 実際の挿入を行います - ?
• 必要に応じてツリーのバランスを取り直します - ?

正しい反復子ヒントを提供すると、最初のステップはO(1)になります。他のステップもO(1)またはO(logN)ですか?

B ツリーは、AVL ツリーのような自己均衡ツリーです。ここでは、AVL ツリーのバランスを保つために左右の回転がどのように使用されているかを確認できます。

そして、HEREは B ツリーへの挿入を説明するリンクです。この挿入手法では、ツリーのバランスを保つために回転は必要ありません。したがって、それはより単純に見えます。

質問: avl ツリーのバランスを保つための同様の (またはローテーションを使用しない他の手法) はありますか?

現在、並べ替えられたリンク リストがあり、void リターン メソッドを使用して、リスト (2 番目のパラメーターと呼ばれます) からバランスのとれた二分探索木を再帰的に構築する必要があります。パラメータとして、LL ヘッド、作成されるルート、およびリストの長さのみを指定できます。

このメソッドは LL に対して破壊的であってはならず、後でツリーをテストするために、printTree と treeDepth があります。

AVL ツリーの再調整に根本的な問題があるかどうか疑問に思っています。いくつかのチュートリアルによると、AVL 挿入の場合、最大 2 回転でバランスを取ることができます。ただし、バランスと呼ばれるものに依存する場合があります。ツリーを見るにはリンクをたどってください。

もともとは6つの要素を持っています。最後の値を 3 または 4.5 または 5.5 または 6.5 として挿入したとします。とにかく、下の左側に挿入されます。合計 7 要素ツリーなので、バランスをとるために 3 行のみと見なします。

これにより、新しいルートが強制的に 6 または 6.5 になります (6.5 を挿入した場合)。2回転以内にバランスを取り戻す方法が本当にわかりません。「バランス」の定義のみに依存する場合、4 行は依然としてバランスが取れていると呼ばれますが、検索時間が長くなります。

何か不足していますか？

写真が削除された場合に備えて、以下はテキスト バージョンです。

つまり、挿入直後に赤黒の木の葉の値を左から右に読み取った場合、その順序は木でバランシング操作を実行した後も同じままでしょうか?

LeetCodeに問題があります。これを解決するために簡単な再帰ソリューションを使用しますが、実行時間が 170 ミリ秒と長すぎます。次に、同様の解決策を見つけましたが、これも再帰的であり、実行時間はわずか約 10 ミリ秒です。なんで？

私の解決策：

私が見つけた迅速な解決策：

ありがとうございました！

「Cracking the Coding Interview」から次の問題を解決しています: 二分木のバランスが取れているかどうかをチェックする関数を実装します。バランスの取れたツリーとは、ノードの 2 つのサブツリーの高さの差が 1 を超えないようなツリーです。

本のサンプル ソリューション (以下にコピー) では、(a) ノードの左と右のサブツリーのバランスが取れている場合、ノードから発するツリーのバランスが取れていると想定しています。(b) ノード自体のバランスがとれている。なぜこれが事実なのか理解しようとしていますか？上記の 2 つの条件が満たされていることは、ノードから発するツリー全体のバランスが取れていることをどのように証明しますか?

ありがとう