Java 中的樹集

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]

這裡我們使用add()方法在TreeSet中加入 4 個數字。如果我們建立一個main方法並運行該程序，輸出將按排序順序 (2, 7, 18, 28)。從TreeSet中刪除元素：

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 中是否存在元素：

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: false

取得TreeSet 的大小：

TreeSet<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: 4

TreeSet 中的排序與迭代

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]
  }
}

在上面的程式碼中，我們建立了一個Integer類型的TreeSet ，並使用Comparator.reverseOrder()提供了一個自訂Comparator來按降序對元素進行排序。產生的TreeSet將包含元素[7, 5, 3, 1]。有多種方法可以迭代TreeSet。我們可以使用迭代器或利用增強的for-each循環。讓我們來看看這兩種方法的範例：

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);
    }
  }
}

在上面的程式碼中，我們建立了一個名為names的TreeSet並且加入了一些元素。然後，我們示範了兩種迭代 TreeSet 的方法：使用迭代器和利用增強的 for-each 迴圈。TreeSet 提供了執行基於範圍的搜尋的方法，使我們能夠根據特定條件檢索元素子集。基於範圍的搜尋的三種主要方法是：

• 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]
  }
}

在上面的程式碼中，我們建立了一個名為numbers的TreeSet並且加入了一些元素。然後，我們使用subSet()、headSet()和tailSet()方法來示範基於範圍的搜尋。

• 子集 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和一個名為LengthComparator的自訂比較器。LengthComparator比較兩個字串的長度並相應地對它們進行排序。結果，TreeSet根據字串的長度進行排序，得到輸出[Ivy, Rick, David, Johnny]。

使用比較器對 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]
    }
  }

在上面的程式碼中，我們建立了一個名為names的TreeSet並且加入了一些元素。然後，我們使用自訂比較器Comparator.reverseOrder()建立一個名為sortedNames的新TreeSet。透過將原始名稱TreeSet中的所有元素加入排序名稱中，我們得到了TreeSet的臨時排序版本。

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會更合適。