Computer >> Máy Tính >  >> Lập trình >> Lập trình

Cây cánh tả thiên về trọng lượng trong cấu trúc dữ liệu


Ở đây chúng ta sẽ thấy một biến thể khác của Leftist Tree. Ở đây chúng ta sẽ xem xét số lượng các nút trong một cây con, thay vì độ dài của một đường ngắn nhất cho nút gốc đến nút bên ngoài. Ở đây chúng ta sẽ xác định trọng số w (x) của nút x, là số lượng nút bên trong trong cây con có gốc x. Nếu x là nút ngoài thì trọng số bằng 0. Nếu x là nút trong thì trọng số lớn hơn tổng trọng số của các nút con.

Đây là một ví dụ về Cây cánh tả thiên lệch trọng lượng (WBLT) -

Giả sử cây nhị phân như thế này -

Cây cánh tả thiên về trọng lượng trong cấu trúc dữ liệu

Nếu chúng ta tính toán các giá trị w (x) cho mỗi nút, nó sẽ như thế này -

Cây cánh tả thiên về trọng lượng trong cấu trúc dữ liệu

Bây giờ định nghĩa của WBLT giống như -

Cây nhị phân được gọi là Cây cánh tả cân bằng trọng số nếu và chỉ khi, tại mọi nút bên trong, w (x) của nút con bên trái lớn hơn hoặc bằng w (x) của nút con bên phải. WBLT tối đa (tối thiểu) là cây tối đa (tối thiểu) cũng là một WBLT.