優れた安定したC ++ツリー実装とは何ですか？

StackOverflow https://stackoverflow.com/questions/181630

  •  05-07-2019
  •  | 
  •  

質問

誰もが良いC ++ツリーの実装を推奨できるかどうか疑問に思っています。 可能な限りstl互換。

記録のために、私はツリーアルゴリズムを何度も書いたことがあり、それが楽しいことを知っていますが、可能な限り実用的で怠zyになりたいです。したがって、ここでは実際のソリューションへの実際のリンクが目標です。

注：バランスの取れたツリーやマップ/セットではなく、一般的なツリーを探しています。この場合、構造自体とツリーの接続性が重要です。内部のデータだけではありません。 そのため、各ブランチは任意の量のデータを保持できる必要があり、各ブランチは個別に反復可能である必要があります。

役に立ちましたか？

解決

要件については知りませんが、グラフ（ブーストグラフ）構造に主に興味があり、バランスをとる速度などのツリー固有の利点にあまり関心がない場合は、グラフを介してツリーを「エミュレート」することができ、おそらく（概念的に）探しているものに近くなります。

他のヒント

これをご覧ください。

C ++のtree.hhライブラリは、ノードに格納されたデータ上にテンプレート化されたn項ツリー用のSTLのようなコンテナクラスを提供します。さまざまなタイプの反復子が提供されています（ポストオーダー、プレオーダー、その他）。可能な場合、アクセス方法はSTLと互換性があるか、代替アルゴリズムが利用可能です。

HTH

ツリーの代わりにstd :: mapを使用することをお勧めします。

ツリーの複雑さの特性は次のとおりです。

挿入：<！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; O（ln（n））
削除：<！> nbsp; <！> nbsp; O（ln（n））
検索：<！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; <！> nbsp; O（ln （n））

これらは、std :: mapが保証する特性と同じです。
したがって、結果としてstd :: mapのほとんどの実装は、カバーの下にツリー（赤黒ツリー）を使用します（技術的には必須ではありません）。

わかりました。別のツリーライブラリを見つけました。 stlplus.ntree 。しかし、まだ試していない。

（キー、値）ペアがなく、単にキーがある場合は、std :: setを使用します。これは、std :: mapと同じ赤黒ツリーを使用します。

そうではない場合でも、質問がバランスのとれた（何らかの形で、主に赤黒木）二分木だとしましょう。

ベクターのようなバランスの取れたバイナリツリーでは、キーを必要とせずに要素の順序を管理できます（ベクターの任意の場所に要素を挿入するなど）が、

  • 最適なO（log（n））または1つの要素のすべての変更に対してより良い複雑さ（開始/終了およびを<！> amp;イテレータの後に追加/削除）
  • イテレータの指す要素の直接破壊以外の変更によるイテレータの持続性を使用。

オプションで、O（log（n））の複雑さを持つベクトル（要素ごとに1つのsize_tのコスト）のようなインデックスによるアクセスをサポートできます。使用する場合、反復子はランダムになります。

オプションで、いくつかの比較関数によって順序を強制できますが、反復子の永続性により、繰り返し不可能な比較スキームを使用できます（例：渋滞中に任意の車線が変更されます）。

実際には、バランスの取れたバイナリツリーは、すべての単一要素操作に対して理論的な最適なO（log（n））の複雑さを達成しながら、ベクター、リスト、ダブルリンクリスト、マップ、マルチマップ、デキュー、キュー、priority_queue ...のインターフェイスを備えています。

<！> lt; sarcastic <！> gt;これがおそらくc ++ stlが<！> lt; / sarcastic <！> gt;

を提案しない理由です。

特に要素の抽出中に、バランスを適切に管理することが難しいため、個人は一般的なバランスの取れたツリーを実装できません。

バランスの取れたバイナリツリーの実装は広く普及していません。最新の赤黒ツリー（現時点では、削除中のコストのかかる固定された数のツリー再編成による最適なタイプのバランスツリー）は、 implementers <！>＃8217;構造の発明者の初期コードから、反復子の永続性を許可しません。これはおそらく、完全に機能するツリーテンプレートが存在しない理由です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top