Cây Leftist thiên vị chiều cao (Height-Biased Leftist Tree) trong cấu trúc dữ liệu

Xem Height-Biased Leftist Tree (HBLT). Xét cây nhị phân thêm nút đặc biệt external node thay cho mỗi cây con rỗng. Các nút còn lại gọi Internal Nodes. Khi thêm external node, gọi là extended binary tree.

Nếu không xét cạnh lá, đó là cây nhị phân thực. Còn đây là extended binary tree.

Gọi s(x) = độ dài đường ngắn nhất từ x đến external node trong cây con của x. Nếu x external, s(x)=0. Nếu x internal:

min{s(L), s(R)} + 1

L, R là con trái, phải. Giá trị s của cây:

Định nghĩa HBLT: Cây nhị phân là HBLT khi và chỉ khi tại mọi nút nội, s(con trái) ≥ s(con phải).

Cây trên không phải HBLT. Cha của nút a có s(L)=0, s(R)=1, ngoại trừ đó các nút khác thỏa mãn. Hoán đổi trái/phải của nút đó để thành HBLT.

Định nghĩa khác:

• Max tree (min tree): giá trị nút ≥ (≤) giá trị con.
• Max HBLT: HBLT cũng là max tree. Min HBLT: HBLT cũng là min tree.