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

Cây Leftist thiên vị trọng số (Weight-Biased Leftist Tree) trong cấu trúc dữ liệu


Xem biến thể Leftist Tree: xét số nút trong cây con thay vì độ dài đường ngắn nhất từ gốc đến nút ngoại. Định nghĩa trọng số w(x) của nút x = số nút nội trong cây con gốc x. Nếu x là nút ngoại, w=0. Nếu x nội, w = 1 + w(left) + w(right).

Ví dụ cây nhị phân:

Cây Leftist thiên vị trọng số (Weight-Biased Leftist Tree) trong cấu trúc dữ liệu

Giá trị w(x):

Cây Leftist thiên vị trọng số (Weight-Biased Leftist Tree) trong cấu trúc dữ liệu

Định nghĩa WBLT: Cây nhị phân gọi là Weight-Balanced Leftist Tree nếu tại mọi nút nội, w(con trái) ≥ w(con phải). Max (min) WBLT là max (min) tree cũng là WBLT.