Метод дерева TreeSet, который управляет вставкой элемента в дерево Red-Black

Question

Я действительно хочу углубить свое понимание того, как TreeSet, особенно версия без аргументов, которая не использует компаратор, поддерживает содержащиеся в ней элементы , Я не могу найти удовлетворительного объяснения нигде; они либо слишком базовые, либо слишком продвинутые для меня. Из моих исследований кажется, что TreeSets фактически хранят свои элементы в TreeMap, а TreeMaps на самом деле являются красно-черными деревьями. Я очень уверен в своем понимании того, как элементы добавляются к красно-черным деревьям.

Я предполагаю, что где-то в API Java должен быть алгоритм или метод, который выполняет вставку элементов в дерево Red-Black. Мой первый вопрос: где в Java API находится этот алгоритм?

Также, как именно этот алгоритм вызывается? Я предполагаю, что он вызывается методом add (E e) в классе TreeSet, правильно? Может ли кто-нибудь предоставить более подробную информацию о точной цепочке событий, которые возникают при добавлении элемента в дерево.

Наконец, как и эксперимент, я дал объекту метод compareTo(), но НЕ реализовал интерфейс Comparable. При попытке добавить эти объекты в TreeSet генерируется исключение. Я хочу понять, почему выбрано исключение, даже если объект имеет метод compareTo(). Я предполагаю, что есть метод где-то в алгоритме вставки, который требует, чтобы все объекты реализовали Comparable, это правильно? СтекTrace для брошенного исключения указывает на метод TreeMap.compare(). Я предполагаю, что это метод, который требует, чтобы все объекты, добавленные в TreeSet, реализовали интерфейс Comparable, но я не вижу этот метод TreeMap.compare() в API. Как я могу найти дополнительную информацию об этом методе TreeMap.compare() в API?

Благодарим вас за помощь.

Answer 1

1. версия без аргументов из TreeSet/TreeMap действительно использовать Comparator, в частности естественного порядка компаратор (Comparator.naturalOrder() в Java 8). Это означает, что тип ключа должен быть Comparable<?>, поскольку это дает понять, что экземпляры класса могут сравниваться друг с другом.

2. Java - это строго типизированный язык, что означает, что типы переменных имеют приоритет над тем, какие методы он содержит. Если кто-то решит переименовать метод compareTo в вашем классе через несколько лет, не понимая, что он используется в контексте Comparable (что совершенно правдоподобно, если это большая система), это приведет к боли и страданиям. Объявление implements Comparable<?> делает это намерение понятным с самого начала.

Answer 2

См. TreeMap source code. В частности, перейдите к строке 2039. Это исходный код, который соответствует обновлению версии 8 Java версии 8.

Там вы можете рассмотреть все красно-черные механики. В принципе, это более или менее, как вы предположили: методы записи инициируют перебалансировку узлов дерева.

Относительно compareTo метода, элементы TreeSet/TreeMap должны реализовывать интерфейс Comparable. Для этого недостаточно использовать метод compareTo, элементы должны быть явным подтипом Comparable.