問題タブ [binary-search-tree]

C で作成されたバイナリ検索ツリーがあります。問題は、id>5 などのすべてのノードを効率的に削除する方法が見つからないことです。

ツリーをトラバースするときにノードを削除すると、構造が同じではないため、再帰でエラーが発生します。

ツリーからデータを削除する前に、補助スタックを使用してデータを保持する代わりに、方法はありますか?

次の二分探索木（BST）の実装の何が問題になっていますか？struct挿入関数の引数として、ノードへのポインタへのポインタを使用する方がよいと言われています。

私はこのコードフラグメントを持っています

insert関数を呼び出すと、insert(5); insert(8);常に出力されroot is nullます。

どうしたの？？

二分探索木をいつ使用するか、いつ辞書を使用するかという概念に苦労しています。

私のアプリケーションでは、C5ライブラリTreeDictionary（赤黒木であると私は信じています）とC＃辞書を使用した小さな実験を行いました。辞書は、追加/検索操作で常に高速であり、また、常により少ないメモリスペースを使用していました。たとえば、16809<int, float>エントリでは、ディクショナリは342 KiBを使用し、ツリーは723KiBを使用しました。

BSTの方がメモリ効率が高いと思いましたが、ツリーの1つのノードには、辞書の1つのエントリよりも多くのバイトが必要なようです。何が得られますか？BSTが辞書よりも優れている点はありますか？

また、副次的な質問として、<int, float>辞書タイプのアクセス用のペアを格納するための、前述の構造のいずれよりも高速でメモリ効率の高いデータ構造があるかどうかを誰かが知っていますか？

これは、BST をトラバースし、ルート ノードを含むすべてのノードを削除することになっています。しかし、最後に「ルートにはまだノードが残っています」というメッセージが表示されます。すべてのノードが削除されないのはなぜですか?

木の高さを計算しようとしています。私は以下に書かれたコードを使いこなしています。

それは私に正しい結果を与えます。しかし、一部の投稿（googledページ）では、ポストオーダートラバーサルを実行し、この高さメソッドを使用して高さを計算することが提案されました。特定の理由はありますか？

「ifright[x]！= NIL then return tree-min」の意味を知っており、次のように翻訳しました。

残りは私が理解するのに苦労しています。

サポートの重複キーを作成したいavl-treeのですが、with duplicates のデフォルトの動作に問題がありbinary search tree、ローテーションによって同じキーを持つノードが親の左右に配置される可能性があります。

たとえば、すべてキー A を持つ 3 つのノードを追加すると、ツリーは次のように回転します。

したがって、そのキーですべてのエントリを取得することは問題になります...そして、双方向の検索は良くありません。

私が考えた解決策は、各ノードに重複の配列を格納することです。そのため、既に存在する新しいアイテムを追加すると、新しいアイテムが配列に追加され、キーでアイテムを削除するとノード全体が削除され、すべてのアイテムが検索されますwith key はその配列を返します。

重複を処理する他の方法はありますか?

挿入項目はキーと値を受け取ります..したがって、特定のキーメソッドを使用してfindAllで値を返すために、値を保存する必要があります。

私はCにまったく慣れていないので、数値と文字列を格納してから出力するバイナリツリーをCに実装しようとしています。

私がこれまでに持っているコードは次のとおりです。

現時点ではints で動作しているようですが、最後に入力した説明部分のみが出力されます。char配列のポインターと関係があると思いますが、うまく機能しませんでした。アイデアやアドバイスはありますか？