Red-Blackツリーへの要素の挿入を制御するJava TreeSetメソッド

Question

TreeSet、特にコンパレータを使用しない引数のないバージョンが、その要素が順番にどのように保持されているかを正確に理解したいと思っています。私はどこでも満足のいく説明を見つけることができません。彼らはあまりにも基本的すぎるか、あまりにも進んで私のためです。私の研究から、TreeSetsは実際にTreeMapに要素を格納し、TreeMapsは実際にはRed-Blackツリーであるようです。赤黒の木に要素がどのように追加されているかについての私の理解はかなり確信しています。

私は、Java APIのどこかに、要素をRed-Blackツリーに挿入するアルゴリズムまたはメソッドが必要であると仮定します。私の最初の質問は、Java APIのどこにアルゴリズムがあるのですか？

また、このアルゴリズムはどのくらい正確に呼び出されていますか？私はそれがTreeSetクラスで、右の追加（E e）メソッドによって呼び出されると思いますか？ツリーセットに要素を追加するときに発生する正確な一連のイベントについて、より詳細な情報を提供できますか？

最後に、実験と同じように、オブジェクトにcompareTo（）メソッドを渡しましたが、DIDはComparableインターフェイスを実装しません。これらのオブジェクトをTreeSetに追加しようとすると、例外がスローされます。オブジェクトにcompareTo（）メソッドがあるのに例外がスローされる理由を理解したい。私は、挿入アルゴリズムのどこかに、すべてのオブジェクトがComparableを実装する必要があるメソッドがあると思いますが、これは正しいですか？スローされた例外のstackTraceはTreeMap.compare（）メソッドを指します。これは、TreeSetに追加されるすべてのオブジェクトがComparableインターフェイスを実装することを必要とするメソッドだと思いますが、このTreeMap.compare（）メソッドがAPIで表示されません。 APIでこのTreeMap.compare（）メソッドの詳細を調べるにはどうすればよいですか？

ご協力いただきありがとうございます。

Answer 1

1. TreeSet/TreeMapの引数なしのバージョンは、実際に（ジャワ8 Comparator.naturalOrder()）Comparator、具体的には自然な順序のコンパレータを使用しません。これは、鍵のタイプがComparable<?>でなければならないことを意味します。これは、クラスのインスタンスを互いに比較できることを明確にしているからです。

2. Javaは強く型付けされた言語です。つまり、変数の型が含まれるメソッドよりも変数の型が優先されます。誰かがあなたのクラスのcompareToメソッドの名前を、数年遅れて、Comparableコンテキスト（それが大規模なシステムの場合は完全にもっともらしい）で使用されていることを認識していない行の名前に変更すると、痛みや苦しみにつながります。 implements Comparable<?>宣言は、この意図を最初から明確にしています。

Answer 2

TreeMap source codeを参照してください。具体的には、2039行にジャンプします。これはJavaのバージョン8のアップデート40に対応するソースコードです。

ここで、赤黒のすべての仕組みを考えることができます。基本的には、あなたが示唆したように多かれ少なかれ：書き込みメソッドはツリーのノードの再平衡をトリガーします。

compareToメソッドに関して、TreeSet/TreeMapの要素は、Comparableインターフェイスを実装する必要があります。 compareToメソッドを実装するだけでは不十分な場合、要素は明示的にサブタイプComparableでなければなりません。