Tôi đã đọc nhiều bài viết về cây đen đỏ, nơi nó mất thời gian O (log n) cho hoạt động. Tôi không rõ cách thức hoạt động và cách bản đồ cây thực sự sử dụng thuật toán cây đỏ đen để cân bằng cây so với cây tìm kiếm nhị phân.Bản đồ cây sử dụng thuật toán cây xanh đen
bất cứ ai có thể vui lòng giải thích với một ví dụ như thế nào các thuật toán làm việc.
Cây đỏ đen là cây tìm kiếm nhị phân. Nó chỉ là một hương vị của BST có phiên bản ưa thích của các hoạt động insert và delete tổ chức lại cây khi chúng chạy để cây không bao giờ bị "dài và xâu chuỗi". Cây càng dài và xâu chuỗi càng lớn, nó càng hoạt động giống như một danh sách liên kết. Trung bình, các hoạt động danh sách liên kết yêu cầu một nửa danh sách được chạm (hoặc toàn bộ danh sách trong trường hợp xấu nhất), do đó thời gian chạy thay đổi tuyến tính (O (n) trong số phần tử n). Khi cây "rậm rạp" hoặc gần như cân bằng, thì hoạt động rẻ hơn nhiều (O (log n)). Các thuật toán màu đỏ-đen đảm bảo rằng cây vẫn rậm rạp.
Để làm cho bê tông này, đây là hai cây lưu trữ các phím A đến G. Bên trái dài và có dây. Lưu ý nó trông giống như một danh sách. Trong trường hợp xấu nhất, phải mất 4 so sánh chính để tìm một phần tử. Cây bên phải là bụi rậm. Nó chỉ cần 3. Ở đây sự khác biệt là nhỏ. Đối với một cây của 1023 yếu tố, cây dây cần 512 so sánh và một trong những bụi rậm chỉ 10. Đây là sức mạnh của log n.
B _D_
/\ / \
A D B F
/\ /\ /\
C F A C E G
/\
E G
Cây đỏ đen là không đảm bảo được một cách hoàn hảo rậm (trong thuật ngữ chính xác "hoàn toàn cân bằng"), nhưng các quy tắc đỏ-đen đảm bảo rằng nó đủ rậm một cách toán học chặt chẽ để lần hoạt động thay đổi như log của n chứ không phải tuyến tính trong n.
Thiên tài quy tắc màu đỏ đen là chúng là "địa phương". Trong quá trình chèn hoặc xóa phá vỡ các quy tắc, có thể khôi phục chúng bằng cách chỉ điều chỉnh số lượng nút liên tục cho mỗi nút được thao tác. Do đó chúng rẻ và khá dễ thực hiện.
Tuy nhiên, khi các quy tắc màu đỏ-đen là đúng cho toàn bộ cây, có thể hiển thị bằng bằng chứng toán học thông minh rằng nó đủ rộng như mô tả ở trên.
Còn sơ đồ cây thì sao? Bản đồ là một hàm có tên miền được gọi là tập hợp khóa K và phạm vi được gọi là tập hợp giá trị V. Để triển khai bản đồ cây, mỗi nút lưu trữ cặp khóa-giá trị <k,v> trong đó k \in K và v \in V. Trong các bản vẽ ở trên (và hầu hết các bài thuyết trình), chỉ có các phím (chữ A-G) mới được hiển thị. Trong bản đồ, chèn, tra cứu, và xóa công việc trên các cặp một cách khá rõ ràng. Ví dụ: tra cứu tìm kiếm khóa bằng thuật toán BST thông thường. Khi tìm thấy khóa, giá trị cũng được tìm thấy bởi vì nó nằm trong cùng một cặp. Đó là những gì được trả lại. Trong java, cặp được gọi là Map.Entry. Bạn có thể kiểm tra điều này trong số Java source code.
Tôi sẽ không đi sâu vào chi tiết về cách quy tắc đen-đen hoạt động vì tôi không thể cải thiện trên the Wikipedia page. Đoán và hy vọng của tôi là bạn đã bỏ lỡ "bức tranh lớn" nên bây giờ cuộc thảo luận đó sẽ có ý nghĩa. Tin vui là gần như tất cả các ngôn ngữ đều cung cấp một cách thực hiện cây được tối ưu hóa hiệu quả và được kiểm tra kỹ lưỡng, vì vậy việc biết các chi tiết phức tạp của phép quay là không cần thiết. Tất nhiên, nếu bạn tò mò và chỉ muốn biết, có nó! Xin chúc mừng!
Đối với những gì đáng giá, giải thích Top Coder về thuật toán không phải lúc nào cũng rõ ràng nhất. Tìm kiếm những người khác cho đến khi một "nhấp chuột" cho bạn.Các sách giáo khoa được tôn trọng trong CS được tôn trọng vì một lý do: giải thích của họ là tuyệt vời. Corman and Rivest là một yêu thích được chấp nhận.
Trước hết, bạn nên cụ thể hơn về câu hỏi của mình. Chỉ định những gì bạn biết, những gì bạn không và những gì bạn đã thử.
Đến với câu hỏi, TreeMap và cây đỏ-đen là các khái niệm hoàn toàn khác nhau. Sự hiểu biết khái niệm của một trong hai không phải là ở tất cả phụ thuộc vào khác và tôi đề nghị bạn không trộn chúng lên. Tôi sẽ không cung cấp cho bạn câu trả lời chính xác, thay vào đó tôi sẽ đưa ra một tổng quan ngắn gọn về các khái niệm và trình tự mà bạn phải học chúng (IMO).
Các dữ liệu bản đồ cấu trúc
Data Tree cấu trúc
Tôi giả sử bạn biết các khái niệm về Maps và tìm kiếm nhị phân Cây. Nếu không, một tìm kiếm đơn giản sẽ dẫn bạn đến rất nhiều tài nguyên tốt.
Bây giờ, đến câu trả lời thực tế.
Trước hết, bạn nên biết Bản đồ phân loại và BST tự cân bằng là gì.
Bản đồ Sorte là gì?
Từ Java docs,
Một Map đó tiếp tục cung cấp một tổng trật tự trên các phím của nó. Bản đồ được sắp xếp theo thứ tự tự nhiên của các khóa của nó, hoặc bởi một bộ so sánh thường được cung cấp tại thời gian tạo bản đồ đã sắp xếp.
Bản đồ sắp xếp được sử dụng khi bạn muốn sắp xếp cặp khóa, giá trị cơ bản (theo khóa). Bằng cách này, sẽ dễ dàng hơn để truy xuất các hoạt động tối thiểu, tối đa hoặc thực hiện dựa trên phạm vi.
Cây tìm kiếm nhị phân tự cân bằng là gì?
Từ wikipedia,
tự cân bằng (hoặc chiều cao cân bằng) cây tìm kiếm nhị phân là bất kỳ cây tìm kiếm nhị phân nút dựa trên tự động giữ chiều cao của nó (số tối đa các cấp dưới root) nhỏ đối mặt với việc chèn và xóa mục tùy ý.
Một lần nữa, cây đỏ đen trong một triển khai BST tự cân bằng.Có others như cây ALV, vv Trường hợp xấu nhất cho bất kỳ hoạt động nào trên BST bình thường là O(n). Ưu điểm chính của việc sử dụng BST cân bằng trên BST bình thường/không cân bằng là trường hợp xấu nhất của tất cả các hoạt động được đưa xuống O(logn) chỉ với một chi phí nhỏ liên quan đến việc sắp xếp lại các nút khi chèn/xóa. Hãy xem this.
Vì vậy, TreeMap là gì?
A TreeMap là triển khai SortedMap.
TreeMap và cây đỏ đen liên quan như thế nào?
Không, chúng không có. Về mặt lý thuyết, bạn có thể sử dụng bất kỳ Cây tìm kiếm nhị phân nào để triển khai TreeMap. Để có được kết quả tốt, chúng tôi sử dụng Cây tìm kiếm nhị phân tự cân bằng có độ phức tạp thấp hơn để chèn, xóa và truy xuất hoạt động. Trong trường hợp Java, cây đỏ đen được sử dụng. Tôi không biết lý do chính xác là tại sao cây đỏ đen được sử dụng, nhưng tôi tin rằng có một.