Tôi có một sự hiểu biết cơ bản về cách 2-3-4 trees duy trì hoạt động tài sản cân bằng chiều cao sau khi hoạt động để đảm bảo ngay cả trường hợp xấu nhất là O (n logn).Tại sao chúng ta không sử dụng 2-3 hoặc 2-3-4-5 cây?
Nhưng tôi không hiểu nó đủ tốt để biết tại sao chỉ 2-3-4?
Tại sao không 2-3 hoặc 2-3-4-5 v.v ...?
Thành thật mà nói, tôi không biết 2-3-4 cây. Tại lớp Data Structures của tôi, chúng tôi được dạy 2-3 cây, và thành thật mà nói, hầu hết chúng ta đã thực hiện các cây AVL cho phần ướt của bài tập.
Nhưng rõ ràng, có khái quát về loại cây này: (a,b) tree.
Thú vị! Điều này có nghĩa là chúng ta không thể có 3-4 cây, và tôi không chắc tại sao? – Lazer
Tôi không chắc chắn. Điều này có vẻ là một cây khá lý thuyết, và không phải là một trong những thường khám phá ... Không có rất nhiều trên (a, b) cây trên mạng. – cha0site
Một cây vectơ, đẹp. :-) –
Thực hiện 2-3-4 cây thường yêu cầu nhiều lớp (2NODE, 3NODE, 4NODE) hoặc bạn chỉ có NODE có một mảng các mục. Trong trường hợp của nhiều lớp bạn lãng phí rất nhiều thời gian xây dựng và phá hủy các thể hiện nút và sửa chữa chúng là cồng kềnh. Nếu bạn sử dụng một lớp duy nhất với mảng để giữ các mục và trẻ em thì bạn hoặc là thay đổi kích thước mảng liên tục mà là lãng phí tương tự hoặc bạn gió lãng phí hơn một nửa bộ nhớ của bạn trên các phần tử mảng không sử dụng. Nó không chỉ rất hiệu quả so với cây Đỏ-Đen.
Cây đỏ-đen chỉ có một loại cấu trúc nút. Vì các cây Đỏ-Đen có tính nhị nguyên với 2-3-4 cây, cây RB có thể sử dụng các thuật toán giống hệt như 2-3-4 cây (không cần các triển khai phức tạp khó hiểu/phức tạp được mô tả trong Cormen, Leiserson và Rivest dẫn đầu với các cây AA không kém phức tạp hơn thuật toán 2-3-4.)
Vì vậy, các cây Đỏ-Đỏ dễ thực hiện cộng với hiệu quả bộ nhớ/CPU của chúng. (Cây AVL cũng tốt. Chúng tạo ra những cây cân bằng hơn và ngu ngốc chỉ đơn giản là mã hóa nhưng chúng có xu hướng ít hiệu quả hơn do làm việc quá thường xuyên để duy trì một cây nhỏ gọn hơn.)
Oh, and 2- 3-4-5-6 ... vv không được thực hiện bởi vì không có gì đạt được. 2-3-4 có một lợi ích ròng trên 2-3 cây vì chúng có thể được thực hiện mà không cần đệ quy dễ dàng (đệ quy có xu hướng kém hiệu quả hơn, đặc biệt là khi nó không thể được mã hóa theo đuôi đệ quy). Tuy nhiên, B-Cây và Bplus-Cây là khá nhiều 2-3-4-5-6-7-8-9-vv cây nơi kích thước tối đa của các nút, n, được chọn để n hồ sơ có thể được lưu trữ trong một khu vực đĩa đơn. (tức là mỗi sector đĩa là một nút trong cây và kích thước của sector tương đương với số lượng các mục được lưu trữ trong nút.) Điều này là do thời gian tìm kiếm thông qua 512 bản ghi tuyến tính trong bộ nhớ vẫn còn nhanh hơn khi duyệt qua một cấp độ trong cây đòi hỏi một đĩa tìm/lấy. và O (512) vẫn là O (1) và do đó duy trì O (lg n) cho cây.
Nếu bạn đã từng thực hiện một cây 2-3-4 hoặc đỏ đen, bạn sẽ biết rằng nó không phải là rất tầm thường để làm đúng và sau đó kiểm tra. Thậm chí còn có một phiên bản đơn giản của cây đỏ-đen, [cây AA] (http://en.wikipedia.org/wiki/AA_tree), ít đối xứng hơn cây đỏ-đen, nhưng dường như là một thay thế tốt cho nó có độ phức tạp thực hiện thấp hơn. Khi bạn cần nhiều cây con hoặc cây phẳng hơn, bạn đi cho cây b-và hỗ trợ rõ ràng nhiều subnodes một cách thống nhất. –
Plus luôn có những lo lắng về địa phương dữ liệu và chi phí mỗi nút (do chi phí phân bổ). Những loại mối quan tâm này có xu hướng khuyến khích các giải pháp dựa trên mảng (ví dụ: bảng băm) trong thực tế. –