Nhấn vào đây để đọc bằng ngôn ngữ khác: English
Trong khoa học máy tính, một cây AVL (được đặt theo tên của các nhà phát minh Adelson-Velsky và Landis) là một cây tìm kiếm nhị phân tự cân bằng. Đây là cấu trúc dữ liệu đầu tiên được phát minh trong số đó. Trong một cây AVL, độ cao của hai cây con của bất kỳ nút nào cũng chỉ khác nhau tối đa một; nếu vào bất kỳ thời điểm nào chúng khác nhau hơn một, sẽ được thực hiện cân bằng lại để khôi phục tính chất này. Tìm kiếm, chèn và xóa đều mất O(log n) thời gian trong cả trường hợp trung bình và trường hợp xấu nhất, trong đó n là số nút trong cây trước khi thực hiện thao tác. Việc chèn và xóa có thể yêu cầu cây phải được cân bằng lại bằng một hoặc nhiều phép xoay cây.
Hình ảnh động hiển thị việc chèn một số phần tử vào một cây AVL. Nó bao gồm các phép quay trái, phải, trái-phải và phải-trái.
Cây AVL với các yếu tố cân bằng (màu xanh lá cây)
Xoay Trái-Trái
Xoay Phải-Phải
Xoay Trái-Phải
Xoay Phải-Trái
