Chỉ vì tò mò, gần đây tôi đã phải sử dụng một cây cho một trong các chương trình của tôi, tôi phải tự xây dựng cây nhị phân, nhưng tại sao API Bộ sưu tập không có mặc định thực hiện cây (hoặc thậm chí một cây nhị phân)?Tại sao Java bộ sưu tập API không có thực hiện cây
Tôi nghĩ có một số lý do chính đáng khiến họ quyết định không đưa nó vào API bộ sưu tập.
java.util.TreeMap là triển khai Cây đỏ và Đen.
Tôi biết TreeMap tồn tại, nhưng nó là một dạng cụ thể hơn của cấu trúc dữ liệu cây, tại sao chúng ta không có tổng quát hơn thực hiện cây, như chúng ta có cho Danh sách và Đặt. tại sao những người sáng tạo của Bộ sưu tập API quyết định không đưa ra một hình thức tổng quát của một cây. Có thể họ có thể đã đưa ra một cây thông số
Tôi đồng ý với câu trả lời của Artem Zh. Cây chỉ là một dạng cụ thể của cấu trúc dữ liệu để giữ một "bộ sưu tập" của các thực thể. – Scorpion
IMHO, về mặt lý thuyết, Cây không phải là một loại bộ sưu tập, nó chỉ là một loại thực hiện. Tôi có nghĩa là có các bộ sưu tập trừu tượng như Set (tập hợp các mục nhập không theo thứ tự), Danh sách (tập hợp các mục nhập), Bản đồ (hai tập hợp các mục có quan hệ giữa chúng), và có các triển khai của chúng: mảng, danh sách (ví dụ: ArrayList và LinkedList), HashSet, vv, tất cả chúng đều có những ưu điểm và nhược điểm riêng. Do đó, Tree chỉ là một trong những triển khai (đối với danh sách, ví dụ) có thể cung cấp cho bạn (gần) tìm kiếm nhanh hơn mảng nhưng không có quyền truy cập theo chỉ mục.
BTW, có TreeMap ("Red-Black dựa trên NavigableMap thực hiện") và TreeSet ("A NavigableSet thực hiện dựa trên một TreeMap.") Lớp học trong Java.
Điều này. Bộ sưu tập không được xác định bởi cấu trúc dữ liệu của họ, nhưng những lời hứa của họ về hiệu suất liên quan đến chèn, xóa và tra cứu. Chi tiết triển khai được cho là không liên quan, bạn chọn vùng chứa dựa trên yêu cầu sử dụng của bạn. Ví dụ, nếu bạn cần một container nơi các phần tử luôn được sắp xếp và tra cứu phải là O (log n), thì bạn cần một Set hoặc SortedMap. Nó không quan trọng như thế nào thực hiện thực hiện đảm bảo hiệu suất. –
Tôi không đồng ý. Bộ sưu tập được xác định theo hợp đồng của họ. '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' 'Lệnh bảo đảm của List, nhưng cho phép trùng lặp. 'Map' bao gồm các mối quan hệ giữa các phần tử. Thực tế là bạn có thể sử dụng cây để thực hiện một số (tất cả?) Trong số này là không thích hợp. Ví dụ, bạn có thể sử dụng một 'Danh sách' để thực hiện một' Bộ' (ví dụ: 'LinkedHashSet'). Có nhiều cách để thực hiện một cây. – Tonio
Tôi nghĩ có một số lý do chính đáng khiến họ quyết định không đưa nó vào API thu thập.
Tôi nghĩ rằng lý do là không ai đã đưa ra một API tốt cho loại cây đó là cả
(Và nơi nào bạn dừng lại? Tree? Cây nhị phân? N-ary cây DAG? Graph?)
Điều đáng chú ý là không phải Apache Commons Bộ sưu tập hoặc Google Collections (aka Ổi) có một API cây. Tuy nhiên, có vấn đề về ổi chủ động về chủ đề này - http://code.google.com/p/guava-libraries/issues/detail?id=174 - vì vậy rõ ràng ít nhất một số người đồng ý với quan điểm của bạn.
CẬP NHẬT
Tính đến phiên bản 15.0, ổi hiện nay có hỗ trợ cây theo hình thức của TreeTraverser và BinaryTreeTraverser lớp. Nhưng điều này có thể không phải là những gì bạn mong đợi. Trong thực tế, các lớp này không thực sự thực hiện cấu trúc dữ liệu cây. Thay vào đó, bạn phải làm điều này trong một tham số kiểu generic. Ngoài ra, các lớp Traverser thậm chí còn tránh giả định về các API của loại nút. Họ làm điều này bằng cách là lớp trừu tượng, và yêu cầu subtype traverser cụ thể để thực hiện các hoạt động thẩm vấn cây; ví dụ. để có được con của một nút.
FWIW, TreeMap và TreeSet không phải là "API cây". Chúng là các triển khai dựa trên cây của các API Map và Set. Cây cối được che giấu hoàn toàn bởi các API công cộng, làm cho hai lớp này hoàn toàn không phù hợp để sử dụng làm cây mục đích chung.
yup, thực sự thú vị – Eugene
TreeSet và TreeMap là hai bộ sưu tập được sao lưu bởi cây nhị phân. –
Im không chỉ nói về cây nhị phân, tại sao chúng ta không có một thực hiện cây tổng quát, một cây inteface? –