問題タブ [binary-search-tree]

こんにちは私はBSTを書いていて、子を追加するための次の関数を書きました。

入力として「23 12 122 1 121 15」を与えています。ルートは、クラスのコンストラクターで作成しているノード 23 です。

問題:ツリー トラバーサルを行っているときに、出力として 23 と 15 しか得られません。 質問: この関数で何が間違っていますか?

二分探索木の前順トラバーサルが 6、2、1、4、3、7、10、9、11 の場合、後順トラバーサルを取得するにはどうすればよいですか?

私は最近、さまざまな二分探索木の実装 (AVL、splay、treap) をコーディングしており、これらの構造をトラバースするイテレータを記述する特に「良い」方法があるかどうかに興味があります。私が現在使用している解決策は、BST 内の各ノードに、ツリー内の次の要素と前の要素へのポインタを格納させることです。これにより、反復が標準のリンク リスト反復に減少します。しかし、私はこの答えに本当に満足していません。これは、各ノードのスペース使用量を 2 つのポインター (次と前) だけ増やします。

スタックを使用してフロンティア ノードを追跡し、後で探索することにより、O(h) 補助ストレージ スペース (h はツリーの高さ) を使用する二分探索ツリー イテレータを構築する方法を知っていますが、私は'メモリ使用量のために、これをコーディングすることに抵抗しました。一定のスペースのみを使用するイテレータを作成する方法があることを期待していました。

私の質問はこれです-次のプロパティを持つ二分探索木に対して反復子を設計する方法はありますか?

1. 要素は昇順でアクセスされます (つまり、順不同の走査)
2. next()hasNext()クエリは O(1) 時間で実行されます。
3. メモリ使用量は O(1)

簡単にするために、反復中にツリー構造の形状が変化しない (つまり、挿入、削除、または回転がない) と仮定しても問題ありませんが、これを実際に処理できるソリューションがあれば非常にクールです。

重複の可能性:
C/C++ での BST スーパーノードの生成

スーパーノードを使用した二分探索木の生成、追加、および削除の実装を手伝ってくれる人はいますか? C/C++ のアルゴリズムが本当に必要です。

今日、二分木のシリアライズを依頼された面接に行きました。ノード i の子 (レベル順トラバーサルの番号付け) が左の子の 2*i インデックスと右の子の 2*i + 1 にある配列ベースのアプローチを実装しました。インタビュアーは多かれ少なかれ満足しているように見えましたが、シリアライズとは正確には何を意味するのでしょうか? ディスクに書き込むためにツリーをフラット化することに特に関連していますか、それともツリーをシリアル化することには、ツリーをリンクされたリストに変換することも含まれますか。また、ツリーを (二重に) リンクされたリストにフラット化し、それを再構築するにはどうすればよいでしょうか? リンクされたリストからツリーの正確な構造を再現できますか?

natbib で Vim LaTeX を 6 か月使用しましたが、問題はありませんでした。しかし、新しい bib スタイル ファイル (つまり、rfs.bst) を使用するために、harvard.sty を使い始めましたが、2 つの小さな問題が発生します。

(1) 構文の強調表示が完全ではありません。特に の場合\citeasnoun、Vim はその\cite部分のみを強調表示します。別の Vim プラグイン (Vim-plugin-R) を使用すると、構文の強調表示を更新できますが、Vim でこれを行う方法がわかりません。MikTex でデータベースを更新しましたが、うまくいきませんでした。

(2) Vim LaTeX は、参照を正しく取得するために、必要に応じて自動的に再実行されます。Vim のステータス ウィンドウには、複数の実行が行われ、結果は期待どおりであることが示されますが、それでも次の警告が表示されます。

これらを修正するにはどうすればよいですか? ありがとう！

サイズ 1024 のランダムな二分探索木を生成しようとしていて、要素はランダムなソートセットである必要があります。手動で要素を追加することで二分探索木を手動で作成するコードを書くことはできますが、私は ' m サイズ 1024 のバランスの取れたランダムなバイナリ ツリーを生成するコードを作成できず、そのツリーでキーを検索してみてください ... どうぞ、よろしくお願いします ....

コメントから追加されたコードを編集する

それは宿題です...そして、これは私がこれまでコードとして得たものです:

私は C++ の初心者で、BST の最小要素を見つけるのに問題があります。BST は次のように実装されます。

InOrder、Destroy、および Insert メソッドは次のように実装されます。

そして、数字を出力するために使用する主な関数と関数は次のようになります。

お気づきかもしれませんが、InOrder メソッドも実装されており、問題を解決するために何らかの方法で使用できる可能性があります...下手な英語で申し訳ありません:/

TツリーとB-/B+ツリーの定義を調べました。Web上の論文から、ディスクドライブやキャッシュメモリなどの階層メモリでBツリーのパフォーマンスが向上することがわかりました。

私が理解できないのは、フラットメモリでもTツリーが使用された理由です。

それらは、AVLツリーのスペース効率の良い代替手段として宣伝されています。

最悪の場合、Tツリーのすべてのリーフノードには1つの要素のみが含まれ、すべての内部ノードには許容される最小量が含まれます。これはほぼ満杯です。これは、割り当てられたスペースの平均で半分しか使用されないことを意味します。私が誤解しない限り、これは、Bツリーのノードが半分いっぱいになっている場合のBツリーの最悪の場合と同じ使用率です。

両方のツリーがキーをノードにローカルに格納し、ポインタを使用してレコードを参照すると仮定すると、唯一の違いは、Bツリーが各ブランチのポインタを格納する必要があることです。これにより、キーのサイズにもよりますが、通常、最大50％以下のオーバーヘッド（Tツリーに対して）が発生します。実際、これは、親ポインター、ノードに埋め込まれたレコード、レコードに埋め込まれたキーがないと仮定すると、AVLツリーで予想されるオーバーヘッドに近いものです。これは、代わりにBツリーを使用できないようにする期待される効率の向上ですか？

Tツリーは通常、AVLツリーの上に実装されます。AVLツリーはBツリーよりもバランスが取れています。これはTツリーのアプリケーションと関連付けることができますか？

fold（+）0サンプルを実行すると、（+）があまりにも多くの引数に適用されているというエラーが発生します。なんで？

参照：折りたたむ