控制元素插入紅黑樹的Java TreeSet方法

Question

我真的很想深入理解一個TreeSet，特別是不使用比較器的無參數版本，是如何保持它包含的元素的。我無法在任何地方找到令人滿意的解釋。他們要麼對我來說太基本，要麼太先進。從我的研究中看來，TreeSets實際上將其元素存儲在TreeMap中，而TreeMaps實際上是紅黑樹。我對我對如何將元素添加到紅黑樹上的理解充滿信心。

我假設在java API的某個地方必須有一個算法或方法來執行元素插入到紅黑樹中。我的第一個問題是該算法在Java API中的位置？

此外，該算法究竟是如何調用的？我想它是由TreeSet類中的add（E e）方法調用的，對嗎？有人可以提供更多關於在向樹集添加元素時發生的確切事件鏈的詳細信息。最後，就像一個實驗，我給了一個對象一個compareTo（）方法，但是DID不實現Comparable接口。嘗試將這些對象添加到TreeSet時，會引發異常。我想知道爲什麼即使對象有一個compareTo（）方法也會引發異常。我想在插入算法中有一個方法需要所有對象實現Comparable，這是正確的嗎？拋出異常的stackTrace指向TreeMap.compare（）方法。我想這是要求所有添加到TreeSet中的對象實現Comparable接口但我無法在API中看到這個TreeMap.compare（）方法的方法。如何在API中找到關於此TreeMap.compare（）方法的更多信息？

非常感謝您的幫助。

Answer 1

1. 的TreeSet/TreeMap的無參數版本確實使用Comparator，特別是自然順序比較器（Comparator.naturalOrder()在Java中8）。這意味着密鑰類型必須是Comparable<?>，因爲這可以清楚地說明該類的實例可以相互比較。

2. Java是一種強類型語言，這意味着變量類型優先於其包含的方法。如果有人決定在班上幾年內重新命名compareTo方法，但沒有意識到它在Comparable上下文中使用（如果這是一個大型系統，這是非常合理的），這會導致痛苦和痛苦。聲明從一開始就表達了這種意圖。

Answer 2

請參閱TreeMap source code。具體來說，跳轉到2039。這是與Java的版本8更新40相對應的源代碼。

在那裏你可以考慮所有的紅黑色機制。基本上，或多或少如您所說：寫入方法會觸發樹的節點重新平衡。

關於compareTo方法，TreeSet/TreeMap的元素必須實現Comparable接口。實施compareTo方法對此不夠，元素必須是明確的子類型Comparable。