Bộ cây trong Java

Java cung cấp một tập hợp lớn các cấu trúc dữ liệu để làm việc hiệu quả với các bộ sưu tập phần tử. Một cấu trúc dữ liệu như vậy là TreeSet, một triển khai cây đỏ đen trong Java. TreeSet duy trì thứ tự sắp xếp để lưu trữ các phần tử duy nhất. Những người mới bắt đầu có thể thấy việc sử dụng lớp Java TreeSet ban đầu có chút khó khăn. Trong bài viết này, chúng ta sẽ tìm hiểu cách sử dụng TreeSet , giải thích các khái niệm cốt lõi của nó và cung cấp các ví dụ về mã để giúp bạn bắt đầu kết hợp TreeSet trong các dự án Java của mình.

Cấu trúc TreeSet: Cây đỏ-đen

Như chúng tôi đã đề cập trước đây, cấu trúc lớp Java TreeSet được triển khai dưới dạng cây tìm kiếm nhị phân tự cân bằng được gọi là cây Đỏ-Đen. Hãy giải thích đây là gì... Cây Đỏ-Đen biểu thị cấu trúc dữ liệu tìm kiếm nhị phân cân bằng thường được sử dụng để lưu trữ và sắp xếp dữ liệu được sắp xếp. Nó lấy tên từ các thuộc tính duy trì sự cân bằng của nó:

Mỗi nút trong cây có màu đỏ hoặc đen.
Rễ của cây Đỏ-Đen luôn có màu đen.
Tất cả các nút lá (nút NIL hoặc liên kết null) đều có màu đen.
Nếu một nút của cây có màu đỏ thì con của nó có màu đen.
Mọi đường dẫn đơn giản từ một nút đến các nút con của nó đều chứa số lượng nút đen bằng nhau.

Cây đỏ đen thể hiện hiệu suất hiệu quả cho các hoạt động chèn, xóa và tra cứu phần tử bằng cách đảm bảo sự cân bằng. Điều này đảm bảo rằng chiều cao của cây vẫn tỷ lệ thuận với logarit của số nút mà nó chứa, dẫn đến độ phức tạp về thời gian logarit cho các phép toán. Cây đỏ đen tìm thấy ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau, bao gồm việc triển khai cây tìm kiếm cân bằng trong ngôn ngữ lập trình, cơ sở dữ liệu (ví dụ: cấu trúc chỉ mục nội bộ) và các tình huống khác khi cần lưu trữ và vận hành hiệu quả trên dữ liệu được sắp xếp.

Tính năng và điểm yếu của TreeSet

TreeSet cung cấp một số tính năng chính giúp nó trở thành một công cụ có giá trị để quản lý các bộ sưu tập đối tượng theo cách được sắp xếp. Thuận lợi:

Tự động bảo trì các phần tử theo thứ tự được sắp xếp. Khi thêm hoặc bớt phần tử, cấu trúc cây sẽ điều chỉnh để sắp xếp chúng. Điều này giúp loại bỏ nhu cầu sắp xếp thủ công và cung cấp khả năng truy cập hiệu quả theo thứ tự tăng dần hoặc giảm dần.
Hoạt động tìm kiếm, chèn và xóa hiệu quả. Nó sử dụng cấu trúc cây tìm kiếm nhị phân, cho phép thực hiện các thao tác này với độ phức tạp về thời gian là O(log N) . Ở đây N là số phần tử.
TreeSet đảm bảo tính duy nhất của các phần tử bằng cách sử dụng thứ tự tự nhiên của chúng hoặc Bộ so sánh tùy chỉnh . Điều này hữu ích khi làm việc với các bộ sưu tập yêu cầu các phần tử riêng biệt.

Hạn chế:

Chậm hơn một chút so với HashSet do duy trì thứ tự sắp xếp.
Không cho phép các phần tử rỗng vì nó dựa vào thứ tự tự nhiên hoặc Bộ so sánh tùy chỉnh để so sánh phần tử.

Java TreeSet: ví dụ về các hoạt động chính

Bây giờ, hãy trình bày cách tạo TreeSet trong Java, lấy kích thước của bộ sưu tập, thêm các phần tử vào đó, xóa chúng khỏi và kiểm tra xem một phần tử có trong TreeSet hay không . Các ví dụ mã này minh họa các thao tác chính khi làm việc với TreeSet : tạo một thể hiện, thêm phần tử, xóa phần tử, kiểm tra sự hiện diện của phần tử và lấy kích thước của TreeSet . Tạo một cá thể TreeSet và thêm các phần tử:


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

Ở đây chúng ta sử dụng phương thức add() để cộng 4 số trong TreeSet . Nếu chúng ta tạo một phương thức chính và chạy chương trình, kết quả đầu ra sẽ được sắp xếp theo thứ tự (2, 7, 18, 28). Xóa các phần tử khỏi 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]

