Sơ đồ cây trong Java

Nếu bạn đang đọc bài viết này, rất có thể bạn đã quen thuộc với giao diện Bản đồ và nơi có thể áp dụng một cách thích hợp. Nếu chưa thì hãy đến đây . Hôm nay chúng ta sẽ nói về các tính năng triển khai của Java TreeMap và cụ thể hơn, nó khác với HashMap như thế nào và cách sử dụng nó một cách chính xác.

So sánh TreeMap, HashMap và LinkedHashMap

Việc triển khai giao diện Bản đồ được sử dụng nhiều nhất là HashMap. Nó dễ sử dụng và đảm bảo truy cập dữ liệu nhanh chóng, vì vậy nó là ứng cử viên tốt nhất để giải quyết hầu hết các vấn đề. Hầu hết, nhưng không phải tất cả. Đôi khi bạn cần lưu trữ dữ liệu theo cách có cấu trúc và có thể điều hướng qua dữ liệu đó. Trong trường hợp này, một triển khai khác của giao diện Bản đồ (TreeMap) sẽ được giải cứu. TreeMap triển khai giao diện NavigableMap kế thừa SortedMap , giao diện này kế thừa giao diện Bản đồ. Bằng cách triển khai các giao diện NavigableMap và SortedMap , TreeMap nhận được chức năng bổ sung không có sẵn trong HashMap, nhưng nó phải trả giá về mặt hiệu suất. Ngoài ra còn có LinkedHashMapclass , cũng cho phép bạn lưu trữ dữ liệu theo một thứ tự cụ thể (thứ tự mà bạn thêm dữ liệu đó vào bản đồ). Để hiểu sự khác biệt giữa ba lớp này, hãy xem bảng sau: Như bạn có thể thấy, các lớp này có nhiều điểm chung, nhưng cũng có một số điểm khác biệt. Mặc dù lớp TreeMap là lớp linh hoạt nhất nhưng không phải lúc nào nó cũng lưu trữ null làm khóa. Ngoài ra, việc truy cập các thành phần của Sơ đồ cây mất nhiều thời gian nhất. Vì vậy, nếu bạn không cần lưu trữ dữ liệu theo một số thứ tự được sắp xếp, thì tốt hơn là sử dụng HashMap hoặc LinkedHashMap .

Cây đỏ đen

Bạn có thể nhận thấy rằng TreeMap sử dụng cấu trúc dữ liệu được gọi là cây đỏ đen. Lưu trữ dữ liệu trong cấu trúc này chính xác là những gì cung cấp thứ tự dữ liệu. Vậy đây là loại cây gì? Hãy tìm ra nó ra! Hãy tưởng tượng rằng bạn cần lưu trữ các cặp Chuỗi số. Các số 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 và 101 sẽ là khóa. Nếu bạn lưu trữ dữ liệu trong một danh sách truyền thống và bạn cần tìm phần tử có khóa 101, thì bạn sẽ cần phải duyệt qua tất cả 13 phần tử để tìm thấy nó. Đối với 13 phần tử, đây không phải là vấn đề lớn, nhưng khi làm việc với một triệu phần tử, chúng ta sẽ gặp vấn đề lớn. Để giải quyết những vấn đề này, các lập trình viên sử dụng các cấu trúc dữ liệu phức tạp hơn một chút. Đây là nơi cây đỏ đen bước vào sân khấu!Tìm kiếm một phần tử bắt đầu từ gốc của cây, trong trường hợp của chúng tôi là 61. Sau đó, chúng tôi so sánh các giá trị nút với giá trị mà chúng tôi đang tìm kiếm. Nếu giá trị của chúng tôi ít hơn, thì chúng tôi sẽ chuyển sang bên trái; nếu nó lớn hơn, thì chúng ta đi sang bên phải. Quá trình này lặp lại cho đến khi chúng ta tìm thấy giá trị mong muốn hoặc gặp phần tử có giá trị null (một chiếc lá của cây). Các màu đỏ và đen được sử dụng để đơn giản hóa việc điều hướng và cân bằng cây. Có những quy tắc phải luôn được tuân thủ khi xây dựng cây đỏ đen:

