問題タブ [avl-tree]

基本的に、値で満たされた BST があります。例えば。1-16 最小、最大および値 (10,15,3) であり、BST の値とツリーの最小および最大内にある指定された値との間の最大 xor 値を見つける必要があります。

ツリー全体を反復せずにこれを行う方法があるかどうか疑問に思っています。min と max が存在しない場合、私のアプローチは次のようになります。

基本的に、より高い xor 値を生成するノードを追跡し続けます。

私が最小値と最大値で遭遇している問題は、 node>=min && node<=max のチェックを配置すると、ツリーは正常にトラバースしますが、範囲内にいる場合は、範囲外の数値への不適切な分岐。

説明させてください。BST 1-16 のこの右側を取る

与えられた：

• 分 = 10
• 最大 = 15
• 値 = 3

Xor の最大値は3^12=15

ただし、私のアルゴリズムでは、ノードが 13 のとき、左側のツリーを 11 にする代わりに、右側のツリーを 15 にします (16 に到達しようとしているが範囲外であるため)。

誰かがより良い解決策を持っていますか? BSTを別の方法でソートする必要がありますか? BST の代わりに何かを使用する必要がありますか? 値のリスト全体をトラバースせずにこれを行うことは可能ですか? ここでの前提は、1 つの値のリスト (BST に入力したもの) と、値のリストに適用する必要があるパラメーター (最小、最大、値) のリストがあることです。

整数を読み取り、昇順で出力するメイン関数を定義する必要があります。

ただし、これを行うにはツリーを使用する必要があります。私は 2 つの機能insertavlを使用することができdeleteavl、自由に使用できます。それらの定義は次のようになります... http://ideone.com/8dwlU 基本的に、deleteavl が呼び出されると、ノードが削除され、それに応じてツリーのバランスが取り直されます ... 興味のある構造があれば、 http: //ideone.com/にあります。キュールゲ。

私はこれまでにこれを得ました：

しかし、これはそれらを昇順で印刷しません。何か提案は役に立ちますか？前もって感謝します！

AvlTree クラス内にクラス イテレータを実装しました。私の AvlTree ノードは次のとおりです。

私のイテレータは次のとおりです。

私の AvlTree には、パブリック メンバーとして開始イテレータと終了イテレータもあります。

私の問題は、メインで次を実行しようとしたときです。

文字列ツリー内のすべての単語を順番に出力する代わりに、ツリー内の最初の順番のアイテムの無限ループを取得します。最初の項目を通過しない理由がわかりません。

だから私は基本的に関数 avl を持っていますか? その実行はO（n ^ 2）で行われます。これは、再帰するたびに、O（n）関数である高さを呼び出しているためです（nはツリー内のノードの数です）。

私の問題は、avlを作りたいということですか？O(n) 時間で実行します。「適用される BST のサイズに関係なく、高さ関数の呼び出しを一定時間内に制限するようにしてください。このようにして、全体で O(n) の実行時間を得ることができます。」というヒントが与えられました。... 一定時間で身長を伸ばす方法がわかりません。私のAVLを作るための提案はありますか？O(n^2) ではなく O(n) で実行しますか?

重複する要素がツリーに挿入されるたびに再編成される自己順序付けバイナリ検索ツリーを作成する割り当てに取り組んでいます。解決するのに助けが必要なエラーがいくつかあります。

まず、ツリーのルートが変更されることはありません (問題は RotateLeft または RotateRight メソッドにあると想定しています) 私が読んでいるサンプル ファイルがあり、コードを見ていくと、それに応じてすべてが整理されているように見えますが、最初の複製が入ってくると、ルートは優先度の高いノードに変更されることはありません。

私が得ている2番目のエラーはBAD ACCESS ERRORです（以下のコードのどこにあるかを書き留めました）。これもRotateメソッドの1つからのものであると推測しています。

BinaryNode 構造体のコードは次のとおりです。

助けるために私が変更できる何かを見ている人はいますか?

具体的には、AVLツリーローテーションのBig O効率はどれくらいですか？

たとえば、挿入する場合：-O（logN）を使用して位置を検索します-O（1）を挿入します-？バランス調整用（再バランス調整が必要な場合）

O（logN）だと思っていたのですが、O（1）だと主張するサイトを見つけました-読み間違えない限り-http: //users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml

（これは2-3ツリーでも同じでしょうか？）

事前に助けてくれてありがとう

IPアドレスの高速検索にAVLツリーを使用する大規模なシステムがあります。

したがって、検索は「struct nhlfe_key」に基づいています。つまり、AVLツリーのコンパレータ関数は次のようになります。

今、私がやろうとしているのは、複数のネクストホップのサポートを追加することです。つまり、nhlfe_entryにリンクリストを追加します。

各「structlist」は、呼び出し元のプライベートデータへの「void *data」ポインタを埋め込むstructlistnodeであり、これは「structnhlfe_key」です。

だから私の質問は-リストからの複数の要素に基づいてキーを生成し、ツリー内のノードを格納/検索する方法です（そうでなければ、リストを導入した後、 1つ のネクストホップのみに基づいてキーを持つことはできません）住所）。また、同じ質問が検索にも当てはまります。

また、リストに新しいノードを追加した後、この操作によってキーが変更され、ツリーのバランスが崩れる可能性があるため、ツリーを再構築する必要がありますか？（または、正しく実装されたAVLツリーを再構築する必要はありませんか？）

すべてのリストノードでCRCを生成し、合計することを考えています。これはキーの一意性を保証できますか？（欠点は、listnodeを追加/削除するたびに、キーを再生成し、treからノードを削除して、新しいキーで再追加する必要があることです）。

ありがとう！

データ構造コースのジェネリックを保持する AVL ツリーを作成します。私の add() メソッドでは、実際に要素を挿入した後、スコアをチェックしている先祖に戻ります。最初の数回の追加では機能しますが、(おそらくバランス調整を行う必要がある時点で) パスをバックアップするループが終了しません。ツリーの親のルートが別のノードなどに設定されていないことを確認するために、考えられるすべてのことを試しました。バランス スコアは右マイナス左として計算しているため、正は木が右に重く、負は左に重くなることを意味します。ここに私の add() があります:

そして、ここに正しい回転方法があります：

AVLツリーが整数でどのように機能するかは理解していますが、代わりに文字列を整数に挿入する方法を見つけるのに苦労しています。文字列はどのように比較されますか？

ASCIIの合計値を使用してそのように並べ替えることを考えましたが、その場合、2つの同一のASCII単語（「tied」と「diet」など）を挿入するとエラーが返されるように見えます。

これをどのように回避しますか？私はそれについて間違った方法で考えていて、ノードをソートするための別の方法が必要ですか？

また、アルファベットなどである必要はありません... AVLツリー内にあるだけなので、すばやく検索できます。