C++ hợp nhất cây b-

Question

Ví dụ, tôi đã mô hình cây b-cây sau với mỗi nút chứa các cặp thẻ/giá trị. Cây cho biết ưu tiên (hoặc ưu tiên), với gốc cao nhất, xuống đến mức thấp nhất (nhưng đây là ứng dụng cụ thể). Tôi muốn kết hợp một phần cây mới vào phần tử cha, với phần mới chứa các cặp thẻ/giá trị có khả năng phổ biến, tất cả các con trỏ xuống nút ngay phía trên nút lá (một phần cây hoàn toàn trùng lặp mới sẽ không được hợp nhất). Ví dụ.

hiện cặp cây (tag, giá trị) cho biết:

  A,0 
,----------,-------------, 
B,1  B,2   B,3 
     ,-------------, 
    C,1   C,2 

cây mới sáp nhập:

   A,0 
       | 
       B,3 
      ,-----------, 
     C,1   C,2 

cuối cùng cây sáp nhập:

  A,0 
,----------,-----------------, 
B,1  B,2    B,3 
     ,-------------, ,-----------, 
    C,1   C,2 C,1   C,2 

Câu hỏi: có một thanh lịch C + + giải pháp để hợp nhất b-cây này bằng cách sử dụng std container, hoặc có thể với một thư viện như tăng? Cảm ơn.

Answer 1

Bạn có thể sử dụng thư viện tree.hh của Kasper Peeter, đó là GPLv2 và GPLv3.

Đó là STL giống như triển khai cho cây n-ary.

documentation nói rằng có một thuật toán có thể thay đổi, được hợp nhất tên, có thể hợp nhất hai cây. Nó cũng giải thích cách nó đạt được.