• Gốc phải có màu đen.
• Lá của cây phải có màu đen.
• Một nút màu đỏ phải có hai nút con màu đen.
• Một nút màu đen có thể có các nút con có màu bất kỳ.
• Đường đi từ một nút đến các lá của nó phải chứa cùng một số nút đen.
• Các nút mới được thêm vào lá.

Nếu bạn xem xét Quy tắc 3, 4 và 5 cùng nhau, bạn có thể hiểu cách màu nút cho phép chúng ta điều hướng cây nhanh hơn: đường đi qua các nút màu đen luôn ngắn hơn đường đi qua các nút màu đỏ. Theo đó, tổng kích thước của cây được xác định bởi số nút đen, được gọi là "chiều cao đen". Cấu trúc dữ liệu cây đỏ đen được triển khai bằng nhiều ngôn ngữ lập trình khác nhau. Có rất nhiều triển khai Java trên Internet, vì vậy chúng tôi sẽ không nán lại ở đây. Thay vào đó, hãy tiếp tục tìm hiểu chức năng của TreeMap.

Các phương thức đến từ giao diện SortedMap và NavigableMap

Giống như HashMap, TreeMap triển khai giao diện Bản đồ, có nghĩa là TreeMap có tất cả các phương thức tồn tại trong HashMap. Nhưng TreeMap cũng triển khai các giao diện SortedMap và NavigableMap và do đó có thêm chức năng từ chúng. SortedMap là một giao diện mở rộng Bản đồ và thêm các phương thức liên quan đến tập dữ liệu được sắp xếp:

• firstKey() : trả về khóa của phần tử đầu tiên trong bản đồ
• lastKey() : trả về khóa của phần tử cuối cùng
• headMap(K end) : trả về một bản đồ chứa tất cả các phần tử của bản đồ hiện tại, từ phần đầu cho đến phần tử có key end
• tailMap(K start) : trả về một bản đồ chứa tất cả các phần tử của bản đồ hiện tại, từ phần tử bắt đầu đến phần cuối
• subMap(K start, K ​​end) : trả về một bản đồ chứa tất cả các phần tử của bản đồ hiện tại, từ phần tử bắt đầu đến phần tử có khóa kết thúc.

NavigableMap là một giao diện mở rộng SortedMap và thêm các phương thức để điều hướng giữa các phần tử của bản đồ:

• firstEntry() : trả về cặp khóa-giá trị đầu tiên
• lastEntry() : trả về cặp khóa-giá trị cuối cùng
• pollFirstEntry() : trả về và xóa cặp đầu tiên
• pollLastEntry() : trả về và xóa cặp cuối cùng
• trầnKey(K obj) : trả về khóa k nhỏ nhất lớn hơn hoặc bằng khóa obj. Nếu không có khóa như vậy, trả về null
• floorKey(K obj) : trả về khóa k lớn nhất nhỏ hơn hoặc bằng khóa obj. Nếu không có khóa như vậy, trả về null
• LowerKey(K obj) : trả về khóa k lớn nhất nhỏ hơn khóa obj. Nếu không có khóa như vậy, trả về null
• HigherKey(K obj) : trả về khóa nhỏ nhất k lớn hơn khóa obj. Nếu không có khóa như vậy, trả về null
• trầnEntry(K obj) : tương tự như phương thức trầnKey(K obj), chỉ trả về một cặp khóa-giá trị (hoặc null)
• floorEntry(K obj) : tương tự như phương thức floorKey(K obj), chỉ trả về một cặp khóa-giá trị (hoặc null)
• LowerEntry(K obj) : tương tự như phương thức LowerKey(K obj), chỉ trả về một cặp khóa-giá trị (hoặc null)
• HigherEntry(K obj) : tương tự như phương thức HigherKey(K obj), chỉ trả về một cặp khóa-giá trị (hoặc null)
• giảm dầnKeySet() : trả về một NavigableSet chứa tất cả các khóa được sắp xếp theo thứ tự ngược lại
• giảm dầnMap() : trả về một NavigableMap chứa tất cả các cặp được sắp xếp theo thứ tự ngược lại
• navigableKeySet() : trả về một đối tượng NavigableSet chứa tất cả các khóa theo thứ tự chúng được lưu trữ
• headMap(K upperBound, boolean incl) : trả về một bản đồ chứa các cặp từ đầu đến phần tử upperBound. Tham số incl cho biết có bao gồm phần tử upperBound trong bản đồ được trả về hay không
• tailMap(K LowerBound, boolean incl) : chức năng tương tự như phương thức trước, chỉ trả về các cặp từ LowerBound đến cuối
• subMap(K LowerBound, boolean lowIncl, K upperBound, boolean highIncl) : như với các phương thức trước đó, trả về các cặp từ LowerBound đến UpperBound; các đối số lowIncl và highIncl cho biết có nên đưa các phần tử ranh giới vào bản đồ mới hay không.