Kiểm tra sự hiện diện của một phần tử trong 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

Lấy kích thước của 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

Sắp xếp và lặp lại trong TreeSet

TreeSet trong Java cung cấp các tính năng mạnh mẽ để sắp xếp và lặp lại các tập hợp phần tử. Trong phần này, chúng ta sẽ khám phá các kỹ thuật khác nhau để sắp xếp các phần tử, lặp qua TreeSet và thực hiện tìm kiếm dựa trên phạm vi bằng cách sử dụng các phương thức subSet() , headSet() và tailSet() . Theo mặc định, TreeSet tự động duy trì các phần tử theo thứ tự được sắp xếp. Tuy nhiên, chúng ta có thể tùy chỉnh hành vi sắp xếp bằng cách cung cấp Bộ so sánh trong quá trình tạo TreeSet . Hãy xem một ví dụ:


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

Trong đoạn mã trên, chúng tôi tạo một TreeSet thuộc loại Integer và cung cấp Bộ so sánh tùy chỉnh bằng cách sử dụng Comparator.reverseOrder() để sắp xếp các phần tử theo thứ tự giảm dần. TreeSet kết quả sẽ chứa các phần tử [7, 5, 3, 1] . Có nhiều cách để lặp lại TreeSet . Chúng ta có thể sử dụng một trình vòng lặp hoặc sử dụng vòng lặp for-each nâng cao . Hãy xem ví dụ về cả hai cách tiếp cận:


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

Trong đoạn mã trên, chúng ta tạo một TreeSet có tên là name và thêm một số phần tử. Sau đó, chúng tôi trình bày hai cách lặp qua TreeSet : sử dụng trình vòng lặp và sử dụng vòng lặp for-each nâng cao. TreeSet cung cấp các phương thức để thực hiện tìm kiếm theo phạm vi, cho phép chúng ta truy xuất các tập hợp con của các phần tử dựa trên các tiêu chí cụ thể. Ba phương pháp chính để tìm kiếm dựa trên phạm vi là:

subSet(E fromElement, E toElement) : Trả về một tập hợp con các phần tử từ fromElement (bao gồm) đến toElement (độc quyền).
headSet(E toElement) : Trả về một tập hợp con các phần tử nhỏ hơn toElement .
tailSet(E fromElement) : Trả về một tập hợp con gồm các phần tử lớn hơn hoặc bằng fromElement .

Hãy xem một ví dụ:


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

Trong đoạn mã trên, chúng ta tạo một TreeSet có tên là số và thêm một số phần tử. Sau đó, chúng tôi trình bày các tìm kiếm dựa trên phạm vi bằng cách sử dụng các phương thức subSet() , headSet() và tailSet() .

Tập hợp con TreeSet chứa các phần tử nằm trong khoảng từ 3 (bao gồm) đến 8 (độc quyền), đó là [3, 5, 7] .
headSet TreeSet chứa các phần tử nhỏ hơn 6, đó là [1 , 3, 5] .
tailSet TreeSet chứa các phần tử lớn hơn hoặc bằng 5, đó là [5, 7 , 9] .

Các phương pháp tìm kiếm dựa trên phạm vi này cho phép chúng tôi truy xuất các tập hợp con của các phần tử dựa trên tiêu chí cụ thể, mang lại sự linh hoạt khi làm việc với dữ liệu được sắp xếp.

Bộ so sánh trong TreeSet: Sắp xếp theo tiêu chí tùy chỉnh

Ngoại trừ thứ tự tự nhiên, bạn có thể sử dụng Bộ so sánh tùy chỉnh để sắp xếp TreeSet . Trong phần này, chúng ta sẽ đi sâu vào khái niệm về bộ so sánh và vai trò của nó trong TreeSet . Chúng ta sẽ khám phá cách tạo TreeSet bằng bộ so sánh tùy chỉnh và cung cấp các ví dụ về mã để minh họa việc sắp xếp TreeSet dựa trên các tiêu chí cụ thể.

Bộ so sánh là gì?

Bộ so sánh là một giao diện trong Java cho phép sắp xếp tùy chỉnh các đối tượng. Nó cung cấp một cách để xác định thứ tự của các phần tử dựa trên các thuộc tính hoặc thuộc tính cụ thể. Bằng cách triển khai giao diện Comparator và ghi đè phương thức so sánh() của nó , chúng ta có thể chỉ định cách sắp xếp các phần tử trong TreeSet .

Tạo TreeSet bằng Bộ so sánh tùy chỉnh

Để tạo TreeSet bằng bộ so sánh tùy chỉnh, chúng ta cần cung cấp bộ so sánh làm đối số khi tạo phiên bản TreeSet . Hãy xem một ví dụ:


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

