Cây AVL là gì?

Mỗi nút trong cây AVL đều theo dõi chiều cao của chính nó: số cạnh trên đường đi dài nhất xuống một nút lá. Nút lá có chiều cao 1, còn cây con rỗng có chiều cao 0. Từ chiều cao của hai nút con, bạn có thể tính hệ số cân bằng của nút đó: height(left) - height(right).

Nút được cân bằng khi hệ số cân bằng của nó là -1, 0 hoặc 1. Quy tắc của cây AVL rất đơn giản: mọi nút đều phải luôn được cân bằng. Bất cứ khi nào thao tác chèn hoặc xóa khiến hệ số cân bằng của một nút thành 2 hoặc -2, cây sẽ thực hiện một phép xoay: sắp xếp lại cục bộ một vài con trỏ để khôi phục sự cân bằng trong thời gian hằng số mà không phá vỡ thứ tự của cây tìm kiếm.

Có bốn trường hợp xoay (trái-trái, phải-phải, trái-phải, phải-trái), nhưng tất cả đều quy về hai thao tác cơ bản: một phép xoay trái đơn và một phép xoay phải đơn. Bạn sẽ tự xây dựng cả hai trong vài bài học tiếp theo.