Giới thiệu

Cây tìm kiếm nhị phân sắp xếp các giá trị: cây con bên trái của mỗi nút chứa các giá trị nhỏ hơn, còn cây con bên phải chứa các giá trị lớn hơn. Cách sắp xếp này giúp tìm kiếm nhanh, nhưng chỉ khi cây vẫn tương đối cân bằng. Nếu chèn các giá trị theo thứ tự đã sắp xếp vào một cây tìm kiếm nhị phân thông thường, cây sẽ thoái hóa thành một đường thẳng, khiến mỗi lần tìm kiếm đều trở thành một lượt quét tuyến tính chậm chạp.

Cây AVL khắc phục điều này bằng cách tự động giữ cân bằng. Sau mỗi lần chèn hoặc xóa, cây kiểm tra xem nút nào bị lệch hay không. Nếu có, cây sẽ thực hiện một điều chỉnh cục bộ nhỏ gọi là phép xoay để khôi phục cân bằng. Dù bạn xây dựng cây theo cách nào, cây AVL cũng không bao giờ thoái hóa thành một đường thẳng.

Trong khóa học này, bạn sẽ tự xây dựng một cây AVL bằng ngôn ngữ bạn chọn: các nút có chiều cao được theo dõi, kiểm tra cân bằng, bốn trường hợp xoay, cùng thao tác chèn và xóa tự cân bằng. Sau đó, bạn sẽ dùng lớp hoàn chỉnh của mình để giải một loạt thử thách luyện tập.