誰かが良い C++ ツリーの実装を推奨できるかどうか疑問に思っています。
記録として、私はこれまで何度もツリー アルゴリズムを作成しており、それが楽しいものであることはわかっていますが、可能であれば実用的で怠惰になりたいと思っています。したがって、実用的なソリューションへの実際のリンクがここでの目標です。
注:バランスの取れたツリーやマップ/セットではなく、一般的なツリーを探しています。この場合、内部のデータだけでなく、構造自体とツリーの接続性が重要です。したがって、各ブランチは任意の量のデータを保持できる必要があり、各ブランチは個別に反復可能でなければなりません。
私はあなたの要件については知りませんが、主に構造に興味があり、バランシングによる速度などのツリー固有の利点にあまり興味がない場合は、グラフ (たとえばBoost Graphの実装) を使用したほうがよいでしょうか? ? グラフを介してツリーを「エミュレート」できます。おそらく、探しているものに (概念的に) 近いものになるでしょう。
これを見てください。
C++ の tree.hh ライブラリは、ノードに格納されたデータをテンプレート化した、n 分木用の STL に似たコンテナー クラスを提供します。さまざまなタイプの反復子が提供されています (ポストオーダー、プリオーダーなど)。可能な場合は、アクセス方法が STL と互換性があるか、代替アルゴリズムが利用可能です。
HTH
ツリーの代わりに std::map を使用することをお勧めします。
ツリーの複雑さの特徴は次のとおりです。
挿入: O(ln(n))
削除: O(ln(n))
検索: O(ln(n))
これらは std::map が保証する特性と同じです。
したがって、結果として std::map のほとんどの実装は、カバーの下にツリー (赤黒ツリー) を使用します (ただし、技術的にはこれは必須ではありません)。
わかりました、別のツリー ライブラリを見つけました。stlplus.ntree。しかし、まだ試していません。
(キー、値) ペアがなく、単にキーがある場合は、std::set を使用します。これは、std::map と同じ赤黒ツリーを使用します。
たとえそうでなくても、質問がバランスの取れた (何らかの形で、ほとんどが赤黒木) 二分木に関するものであるとします。
ベクトルのようなバランスのとれた二分木は、キーを必要とせずに要素の順序付けを管理することを可能にします (ベクトル内の任意の場所に要素を挿入するなど)。
必要に応じて、O(log(n)) の複雑さで、ベクトル (要素ごとに 1 size_t のコスト) のようにインデックスによるアクセスをサポートすることができます。使用すると、反復子はランダムになります。
オプションで、いくつかの比較関数によって順序を強制できますが、イテレータの永続性により、繰り返し不可能な比較スキームを使用できます (例: 交通渋滞中に任意の車線が変更されます)。
実際には、バランスの取れたバイナリ ツリーには、ベクトル、リスト、ダブル リンク リスト、マップ、マルチマップ、デキュー、キュー、priority_queue... のインターフェイスがあり、すべての単一要素操作に対して理論的に最適な O(log(n)) の複雑さを達成します。
<皮肉> これがおそらく c++ stl がそれを提案しない理由です </皮肉>
個人は、特に要素の抽出時にバランスを正しく管理することが難しいため、一般的なバランス ツリーを自分で実装することはできません。
バランスの取れたバイナリ ツリーの広く利用可能な実装はありません。これは、最先端のレッド ブラック ツリー (現時点では、除去中のコストのかかるツリーの再編成の回数が固定されているため、バランスのとれたツリーの最適なタイプ) が実装を認識しており、すべての実装者によって惜しみなくコピーされているためです。構造発明者の初期コードでは、反復子の永続性が許可されていません。これはおそらく、完全に機能するツリー テンプレートがないことの理由です。