Định nghĩa :
Một cây nhị phân tìm kiếm cân bằng ( AVL Trees ) bao gồm những yếu tố :

• Chiều cao cây con trái và cây con phải của gốc cây cha  phải chênh lệch nhau không quá 1

• Bản thân cây con trái và cây con phải cũng là cây AVL

Ta kí hiệu chiều cao cây con trái cao hơn là / , chiều cao cây con phải cao hơn là : \ và chiều cao 2 cây con bằng nhau là _ , ta sẽ có vài ví dụ như sau :

 

 Cây AVL với chiều cao h :

Chiều cao lớn nhất của cây nhị phân AVL :

Chiều cao lớn nhất của cây AVL có chính xác là n nút ? Để trả lời câu hỏi này, ta hãy xem xét bên dưới.

Gọi F_h là cây nhị phân AVL có chiều cao là h có số nút ít nhất, F_l, F_r lần lượt là cây con trái và phải tương ứng của cây Fh, khi đó F_l hoặc F_r phải có chiều cao là h-2/

Giả sử cây F_l có chiều cao h-1, và F_r có chiều cao là h-2. Lưu ý F_l là cây AVL có số nút ít nhất trong số các cây AVL có chiều cao h-1, tương tự thì F_r có số nút nhỏ nhất trong số các cây AVL có chiều cao h-2. Như vậy ta có:

| F_h| = | F_{h - 1}| + | F_{h - 2}| + 1

trong đó | F_h|  biểu thị số nút của F_h, cây AVL cực tiểu còn gọi là là cây Fibonacci, | F₀| = 1 và | F₁| =2 . Thêm 1 vào cả 2 bên ta được :

| F_h| + 1 = (| F_{h - 1}| + 1) + (| F_{h - 2}| + 1)

 như cậy | F_h| + 1 là số Fibonacci, sử dụng công thức gần đúng của số Fibonacci ta sẽ có :

| F_h| + 1 

=> h  1.44log| F_n|
=> Với cây AVL có n nút, chiều cao là :     h 1.44log n
=> Chiều cao tệ nhất của cây AVL với n nút là  h 1.44log n