Trong đoạn mã trên, chúng ta tạo TreeSet có tên là name với bộ so sánh tùy chỉnh có tên là lengthComparator . Bộ so sánh độ dài so sánh độ dài của hai chuỗi và sắp xếp chúng cho phù hợp. Kết quả là TreeSet được sắp xếp dựa trên độ dài của chuỗi, cho chúng ta kết quả đầu ra [Ivy, Rick, David, Johnny] .

Ví dụ về sắp xếp TreeSet bằng Bộ so sánh

Bên cạnh việc tạo TreeSet bằng bộ so sánh tùy chỉnh, chúng ta cũng có thể sử dụng bộ so sánh để sắp xếp TreeSet tạm thời mà không sửa đổi thứ tự tự nhiên của nó. Hãy xem một ví dụ:


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

Trong đoạn mã trên, chúng ta tạo một TreeSet có tên là name và thêm một số phần tử. Sau đó, chúng tôi tạo một TreeSet mới có tên là SortNames với bộ so sánh tùy chỉnh Comparator.reverseOrder() . Bằng cách thêm tất cả các phần tử từ tên ban đầu TreeSet vào SortNames , chúng ta thu được phiên bản được sắp xếp tạm thời của TreeSet .

So sánh TreeSet với các cấu trúc dữ liệu khác

So sánh TreeSet với HashSet

Cả TreeSet và HashSet đều là các triển khai của giao diện Set trong Java. Tuy nhiên, có sự khác biệt đáng kể giữa chúng. TreeSet : TreeSet lưu trữ các phần tử duy nhất theo thứ tự được sắp xếp. Nó sử dụng cây tìm kiếm nhị phân tự cân bằng (thường là Cây Đỏ-Đen) để duy trì thứ tự sắp xếp, dẫn đến độ phức tạp về thời gian logarit cho các hoạt động như chèn, xóa và tìm kiếm. TreeSet hiệu quả trong việc duy trì bộ sưu tập được sắp xếp và thực hiện các hoạt động dựa trên phạm vi. Tuy nhiên, nó có chi phí bộ nhớ cao hơn do cấu trúc cây và không cho phép các phần tử null. HashSet : HashSet lưu trữ các phần tử duy nhất theo cách không có thứ tự bằng cách sử dụng mã băm và hàm băm bên trong. Nó cung cấp độ phức tạp về thời gian không đổi cho các hoạt động cơ bản như chèn, xóa và tìm kiếm. HashSet hiệu quả trong việc tra cứu phần tử nhanh chóng và không áp đặt thêm bất kỳ chi phí bộ nhớ nào để duy trì trật tự. Tuy nhiên, nó không đảm bảo bất kỳ thứ tự cụ thể nào của các phần tử.

Khi nào nên sử dụng TreeSet:

Khi bạn cần tự động duy trì các phần tử theo thứ tự được sắp xếp.
Khi bạn yêu cầu các hoạt động dựa trên phạm vi hoặc cần tìm các phần tử trong một phạm vi cụ thể một cách hiệu quả.
Khi các phần tử trùng lặp không được phép và tính duy nhất là điều cần thiết.
Khi bạn sẵn sàng đánh đổi mức sử dụng bộ nhớ cao hơn một chút để lấy lợi ích của hoạt động phân loại và phạm vi tự động.

So sánh TreeSet với ArrayList

ArrayList là một triển khai mảng động trong Java. Dưới đây là những khác biệt chính giữa TreeSet và ArrayList :

TreeSet : TreeSet lưu trữ các phần tử duy nhất theo thứ tự được sắp xếp, cung cấp các hoạt động hiệu quả để duy trì bộ sưu tập đã được sắp xếp và thực hiện tìm kiếm dựa trên phạm vi. Nó có độ phức tạp thời gian logarit cho các hoạt động. TreeSet không phù hợp để truy cập ngẫu nhiên hoặc duy trì thứ tự chèn.
ArrayList : ArrayList lưu trữ các phần tử theo thứ tự chèn, cung cấp khả năng truy cập ngẫu nhiên nhanh chóng vào các phần tử bằng cách sử dụng các chỉ mục. Nó có độ phức tạp về thời gian không đổi đối với hầu hết các thao tác khi truy cập các phần tử theo chỉ mục. Tuy nhiên, nó có độ phức tạp về thời gian tuyến tính khi chèn hoặc xóa các phần tử ở giữa danh sách vì nó yêu cầu dịch chuyển các phần tử.

Khi nào cần xem xét các cấu trúc dữ liệu khác

Nếu không cần phải duy trì các phần tử theo thứ tự được sắp xếp và bạn cần tra cứu phần tử nhanh hoặc bộ sưu tập không có thứ tự, thì HashSet có thể là lựa chọn tốt hơn.
Nếu bạn yêu cầu truy cập ngẫu nhiên thường xuyên vào các phần tử theo chỉ mục hoặc cần duy trì thứ tự chèn, ArrayList sẽ phù hợp hơn.