kdtreeのためのC++のキーセットをOOで実装する方法

Question

k -dツリーに適合したB +ツリーを実装する必要があります。 の説明として、k -dツリーは、その ノードに複数の値を持つキー、つまりいくつかの値を持つキーがあるという点を除けば、バイナリツリーと似ています。そして、 もB +ツリーになるでしょう。内部ノードは鍵の値の のうちの1つを格納することを意味し、実際のデータはリーフノードに格納されます。ここでの短い グラフィカルな説明です：

私は第三を追加し、私は分割をしなければならないまで、正常に動作します 最初の2のすべてを追加したときに私のリーフノードは、2つの要素のためのスペースを持っています。そのためには、私は は、順序を定義するキーの最初の値を選択するので、私は すべての3つの要素の中央値を取ると結果は27ですので、すべての要素 は、右側に行くよりも大きいか等しい。

トムとリンダの年齢が27歳未満であるため、 は既に葉ノードを完成させています。息子を追加すると、ノードが再び分割されますが、今回はキーの値を切り替える必要があります 社会保障番号の順番を定義します。再び中央値をとり、結果は530であるので、 はSS番号が530未満のものはすべて左に移動します。

最後のk -dツリーとなります。 内のインデックスとなるキーの特定の値と、リーフノードの完全キーです。

は

は今、私の質問は、コンテキストを説明した後、どのように私は 完全なキーをノードIが葉で保存しなければならないことを考えると、キーの ソリューションを実装することができますされていますが、内部のノードで私は一つだけを使用します キーの値のうちの1つです。

複数のフィールド に値があるデータベースとの類似性に気付くことができます。異なるフィールドで情報を並べ替えることもできます（同じ の時刻、次のものより重要なものなど）。

私は は、すべての値を保持することをatributesで、上記の例のために、それは SSNumberと名のstringのための年齢のためのintとint可能性があり、Keyまたは他の名前という名前classを行うことを考えました。しかし、私の問題は、私のクライアントが彼に決定した場合、 はさらに値を追加したいと考えています。そして、私のクラスはますます大きくなるでしょう。これは 良いOOの決定ですか？私はこれを別の方法で実装しても、依然としてOOですか？私は 想像力が貧弱かもしれないことを知っていますが、私はクライアントがより多くの値を求めていると思うので、私は が私の値を保持するリストを作ることができました。 OO のようには聞こえません。何か案は？

また、ツリーのアルゴリズムのある時点で、 がツリーのインデックスとして使用するキーの属性を1つ取る必要があるため、これを追加する必要があります。 もこれをサポートする必要があります。

私はOO のアプローチに従うことでこれを解決する方法のアイデアに本当に感謝しています。

Answer 1

KeyをKeyPartの配列にすると、各タイプのキー値（age、ss＃）はKeyPartからサブクラス化できます。ツリーの各内部ノードには、単一のKeyPartとキーパーツインデックス（どの部分が分割されているかを知るために）を格納できます。葉は完全なKeyを保存することができます。