TreeSet trong Java (Java TreeSet)

1. TreeSet là gì?

TreeSet trong Java là một cấu trúc dữ liệu thuộc Java Collections Framework dùng để lưu trữ các phần tử theo thứ tự tự nhiên (hoặc theo một tiêu chí được chỉ định) và không cho phép các phần tử trùng lặp. TreeSet được triển khai dựa trên NavigableSet và sử dụng cây nhị phân cân bằng (Red-Black Tree) để lưu trữ và sắp xếp các phần tử.

2. Đặc điểm chính của TreeSet

• Sắp xếp tự động: Các phần tử trong TreeSet được sắp xếp theo thứ tự tự nhiên hoặc theo thứ tự được xác định bởi Comparator tùy chỉnh nếu được cung cấp.
• Không cho phép trùng lặp: TreeSet không cho phép các phần tử trùng nhau. Nếu bạn cố thêm phần tử đã tồn tại, TreeSet sẽ bỏ qua.
• Cấu trúc Cây nhị phân cân bằng: TreeSet sử dụng cây Red-Black để lưu trữ các phần tử, giúp cho các thao tác như thêm, xóa và tìm kiếm đạt hiệu suất trung bình là O(log n).
• Không cho phép null: TreeSet không cho phép giá trị null, vì thứ tự của phần tử null không thể xác định trong một cây sắp xếp.

3. Các phương thức quan trọng của TreeSet

Một số phương thức thường dùng trong TreeSet bao gồm:

• add(E e): Thêm một phần tử vào TreeSet.
• remove(Object o): Xóa phần tử cụ thể khỏi TreeSet.
• first(): Lấy phần tử nhỏ nhất.
• last(): Lấy phần tử lớn nhất.
• higher(E e): Lấy phần tử lớn hơn phần tử e gần nhất.
• lower(E e): Lấy phần tử nhỏ hơn phần tử e gần nhất.
• ceiling(E e): Lấy phần tử lớn nhất bằng hoặc lớn hơn e.
• floor(E e): Lấy phần tử nhỏ nhất bằng hoặc nhỏ hơn e.
• subSet(E fromElement, E toElement): Trả về một SortedSet chứa các phần tử từ fromElement đến toElement.
• headSet(E toElement): Trả về một SortedSet chứa các phần tử nhỏ hơn toElement.
• tailSet(E fromElement): Trả về một SortedSet chứa các phần tử lớn hơn hoặc bằng fromElement.

– Ví dụ:

import java.util.TreeSet;

public class App {

    public static void main(String[] args) {
        // Khởi tạo TreeSet
        TreeSet treeSet = new TreeSet<>();

        // Thêm phần tử vào TreeSet
        treeSet.add(10);
        treeSet.add(5);
        treeSet.add(20);
        treeSet.add(15);

        // TreeSet tự động sắp xếp các phần tử
        System.out.println("TreeSet: " + treeSet); // [5, 10, 15, 20]

        // Truy cập phần tử đầu tiên và cuối cùng
        System.out.println("Phần tử nhỏ nhất: " + treeSet.first()); // 5
        System.out.println("Phần tử lớn nhất: " + treeSet.last());  // 20

        // Sử dụng các phương thức điều hướng
        System.out.println("Phần tử lớn hơn 10: " + treeSet.higher(10)); // 15
        System.out.println("Phần tử nhỏ hơn 15: " + treeSet.lower(15));  // 10

        // Xóa phần tử
        treeSet.remove(10);
        System.out.println("TreeSet sau khi xóa 10: " + treeSet); // [5, 15, 20]
    }
}

– Kết quả:

TreeSet: [5, 10, 15, 20]
Phần tử nhỏ nhất: 5
Phần tử lớn nhất: 20
Phần tử lớn hơn 10: 15
Phần tử nhỏ hơn 15: 10
TreeSet sau khi xóa 10: [5, 15, 20]

4. Ưu và nhược điểm của TreeSet

• Ưu điểm:
  • Duy trì thứ tự sắp xếp tự nhiên.
  • Cung cấp hiệu suất tốt cho các thao tác tìm kiếm, thêm, và xóa với thời gian O(log n).
  • Hỗ trợ các thao tác điều hướng như subSet, headSet, tailSet để lấy các tập con của TreeSet.
