Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Hợp nhất hai Max HBLT trong cấu trúc dữ liệu


Chiến lược meld dễ dàng bằng đệ quy. A, B là hai HBLT cần meld. Nếu một rỗng, kết quả là cái kia. Nếu cả hai không rỗng, so sánh gốc. Gốc lớn hơn thành gốc của HBLT meld.

Giả sử A gốc lớn hơn. Cây con trái của A là L. C là max HBLT từ meld(cây con phải của A, B). HBLT cuối: gốc A, cây con L và C. Nếu s(L) < s(C), C thành cây con trái, ngược lại L là trái.

Ví dụ hai HBLT:

Hợp nhất hai Max HBLT trong cấu trúc dữ liệu

Meld: 7 thêm làm con phải 9, nhưng s(L)=0, s(R)=1 → hoán đổi, 7 thành con phải.

Hợp nhất hai Max HBLT trong cấu trúc dữ liệu

Ví dụ khác

Hợp nhất hai Max HBLT trong cấu trúc dữ liệu

Tạm thêm HBLT nhỏ làm con phải HBLT lớn.

Hợp nhất hai Max HBLT trong cấu trúc dữ liệu

Không giữ tính chất HBLT,

Hợp nhất hai Max HBLT trong cấu trúc dữ liệu