問題タブ [binary-tree]

スティーブ・エッゲのシングルトンに関する記事を読んでいました。その中で彼は、先生がAVL木は悪だと言ったと述べています。赤と黒の木がより良い解決策であるというだけですか？

JavaでIntervalTreeまたはRangeTreeの実装が必要ですが、削除サポートが機能しているものを見つけるのに問題があります。

sun.jvm.hotspot.utilities.IntervalTreeに組み込みのものがありますが、RBTreeスーパークラスのdeleteNodeメソッドは次のように述べています。

ツリーからノードを削除しようとすると、例外がスローされます。

ノードの最大エンドポイントが正しく更新されませんでした

deletesun.jvm.hotspot.utilities.IntervalTreeのサブクラスに機能を適切に実装することはどれほど難しいでしょうか。または、これをすでに正しく実装している別の区間木実装はありますか？

現在、私はツリーを一掃し、削除があるたびに再入力しています。これは理想からはほど遠いです（注：RBTreeでDEBUGGING = falseを設定すると、処理が大幅に高速化されます）。

いくつかの整数値を使用してバイナリ ツリーを作成しました。コードでツリーを検索できます。しかし、ノードの削除操作を続行する方法がわかりません。

では、どうすればノードを削除できますか?

再帰的および反復的な C++ での単純なツリー反復の例を探しています。（ポスト、プレ、インオーダー）

ツリークラスでは、アイテムの検索と追加を知っているので、2つのノードを比較すると思います。比較可能にする方法にいくつか問題があります。ツリーにデータ（汎用、その他）を追加すると、Treeクラスが呼び出され、新しいNodeオブジェクトが作成されます。Nodeクラスで変数data/elementを宣言して、タイプE（何でも）でありながら比較可能にするにはどうすればよいですか？真剣に、私は何も結論を出さずに前後に試しました。

与えられた 2 つのバイナリ ツリーの構造と内容が等しいかどうかを調べる効率的なアルゴリズムは何でしょうか?

この質問によると、特定のサイズの異なる探索木の数はカタラン数に等しくなります。それらの木を列挙することは可能ですか？つまり、誰かが次の2つの機能を実装できますか。

（ツリーのバイナリコード（この質問に対する答えの1つ）は、範囲が不明な任意の大きな整数を表すための非常に効率的なコード、つまり整数の可変長コードになるため、私は尋ねます

各コード長の整数の数が1、1、2、5、..（カタラン数列）であることに注意してください。）。

ここでの二分木は、必ずしも二分探索木である必要はありません。
構造は次のように取ることができます -

私が友人と一緒に解決できる最大の解決策は、このようなものでした -この二分木
を考えてみましょう:

順序通りのトラバーサルの結果 - 8、4、9、2、5、1、6、3、7

そして、ポストオーダー トラバーサルは、8、9、4、5、2、6、7、3、1 を生成します。

したがって、たとえば、ノード 8 と 5 の共通の祖先を見つけたい場合は、順序付けされたツリー トラバーサルで 8 と 5 の間にあるすべてのノードのリストを作成します。この場合、たまたま [4, 9 、2]。次に、このリストのどのノードがポストオーダー トラバーサルで最後に表示されるかを確認します。これは 2 です。したがって、8 と 5 の共通の祖先は 2 です。

このアルゴリズムの複雑さは、O(n) (順序/事後トラバーサルの場合は O(n)、配列内の単純な反復にすぎないため、残りのステップは O(n) であると私は信じています)。しかし、これが間違っている可能性が非常に高いです。:-)

しかし、これは非常に大雑把なアプローチであり、場合によってはうまくいかないかどうかはわかりません。この問題に対する他の (おそらくより最適な) 解決策はありますか?

Perl でバイナリ ツリーを作成するにはどうすればよいですか?