java - Java で独自のツリーセットを実装する

Question

独自の Java ツリーセットを実装しています。基になるデータ構造は BST であり、ツリー内の各ノードにはオブジェクト型のデータ フィールドが含まれていると思います。ただし、自然順序付けコンパレーターを使用して 2 つのオブジェクト型データを比較する方法に固執しました。2 つのオブジェクトを比較して自然順序付けの値を返す compareTo 関数はありますか? また、ハッシュコードを各ノードのインデックスキーとして使用し、それに基づいて比較を行うことも考えています。しかし、個別のオブジェクトが同じハッシュコードを持つ可能性があるようです。アドバイスをいただければ幸いです。

Answer 1

BST の代わりに RBT (Red black tree) を検討してください。詳細については、こちらを参照してください。

これで、MyTreeSet は 2 種類のオブジェクトを取ることができます。1. String、Integer、Long などのラッパー クラスを指定した Java のオブジェクト または 2. 独自に作成したカスタム クラスのオブジェクト。

データ構造がケース 1 をサポートする必要がある場合は、指定されたすべての Java ラッパー クラスによって実装される compareTo メソッドに基づいて簡単に注文できます。戻り値 0、負の値、正の値に基づいて、どのオブジェクトが他のオブジェクトよりも大きいか、等しいか、または小さいかを知るには、compareTo メソッドを呼び出すだけです。

ケース 2 の場合、MyTreeSet がカスタム クラスのオブジェクトも取得する必要があることを意味します。次に、Comparable インターフェイスをカスタム クラスに実装し、そこに比較アルゴリズムを記述する必要があります。たとえば、MyTreeSet が Employee クラス オブジェクトを取得する必要がある場合は、Comparable メソッドを Employee クラスに実装し、emp1 を emp2 と比較する方法に基づいて compareTo メソッドの実装を記述します。従業員 ID に基づいて並べ替えることができます。

お役に立てば幸いです。