Bài giảng Cấu trúc dữ liệu và giải thuật: Cây tìm kiếm nhị phân cân bằng (AVL)

Tài liệu này cung cấp một cái nhìn tổng quan về cây tìm kiếm nhị phân cân bằng (AVL), một dạng đặc biệt của cây tìm kiếm nhị phân được thiết kế để duy trì hiệu suất tìm kiếm tối ưu bằng cách tự động cân bằng cấu trúc của nó.

Tài liệu này hướng đến sinh viên ngành Khoa học Máy tính, Kỹ thuật Phần mềm và các chuyên gia trong lĩnh vực cấu trúc dữ liệu và giải thuật, những người muốn tìm hiểu sâu về cách hoạt động và ứng dụng của cây AVL.

Cây tìm kiếm nhị phân cân bằng (AVL) là một loại cây tìm kiếm nhị phân tự cân bằng, trong đó chiều cao của cây con trái và cây con phải của bất kỳ nút nào không chênh lệch quá 1. Để duy trì tính cân bằng này, mỗi nút trong cây được gán một hệ số cân bằng có thể là -1 (cây con trái cao hơn), 0 (chiều cao bằng nhau) hoặc +1 (cây con phải cao hơn). Khi có các thao tác thêm hoặc xóa nút làm thay đổi hệ số cân bằng và phá vỡ tính cân bằng của cây, các phép xoay cây sẽ được thực hiện để khôi phục lại trạng thái cân bằng. Có hai loại phép xoay chính: phép xoay đơn (single rotation) và phép xoay kép (double rotation). Phép xoay đơn được áp dụng khi mất cân bằng xảy ra theo một hướng duy nhất (ví dụ: thêm nút vào cây con trái của cây con trái hoặc cây con phải của cây con phải), bao gồm các trường hợp xoay trái hoặc xoay phải. Phép xoay kép được sử dụng khi mất cân bằng xảy ra theo kiểu zig-zag (ví dụ: thêm nút vào cây con phải của cây con trái hoặc cây con trái của cây con phải), và thực chất là sự kết hợp của hai phép xoay đơn liên tiếp, nhằm khôi phục lại trạng thái cân bằng cho cây một cách hiệu quả, đảm bảo các thao tác tìm kiếm, thêm, xóa luôn có độ phức tạp thời gian tối ưu.