問題タブ [avl-tree]

自己平衡二分木に関するいくつかのQ＆Aを読みましたが、それらすべてに精通しているわけではありません。

私が知った最初のものはAVLで、2番目は赤黒木です。

私がよく理解していないことがあります。いくつかの本や記事によると、AVLは赤黒木よりも少し速く検索を実行できます。これは理解できます。

1. では、AVLに対する赤黒木のエッジは何ですか？

2. AVLでは、おそらく挿入のたびにバランスをチェックする必要がありますが、赤黒木ではそのようなことを頻繁に行う必要はありませんよね？

PS：私はSOで似たようなものを検索しましたが、満足のいく答えは得られませんでした。何人かの友人が私に自己平衡木の詳細な比較を教えてくれることを願っています。

Weissによるデータ構造と分析のAVL tresを読んでいます

バランス条件の 1 つは、すべてのノードが同じ高さの左右のサブツリーを持つ必要があることを主張します。空のサブツリーの高さが (通常どおり) -1 に定義されている場合、((2 の k 乗) - 1) ノードの完全にバランスの取れたツリーのみがこの基準を満たします。したがって、これにより深さの小さいツリーが保証されますが、バランス条件が硬すぎて役に立たないため、緩和する必要があります。

例を挙げて、上記のテキストを理解するための助けを求めてください。2. 「これによりツリーの深さが浅くなることは保証されますが、バランス条件が硬すぎて役に立たないため、緩和する必要があります」とはどういう意味ですか?

ありがとう！

私はマーク・アレン・ウェシスによるデータ構造とアルゴリズムのAVLツリーについて読んでいます

リバランスされるノードが X であると仮定します。修正しなければならないケースが 4 つあります (2 つは他の 2 つのミラー イメージです): X の左の子の左のサブツリーへの挿入、右のサブツリーへの挿入X の左の子の、 X の右の子の左のサブツリーへの挿入、または X の右の子の右のサブツリーへの挿入。

バランスは木の回転によって復元されます。

以下は、上記のテキスト スニペットに関する質問です。

1. 著者は、他の 2 つのミラー イメージによって何を意味しますか?
2. 一回転と二回転の対称ケースとは？

ありがとう

いろいろな木を勉強していて、AVL木やスプレー木に出くわしました。私は知りたいです

1. AVLツリーとスプレーツリーの違いは何ですか？
2. これらの房をどのような基準で選択しますか？
3. これらの木のポジティブとネガティブは何ですか？
4. これらの木のパフォーマンスは、大きなO表記でどのようになっていますか？

単純な AVL ツリーを作成していますが、GCC から次のコンパイラ エラーが発生します。

エラー: '*' トークンの前にコンストラクタ、デストラクタ、または型変換が必要です

実装ファイルの最小関数宣言と最大関数宣言の両方でエラーが発生します。

次の 2 つのメンバー関数が問題になっています。

宣言は次のとおりです。

クラスと node_t 構造体の宣言は次のとおりです。

「avlツリーのルックアップアルゴリズム」という用語は少し混乱しています。これをグーグルで検索したところ、avlツリーではなくbツリーに関連するウェブサイトがたくさんあります。

それで、b-treeアルゴリズムはavltreeの同等のルックアップアルゴリズムですか？そうでない場合、「avlツリーのルックアップアルゴリズム」とは何ですか？また、「ルックアップアルゴリズム」とはどういう意味ですか？もちろん、可能であればリンクを教えてください。

私は AVL ツリーの割り当てに取り組んでおり、それらの定義について簡単な質問があります。ソートされたリストが与えられ、そこから O(n) 時間で AVL ツリーを生成する必要があります。私はこれを完了しました (StackOverflow からの他の助けのおかげで!)、私の結果は、有効な AVL ツリーでありながら、提供された例の結果とは異なります。同じソート済みリストから複数の AVL ツリーを生成できますか?

ありがとう！

JavaでAVLツリーのダイアグラムを印刷する必要があります.唯一の要件は、イテレータを使用する必要があり、私の教授からのarbitrary側面を使用できないことです. AVL であるため、ツリーに穴が開いたときに NoSuchElementException を取り除く論理的な方法を見つけることができないようです。助言がありますか？

非常に大量のレコード (400K レコード以上) のソフトウェア表現を探しています

各レコードには 2 つのキーがあります。1 つは下限用、もう 1 つは上限用です。これらの数値は範囲を表します。また、各レコードにはいくつかの情報があり、それを I と呼びましょう。言い換えれば、各レコードは共通のアイテム インデックスを集約し、それらに関するいくつかの共通の説明を持っています。

私のソフトウェアにはアイテム番号が与えられており、その情報を取得する必要があります。

AVL、B-Tress、またはフィボナッチについて考えました。しかし、その膨大な量のレコードには、どちらが最適であると確信しています。私は間違いなくAVL /バランスのとれたAVLを小さなデータベースに使用します.

このavlツリーでは、左右のノードと他のバランス方法を比較したいのですが、開始点では、このコード行のcomparetoではサポートされていません。

私はインターフェースIcomaparableを使用しましたが、誰もがそれに欠けているものを教えてくれますか??????????????