Ở đây chúng ta sẽ xem Cây cánh tả cân bằng chiều cao (HBLT) là gì. Hãy xem xét một cây nhị phân trong đó một nút đặc biệt, được gọi là nút bên ngoài thay thế từng cây con trống. Tất cả các nút khác được gọi là Nút nội bộ . Khi một số nút bên ngoài được thêm vào với một số cây nhị phân, thì đó được gọi là cây nhị phân mở rộng .
Nếu chúng ta không xem xét các mép lá của cây này, thì đó là cây nhị phân thực sự. và đây là cây nhị phân mở rộng.
Bây giờ, giả sử s (x) là độ dài của đường đi ngắn nhất từ nút x đến nút bên ngoài trong cây con của nó. Nếu x là một nút bên ngoài, thì s (x) của nó giá trị là 0. Nếu x là nút bên trong, giá trị là -
min{𝑠(𝐿), 𝑠(𝑅)} + 1 Ở đây L và R là con trái và phải của x. Bây giờ chúng ta hãy xem các giá trị s của cây đã cho.
Định nghĩa của HBLT như sau:Cây nhị phân là Cây cánh tả cân bằng chiều cao (HBLT), nếu và chỉ khi, tại mọi nút bên trong, giá trị s của nút con bên trái lớn hơn hoặc bằng giá trị s của nút con bên phải.
Cây trên không phải là HBLT. Nút cha của nút a, có s (L) =0 và s (R) là 1, ngoại trừ tất cả các nút khác đều thỏa mãn quy tắc của HBLT. Vì vậy, nếu chúng ta trái và phải cây con của nút đó, để làm cho nó trở thành HBLT.
Một số định nghĩa khác là -
-
Cây tối đa (cây tối thiểu) là một cây, trong đó giá trị của mỗi nút lớn hơn (nhỏ hơn) hoặc bằng các nút con của nó.
-
HBLT tối đa là HBLT, cũng là cây tối đa, HBLT tối thiểu là HBLT, cũng là cây tối thiểu.