Java 提供了大量的資料結構來有效地處理元素集合。其中一種資料結構是 TreeSet，它是 Java 中紅黑樹的實作。TreeSet維護儲存唯一元素的排序順序。初學者可能會發現最初使用 Java TreeSet類別有點困難。在本文中，我們將了解如何使用TreeSet，解釋其核心概念並提供程式碼範例來幫助您開始將TreeSet合併到 Java 專案中。
TreeSet結構：紅黑樹
正如我們之前提到的，Java TreeSet類別結構被實作為一種稱為紅黑樹的自平衡二元搜尋樹。讓我們解釋一下這是什麼...紅黑樹代表一種平衡的二分搜尋資料結構，通常用於儲存和組織排序資料。它的名字來自於維持其平衡的特性：- 樹中的每個節點都是紅色或黑色。
- 紅黑樹的根始終是黑色的。
- 所有葉節點（NIL 節點或空連結）都是黑色的。
- 如果樹的一個節點是紅色的，那麼它的子節點是黑色的。
- 從節點到其後代節點的每條簡單路徑都包含相同數量的黑色節點。
TreeSet的特徵和缺點
TreeSet提供了幾個關鍵功能，使其成為以排序方式管理物件集合的寶貴工具。優點：- 按排序順序自動維護元素。當新增或刪除元素時，樹結構會進行調整以保持它們的排序。這消除了手動排序的需要，並提供了按升序或降序排列的高效存取。
- 高效率的搜尋、插入和刪除操作。它利用二元搜尋樹結構，使這些操作的時間複雜度為O(log N)。這裡N是元素的數量。
- TreeSet透過利用元素的自然順序或自訂Comparator來保證元素的唯一性。當處理需要不同元素的集合時，這非常有用。
- 由於保持排序順序，比HashSet稍慢。
- 不允許空元素，因為它依賴自然排序或自訂比較器進行元素比較。
Java TreeSet：主要操作範例
現在讓我們示範如何在 Java 中建立TreeSet、取得集合的大小、在其中新增元素、從中刪除元素以及檢查元素是否在 TreeSet中。這些程式碼範例示範了使用TreeSet時的主要操作：建立實例、新增元素、刪除元素、檢查元素是否存在以及取得 TreeSet 的大小。建立TreeSet實例並新增元素：// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();
// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);
System.out.println(numbers); // Output: [2, 7, 18, 28]TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");
// Removing an element from the TreeSet
names.remove("David");
System.out.println(names); // Output: [Ivy, Johnny, Ricky]TreeSet<String> musicalInstrument = new TreeSet<>();
musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");
// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");
System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: falseTreeSet<Character> letters = new TreeSet<>();
letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');
// Getting the size of the TreeSet
int size = letters.size();
System.out.println(size); // Output: 4TreeSet 中的排序與迭代
Java 中的TreeSet提供了用於對元素集合進行排序和迭代的強大功能。在本節中，我們將探索對元素進行排序、迭代TreeSet以及使用subSet()、headSet()和tailSet()方法執行基於範圍的搜尋的各種技術。預設情況下，TreeSet會自動按排序順序維護元素。但是，我們可以透過在TreeSet建立期間提供Comparator來自訂排序行為。讓我們來看一個例子：import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetSortingExample {
public static void main(String[] args) {
// Create a TreeSet with custom sorting
TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());
// Add elements to the TreeSet
numbers.add(5);
numbers.add(3);
numbers.add(7);
numbers.add(1);
System.out.println(numbers); // Output: [7, 5, 3, 1]
}
}import java.util.TreeSet;
import java.util.Iterator;
public class TreeSetIterationExample {
public static void main(String[] args) {
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("Ricky");
names.add("David");
// Iterating using an iterator
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
String name = iterator.next();
System.out.println(name);
}
// Iterating using the enhanced for-each loop
for (String name : names) {
System.out.println(name);
}
}
}- subSet(E fromElement, E toElement) ：傳回從fromElement（包含）到toElement （不包含）的元素子集。
- headSet(E toElement)：傳回小於toElement的元素子集。
- tailSet(E fromElement)：傳回大於或等於fromElement的元素子集。
import java.util.TreeSet;
public class TreeSetRangeSearchExample {
public static void main(String[] args) {
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(1);
numbers.add(3);
numbers.add(5);
numbers.add(7);
numbers.add(9);
// Performing range-based search using subSet()
TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
System.out.println(subset); // Output: [3, 5, 7]
// Performing range-based search using headSet()
TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
System.out.println(headSet); // Output: [1, 3, 5]
// Performing range-based search using tailSet()
TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
System.out.println(tailSet); // Output: [5, 7, 9]
}
}- 子集 TreeSet包含 3（含）和 8（不含）之間的元素，即[3, 5, 7]。
- headSet TreeSet包含少於 6 個元素，即[1 , 3, 5]。
- tailSet TreeSet包含大於或等於 5 的元素，即[5, 7, 9 ] 。
TreeSet 中的比較器：使用自訂標準排序
除了自然排序之外，您還可以使用自訂Comparator對TreeSet進行排序。在本節中，我們將深入比較器的概念及其在TreeSet中的作用。我們將探索如何使用自訂比較器建立TreeSet並提供程式碼範例來示範根據特定條件對 TreeSet進行排序。什麼是比較器？
比較器是 Java 中的一個接口，允許對物件進行自訂排序。它提供了一種根據特定屬性或屬性定義元素順序的方法。透過實作Comparator介面並重寫其compare()方法，我們可以指定元素在 TreeSet 中的排序方式。使用自訂比較器建立 TreeSet
要建立具有自訂比較器的TreeSet ，我們需要在建立TreeSet實例時提供比較器作為參數。讓我們來看一個例子：import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetComparatorExample {
public static void main(String[] args) {
// Create a TreeSet with a custom comparator
TreeSet<String> names = new TreeSet<>(new LengthComparator());
// Add elements to the TreeSet
names.add("Johnny");
names.add("Ivy");
names.add("Rick");
names.add("David");
System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
}
}
class LengthComparator implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
return Integer.compare(s1.length(), s2.length());
}
}使用比較器對 TreeSet 進行排序的範例
除了使用自訂比較器建立TreeSet之外，我們還可以使用比較器對TreeSet進行臨時排序，而無需修改其自然順序。讓我們來看一個例子：import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("Ricky");
names.add("David");
// Sort TreeSet temporarily using a comparator
TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
sortedNames.addAll(names);
System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
}
}TreeSet 與其他資料結構的比較
TreeSet 與 HashSet 的比較
TreeSet和HashSet都是Java中Set介面的實作。然而，它們之間存在顯著差異。 TreeSet：TreeSet會依排序順序儲存唯一元素。它使用自平衡二元搜尋樹（通常是紅黑樹）來維護排序順序，從而導致插入、刪除和搜尋等操作的對數時間複雜度。TreeSet對於維護排序集合和執行基於範圍的操作非常有效。然而，由於樹結構，它的記憶體開銷較高，且不允許空元素。 HashSet：HashSet內部使用雜湊碼和雜湊表以無序的方式儲存唯一元素。它為插入、刪除和搜尋等基本操作提供恆定的時間複雜度。HashSet對於快速元素查找非常有效，並且不會為維護順序施加任何額外的記憶體開銷。但是，它不保證元素的任何特定順序。何時使用 TreeSet：
- 當您需要自動按排序順序維護元素時。
- 當您需要基於範圍的操作或需要有效率地尋找特定範圍內的元素時。
- 當不允許重複元素且唯一性至關重要時。
- 當您願意犧牲稍高的記憶體使用量來換取自動排序和範圍操作的好處時。
TreeSet 與 ArrayList 的比較
ArrayList是Java中的動態陣列實作。以下是TreeSet和ArrayList之間的主要差異：- TreeSet：TreeSet依排序順序儲存唯一元素，為維護排序集合和執行基於範圍的搜尋提供有效的操作。它的運算時間複雜度為對數。TreeSet不適合隨機存取或維護插入順序。
- ArrayList：ArrayList按插入順序儲存元素，使用索引提供對元素的快速隨機存取。透過索引存取元素時，大多數操作具有恆定的時間複雜度。然而，從清單中間插入或刪除元素具有線性時間複雜度，因為它需要移動元素。
何時考慮其他資料結構
- 如果不需要按排序順序維護元素，並且需要快速元素查找或無序集合，則HashSet可能是更好的選擇。
- 如果需要經常透過索引隨機存取元素或需要維護插入順序，ArrayList會更合適。
GO TO FULL VERSION