c++ - BST の実装に関する小さな問題

Question

二分探索木用のSTLライクなコンテナを書いています。Tree 自体のテンプレート クラスとネストされたクラス TreeNode があります。
私の質問は、キーを比較するバイナリ述語関数をツリークラスまたはノードクラスのどこに配置する必要があるかです。Tree クラスに入れることにした場合、すべてのノードはキーを比較する方法を知りません:(
そして、Node クラスの場合、この関数を静的にする必要がありますか?

Answer 1

静的にできないことは明らかです。そうすると、2 つの異なる比較関数を持つ 2 つの異なるツリーが機能しなくなります (後のツリーがグローバルを上書きします)。

また、ノードごとであってはならないことも明らかです。まったく同じ機能をノードごとに複製することになり、理由もなく、1 つのツリー内のすべてのノードが同じ比較子を持つことになります。

したがって、最良の選択は、コンテナーの一部にすることです。ノードが自分自身を比較できないというあなたの異議については、なぜそれが重要なのですか? 2 つのノードを比較するのは、コンテナーに対する操作のコンテキスト内だけです。その場合、comparer オブジェクトが便利です。

Answer 2

ノード自体の間ではなく、ノード内に格納されている値の間で比較を行う必要があります。したがって、推奨される場所のいずれにもコンパレータは必要ありません。ツリー（およびノー​​ド）のテンプレート化されたパラメーターとしてコンパレータークラスを取得するか、ノード内に保持されている値を比較するときにデフォルトのクラスに依存することができます。