Ngoài các hàm tạo thông thường, TreeMap còn có một hàm tạo khác chấp nhận một thể hiện của bộ so sánh. Bộ so sánh này chịu trách nhiệm về thứ tự các phần tử được lưu trữ.

Ví dụ về Sơ đồ cây

Sự phong phú của các phương pháp bổ sung này có vẻ không cần thiết, nhưng hóa ra chúng lại hữu ích hơn nhiều so với những gì bạn có thể nhận ra ngay từ cái nhìn đầu tiên. Hãy cùng nhau khám phá ví dụ sau. Hãy tưởng tượng rằng chúng tôi làm việc trong bộ phận tiếp thị của một công ty lớn và chúng tôi có cơ sở dữ liệu về những người mà chúng tôi muốn hiển thị quảng cáo. Có hai chi tiết cần ghi nhớ:

• Chúng ta cần theo dõi số lần hiển thị cho mỗi người
• Thuật toán hiển thị quảng cáo cho trẻ vị thành niên là khác nhau.

Hãy tạo một lớp Person , lớp này sẽ lưu trữ tất cả thông tin liên quan về mỗi người:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Chúng tôi triển khai logic trong lớp Chính :

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

Trong lớp Chính, hãy tạo Sơ đồ cây, trong đó mỗi khóa đại diện cho một người cụ thể và mỗi giá trị là số lần hiển thị quảng cáo trong tháng này. Chúng tôi chuyển hàm tạo một bộ so sánh để sắp xếp mọi người theo độ tuổi. Chúng tôi điền vào bản đồ với các giá trị tùy ý. Bây giờ chúng tôi muốn tham chiếu đến người lớn đầu tiên trong kho lưu trữ dữ liệu nhỏ của chúng tôi. Chúng tôi làm điều này bằng cách sử dụng Stream API. Sau đó, chúng tôi nhận được hai bản đồ riêng biệt mà chúng tôi chuyển đến các phương thức hiển thị quảng cáo. Có rất nhiều cách chúng ta có thể hoàn thành nhiệm vụ này. Kho phương pháp của lớp TreeMap cho phép chúng tôi tạo các giải pháp tùy chỉnh cho mọi nhu cầu. Bạn không cần phải nhớ tất cả, vì bạn luôn có thể sử dụng tài liệu hoặc mẹo từ IDE của mình. Để củng cố những gì bạn đã học, chúng tôi khuyên bạn nên xem một video bài học từ Khóa học Java của chúng tôi

Đó là tất cả cho bây giờ! Tôi hy vọng rằng lớp TreeMap đã rõ ràng với bạn bây giờ và bạn sẽ áp dụng nó đúng cách trong việc giải quyết các nhiệm vụ mã hóa thực tế.