問題タブ [avl-tree]

この avlRotate 関数を使用するたびに、ツリーからいくつかの要素が削除されます。z は不均衡が検出されたノード、y はより高い高さを持つそのサブツリー ノード、x は新しく挿入されたノードです。この関数は、1 回の挿入の直後に呼び出されます。

関数は次のように呼び出されます。

挿入機能で。

出力：

この関数で明らかに間違っていることはありますか?

注:各ノードには範囲が格納されます。3 to 5.

本質的にハッシュベースのルックアップである現在のインデックス作成の実装よりも高速であるかどうかをテストしたいので、インデックス作成にツリー構造を使用して実験することを考えています。

Bツリー、AVLツリー、赤黒ツリーのパフォーマンスに関するさまざまな質問や記事を読んだことがありますが、パフォーマンスの面でそれらの違いはあまりわかりません。

人々が推奨するツリー構造とその理由は何ですか？理想的には、既存の.Net実装が利用可能である必要がありますが、必要に応じて独自の実装を行うことを嫌がりません。

AVLツリーの実装を作成しましたが、AVLツリーは非常に複雑な構造であるため、テストする必要があります。だから問題は-どうすればそれをテストできますか？

この瞬間まで、私は次のテストを行っています。

1. 基本的な健全性チェック-すべてのノードの高さが最大に等しいことをチェックします。子ノードの高さ+1、バランスは[-1、1]、左の子のキー<このノードのキー<右の子のキー、循環参照はありません（ノードの左の子がノード自体であるように）。

2. AVLツリー（および全体としての二分探索木）での順序どおりの走査が、基になるセットからの値を順番に返すことを確認します。

3. AVLツリーの高さが厳密に1.44*log2（N + 2）-1（Nは要素の数）未満であることを確認します-AVLツリーの作成者によって証明されました。

4. ビジュアルチェック-うまく機能しません。ツリーを描画しようとします（最初の行にルートノード、次の行に彼の直接の子、3行目にルートノードの直接の子の子など）が、それはでのみ機能します小さな木、大きな木にとっては完全な混乱になります。

5. ロシアのウィキペディアは、2回の挿入で1回のリバランスが必要であり、5回の除去でも1回のリバランスが必要であることが実験的に証明されていると述べていますが、本当にそうですか？英語版ウィキペディアはそれについて何も述べていません。私のAVLの場合、2回の挿入または4回の削除に1回のリバランスが必要でしたが、これはまったく同じではありません。

これらのテストで十分かもしれませんが、実装するのが難しくないテストが他にある場合は、それを実行してみませんか？

クラスの AVL ツリーのバランスを取る方法を見つけようとして、最も苦労しています。私はこれを挿入しました：

私の計画は、balance() の呼び出しでツリーのバランスが必要かどうかを確認し、必要に応じてバランスを取ることでした。問題は、ツリーをトラバースして正しい不均衡ノードを見つける方法さえ理解できないことです。ツリーを再帰的にトラバースする方法は知っていますが、そのアルゴリズムを変換して、最も低い不均衡なノードを見つけることができないようです。反復アルゴリズムの作成にも問題があります。どんな助けでも大歓迎です。:)

x (百万) 個の正の整数があり、それらの値は許容される最大値 (+2,147,483,647) にできます。それらが一意であると仮定すると、ルックアップ集中型プログラムのためにそれらを保存する最良の方法は何ですか.

これまでのところ、整数がマップされたデータ (名前) のキーであるバイナリ AVL ツリーまたはハッシュ テーブルを使用することを考えました。ただし、ハッシュテーブルを使用してそのような大きなキーを大量に実装できるかどうかはわかりません（衝突が発生しやすくなるだけでなく、0.8以上の負荷係数が発生しませんか？）

私の状況に適したデータ構造についてアドバイスをいただけますか

AVL についていくつか質問があります。整数の avl ツリーを作成したと仮定しましょう。最長の数列を取り出すために、ツリーへの挿入をどのように管理する必要がありますか (挿入は複雑さ O(logn である必要があります) ））、 例えば：

この場合、最長のシーケンスは 6,7,8 になるため、関数void sequence(int* low, int* high)では * low = 6, *high = 8...を実行します。

関数 (シーケンス) の複雑さは O(1) でなければなりません

任意のアイデアを前もって感謝します

2 つの AVL ツリーがあり、それぞれのサイズがわかっているとします。ただし、ノードが繰り返されているかどうか、またはその他の情報があるかどうかはわかりません。それらを新しい AVL ツリーにマージする最も効率的な方法は何ですか? 元の木は破壊することができます。

特別な要件を持つAVLツリーに基づいてランクツリーを作成しようとしています。ノードを含むAVLツリーがあり、各ノードに2つのフィールドがあると仮定します。

私のAVLツリーはidでソートされており、次の関数もあります。

currentIdこの関数によって以下のすべてのIDの優先度を下げると、複雑さO（log n）で機能する必要があるため、私の質問は、ノードをatでdelta ポップできるようにするためにどの追加情報を格納する必要があるかです。highest priority任意の段階with complexity O(1)（fooも使用した後！）。

P.S.右側のサブツリーに最大優先度、左側のサブツリーに最大優先度に関する情報を保存しようとしましたが、その後に多くの変更が必要fooです。O（log n）以上のものが必要になります。木についての良いアイデアや良い本を事前に感謝します。

私は次のAVLツリーを持っています：

3を挿入すると、次のようになります。

各ノードのバランス係数を計算すると、すべてのBFが有効であるように見えます:(ノード：BF）-> 10：1、5：0、2：-1、1：0、4：-1、8：0、 7：0、9：0、3：0、12：0、11：0、13：0しかし、どうやらこのツリーはバランスを取り直す必要があります。無効なBFはどこにあり、必要なローテーションをどのように行うのでしょうか。

私は現在、cとアルゴリズムを学んでいます。モックアップ辞書をツリーとして実装しました。コースの作業をもう少し進めて、avlツリーを使用したいと思います。

私はオンラインで実装を探してみましたが、説明がかなり混乱していることがわかりました。このツリー構造をavlツリー構造に変更する方法について誰かが私を正しい方向に向けることができますか？

ありがとう