• Nhược điểm:
  • Không cho phép phần tử null.
  • TreeSet có hiệu suất kém hơn HashSet trong trường hợp không cần duy trì thứ tự vì HashSet có thời gian O(1) cho các
  • thao tác thêm, xóa, và tìm kiếm.

5. Câu hỏi phỏng vấn TreeSet

1. Câu hỏi lý thuyết

• TreeSet trong Java là gì? Giải thích cách TreeSet hoạt động và cấu trúc mà nó sử dụng để lưu trữ dữ liệu.
• TreeSet có sự khác biệt gì với HashSet? Khi nào thì dùng TreeSet thay vì HashSet?
• TreeSet sắp xếp các phần tử như thế nào? Tại sao TreeSet không cho phép các phần tử trùng lặp?
• TreeSet có cho phép null không? Tại sao không? Điều gì sẽ xảy ra nếu cố thêm null vào TreeSet?
• TreeSet có phải là synchronized không? Làm thế nào để tạo một TreeSet thread-safe?
• TreeSet sử dụng cấu trúc cây nhị phân cân bằng nào? Giải thích cách cấu trúc Red-Black Tree hoạt động trong TreeSet.

2. Câu hỏi về thao tác với TreeSet

• Làm sao để lấy phần tử nhỏ nhất và lớn nhất trong TreeSet?
• Cách sử dụng các phương thức higher(), lower(), ceiling(), và floor()? Giải thích chúng khác nhau thế nào và đưa ra ví dụ.
• Giải thích cách sử dụng subSet(), headSet(), tailSet() trong TreeSet. Khi nào thì nên dùng các phương thức này?
• TreeSet đảm bảo các phần tử được sắp xếp theo thứ tự gì? Làm thế nào để thay đổi thứ tự mặc định của TreeSet?
• Có thể tạo một TreeSet từ Comparator tùy chỉnh không? Làm sao để thay đổi thứ tự sắp xếp trong TreeSet?

3. Câu hỏi thực hành và thuật toán

• Duyệt TreeSet theo thứ tự giảm dần: Làm thế nào để duyệt qua các phần tử của TreeSet theo thứ tự giảm dần?
• Tìm k phần tử nhỏ nhất trong TreeSet: Làm sao để lấy k phần tử nhỏ nhất từ TreeSet?
• Hợp nhất hai TreeSet đã sắp xếp: Cho hai TreeSet đã sắp xếp, viết mã để hợp nhất chúng thành một TreeSet đã sắp xếp.
• Xóa phần tử lớn hơn một giá trị nhất định: Viết mã để xóa tất cả các phần tử lớn hơn một giá trị cụ thể trong TreeSet.
• So sánh các phần tử của TreeSet: Viết mã để tìm các phần tử chung giữa hai TreeSet.

4. Câu hỏi nâng cao

• Triển khai cấu trúc dữ liệu tương tự TreeSet: Nếu TreeSet không có sẵn, bạn sẽ triển khai nó như thế nào? Giải thích cách bạn sẽ xử lý việc sắp xếp và loại bỏ trùng lặp.
• Sử dụng TreeSet để giải quyết bài toán số duy nhất: Cho một mảng số nguyên, làm sao bạn sẽ dùng TreeSet để tìm các số duy nhất và in chúng theo thứ tự tăng dần?
• Tối ưu hóa bộ nhớ cho TreeSet lớn: Nếu bạn có một TreeSet rất lớn chứa hàng triệu phần tử, bạn sẽ làm gì để giảm thiểu bộ nhớ sử dụng?
• Sử dụng TreeSet để duyệt theo thứ tự gần đúng: Cho một tập các điểm tọa độ, làm sao bạn sẽ sử dụng TreeSet để duyệt qua các điểm theo khoảng cách tăng dần từ một điểm cụ thể?
• Ứng dụng của TreeSet trong các bài toán liên quan đến khoảng thời gian: Giả sử bạn có danh sách các khoảng thời gian, làm sao bạn sẽ sử dụng TreeSet để tìm các khoảng giao nhau hoặc khoảng thời gian rảnh?