問題タブ [binary-tree]

どちらに時間がかかりますか？

バイナリ検索ツリーに格納されているすべてのアイテムを並べ替えられた順序で印刷するか、ハッシュテーブルに格納されているすべてのアイテムを並べ替えられた順序で印刷します。

ハッシュテーブルが正しくソートされないため、ハッシュテーブルのアイテムをソートされた順序で出力するのに時間がかかりますか？そしてBSTは？

空の二分探索木 n^2 に N 個の項目を挿入する最悪のケースが big-O になるのはなぜですか? 残高チェックはありません。

1000 個のランダムな int を追加するときに、二分探索木の平均高さをどのように計算しますか? 平均身長は？

C++ での二分探索ツリーの実装に関して質問があります。以下、質問です

整数を格納する単純な (テンプレート化されていない) BST を実装します。次の操作を提供します: Insert、Remove、inOrder トラバーサル、preOrder トラバーサル、postOrder トラバーサル。

ツリーの処理には再帰ルーチンを使用します。

ノードを処理するには、ノードの内容を出力するだけです。この場合は、ノードに格納されている整数です。

データはテスト ファイルから取得する必要があります。メイン プログラムは、データ ファイルを開いてツリーに挿入し、他のツリー操作を実演する必要があります。

この演習のポイントは、BST を理解していることを示すことです。やり過ぎて、求められていない操作を行う必要はありません。

これまでのところ、ヘッダー ファイルのみを作成しました。誰かが見て、私が正しい方向に向かっているかどうかアドバイスしてもらえますか?

次に、BSTNode.cpp ファイルを作成する必要があります。メールで jediknight80n@hotmail.com までご返信いただければ幸いです。よろしくお願いいたします。

これが問題の二分木です。リーフは a、b、c、d で、エッジには 0 または 1 のラベルが付いています。

すべてのノードがリーフであるか、2 つの子ノードを持っているため、これは完全なバイナリ ツリーのように思えますが、完全なバイナリ ツリーではないと言われているような気がします。そうでない場合、なぜそうではないのですか?

ノードにリーフである子がある場合、それは子ノードとしてカウントされませんか?

ソートされたツリーとは何か、バイナリ ツリーと avl および and and ... を理解しようとしましたが、ソートされたツリーがソートされる理由はまだわかりません。また、ソートされたツリーでの検索とソートされていないツリーでの検索の複雑さ (Big-Oh) は何ですか? あなたが私を助けてくれることを願っています。

少なくともO(log n)挿入、削除、アクセス、およびマージを行うマップ データ構造はありますか?

AVL 木や赤黒木などのほとんどの自己均衡二分木は、これらの特性のほとんどを備えていますが、それらには融合があると私は信じています。マージが高速なデータ構造はありますか?O(n log n)

編集：私は周りを見回しましたが、このようなものは見つかりません。そのようなデータ構造がない場合、なぜこれが不可能なのかについての洞察が欲しいです。

リレーショナル データベースには、明らかに外部キー関係のために互いに依存しているテーブルがたくさんあります。依存関係ツリーを構築し、それをトラバースして、INSERT SQL ステートメントを出力したいと考えています。親テーブルは外部キー識別子テーブルの値に依存するため、最初に依存関係ツリー内の外部キー テーブルの SQL を出力する必要があります。

ポストオーダーでたどる二分木は、このタスクに適しているように見えますか?

2 つのバイナリ ツリーがある場合、すべてのノードの要素が等しいかどうかを確認するにはどうすればよいでしょうか。

この問題を解決する方法についてのアイデアはありますか?

再帰を使用せずに、バイナリツリー（バランスの取れたもの、またはBSTではない）のノードの深さを取得する方法を誰かが指摘できますか？理想的にはJava/C / C＃で

ノードは次のように表されます。

FIFOリストでレベル順序を使用することは私の最初の考えでしたが、特に不均衡なツリーの場合、レベルがいつ変化するかを検出することに困惑しました。