Là một lập trình viên khi nào tôi nên xem xét sử dụng cây RB, cây B hoặc cây AVL? Những điểm chính cần được xem xét trước khi quyết định lựa chọn là gì?Khi nào nên chọn cây RB, cây B hoặc cây AVL?
Ai đó có thể giải thích với một kịch bản cho mỗi cấu trúc cây tại sao nó được chọn trên những người khác có tham chiếu đến các điểm chính không?
Hãy điều này với một nhúm muối:
B-cây khi bạn đang quản lý hơn hàng ngàn mặt hàng và bạn đang phân trang chúng từ một đĩa hoặc một số phương tiện lưu trữ chậm.
Cây RB khi bạn đang thực hiện chèn khá thường xuyên, xóa và khôi phục trên cây.
Cây AVL khi chèn và xóa của bạn không thường xuyên tương đối so với các lần truy xuất của bạn.
Chỉ cần thêm một số chi tiết hơn: B-cây có thể có số lượng thay đổi của trẻ em cho phép nó giữ nhiều hồ sơ nhưng vẫn duy trì một cây chiều cao ngắn. RB Tree có các quy tắc ít nghiêm ngặt hơn về việc tái cân bằng, giúp việc chèn/xóa nhanh hơn cây AVL. Ngược lại, cây AVL được cân đối chặt chẽ hơn nên tra cứu nhanh hơn cây RB. – pschang
Cây RB cũng có hiệu suất tốt hơn O (1) đối với sự cân bằng mà làm cho chúng phù hợp hơn cho các cơ sở dữ liệu liên tục với tính năng cuộn ngược và cuộn về phía trước. –
Khi chọn cấu trúc dữ liệu bạn đang kinh doanh tắt các yếu tố như
Tôi sẽ bắt đầu bằng cách đọc các bài viết Wikipedia được Robert Harvey tham chiếu.
Thực tế, khi làm việc bằng các ngôn ngữ như Java, trình lập trình trung bình có xu hướng sử dụng các lớp thu thập được cung cấp. Nếu trong một hoạt động điều chỉnh hiệu suất người ta phát hiện ra rằng hiệu suất thu thập là có vấn đề sau đó người ta có thể tìm kiếm triển khai thay thế. Nó hiếm khi là điều đầu tiên mà một doanh nghiệp dẫn đầu phát triển phải xem xét. Thật hiếm khi người ta cần phải thực hiện các cấu trúc dữ liệu như vậy bằng tay, thường có các thư viện có thể được sử dụng.
Để công bằng, OP đã hỏi 'khi nào tôi nên cân nhắc việc sử dụng', không phải' khi nào tôi nên xem xét triển khai'. Trong khi đoạn cuối cùng là đúng, nó không cung cấp nhiều giá trị trong ngữ cảnh của câu hỏi này. Ngay cả với các thư viện, bạn cần phải hiểu các thuật toán để chọn hiệu quả cấu trúc nào phù hợp nhất với nhu cầu kinh doanh của bạn. – Dan
Tôi nghĩ rằng cây B + là cấu trúc dữ liệu vùng chứa có mục đích chung tốt, ngay cả trong bộ nhớ chính. Ngay cả khi bộ nhớ ảo không phải là vấn đề, tính thân thiện với bộ nhớ cache thường và các cây B + đặc biệt tốt cho việc truy cập tuần tự - hiệu suất tiệm cận tương tự như danh sách được liên kết, nhưng với tính thân thiện với bộ nhớ cache gần với một mảng đơn giản. Tất cả điều này và tìm kiếm O (log n), chèn và xóa.
B + cây không có vấn đề, mặc dù - chẳng hạn như các mục di chuyển xung quanh trong các nút khi bạn chèn/xóa, làm mất hiệu lực con trỏ đến các mục đó. Tôi có một thư viện chứa "con trỏ bảo trì" - con trỏ đính kèm vào nút lá mà họ hiện đang tham chiếu trong một danh sách liên kết, do đó chúng có thể được sửa chữa hoặc vô hiệu hóa tự động. Vì hiếm khi có nhiều hơn một hoặc hai con trỏ, nó hoạt động tốt - nhưng đó là một chút công việc giống nhau.
Một điều nữa là cây B + về cơ bản là như vậy. Tôi đoán bạn có thể loại bỏ hoặc tái tạo các nút không phải lá phụ thuộc vào việc bạn có cần chúng hay không, nhưng với các nút cây nhị phân, bạn sẽ linh hoạt hơn nhiều. Một cây nhị phân có thể được chuyển đổi thành một danh sách liên kết và ngược lại mà không cần sao chép các nút - bạn chỉ cần thay đổi các con trỏ rồi nhớ rằng bạn đang xử lý nó như một cấu trúc dữ liệu khác bây giờ. Trong số những thứ khác, điều này có nghĩa là bạn nhận được khá dễ dàng O (n) sáp nhập của cây - chuyển đổi cả hai cây vào danh sách, hợp nhất chúng, sau đó chuyển đổi trở lại một cây.
Một điều khác là cấp phát bộ nhớ và giải phóng.Trong cây nhị phân, điều này có thể được tách ra khỏi các thuật toán - người dùng có thể tạo một nút rồi gọi thuật toán chèn, và xóa có thể trích xuất các nút (tách chúng ra khỏi cây, nhưng không giải phóng bộ nhớ). Trong B-tree hoặc B + -tree, điều đó rõ ràng không hoạt động - dữ liệu sẽ sống trong một nút nhiều mục. Viết các phương thức chèn "lập kế hoạch" hoạt động mà không sửa đổi các nút cho đến khi chúng biết cần bao nhiêu nút mới và chúng có thể được cấp phát là một thách thức.
Đỏ đen so với AVL? Tôi không chắc nó có tạo nên sự khác biệt lớn nào không. Thư viện của riêng tôi có một lớp "công cụ" dựa trên chính sách để thao tác các nút, với các phương thức cho các danh sách được liên kết kép, cây nhị phân đơn giản, cây phát, cây đỏ đen và treap, bao gồm các chuyển đổi khác nhau. Một số trong những phương pháp đó chỉ được thực hiện bởi vì tôi đã chán tại một thời gian này hay cách khác. Tôi không chắc tôi thậm chí đã thử nghiệm các phương pháp treap. Lý do tôi chọn cây đỏ-đen thay vì AVL là vì cá nhân tôi hiểu các thuật toán tốt hơn - điều đó không có nghĩa là chúng đơn giản hơn, nó chỉ là một lịch sử mà tôi quen thuộc hơn với chúng.
Điều cuối cùng - Ban đầu tôi chỉ phát triển các thùng chứa cây B + của mình làm thử nghiệm. Đó là một trong những thí nghiệm chưa bao giờ kết thúc thực sự, nhưng đó không phải là điều tôi khuyến khích người khác lặp lại. Nếu tất cả những gì bạn cần là một vùng chứa có thứ tự, câu trả lời hay nhất là sử dụng vùng chứa mà thư viện hiện có của bạn cung cấp - ví dụ: std :: map etc trong C++. Thư viện của tôi phát triển qua nhiều năm, phải mất một thời gian để nó ổn định, và tôi chỉ mới phát hiện gần đây về mặt kỹ thuật không di động (phụ thuộc vào một chút hành vi không xác định WRT offsetof).
Trong bộ nhớ B-Tree có lợi thế khi số lượng mục vượt quá 32000 ... Hãy xem speedtest.pdf từ stx-btree.
Vâng, tôi cho một đánh giá cao câu hỏi này - hiện đang trình bày với một sự lựa chọn của fastutil IntAVLTreeSet vs IntRBTreeSet. – Yang