Giới thiệu

Định dạng của một cấu trúc cây thay đổi phụ thuộc vào thứ tự chèn dữ liệu của nó. Trong trường hợp xấu nhất, nó có thể có dạng đường tuyến tính (giống với danh sách liên kết), khi đó các thao tác trên cây có hiệu quả thấp nhất. Trong các trường hợp trung bình ta có độ phức tạp thời gian của các thao tác chèn, xóa, và tìm kiếm phần tử trên cây là O(logn), và trong trường hợp xấu nhất là O(n).

Một cây áp dụng các thuật toán giúp định dạng của cây được cân bằng. Được gọi là cây cân bằng. Ta sẽ đi vào tìm hiểu kỹ hơn về cây cân bằng và các thuật toán giúp cây cân bằng ngay dưới đây.

Cây cân bằng – AVL Tree

Có vài thuật toán giúp cho cây cân bằng, trong đó thuật toán cơ bản và nổi tiếng nhất là AVL

AVL là viết tắt của hai tác giả đề xuất ra thuật toán này G.M. Adelson-Velsky và E.M. Landis.

Cây AVL là cây nhị phân tìm kiếm mà sự khác biệt về chiều cao giữa cây con trái và cây con bên phải không vượt quá 1. Các thao tác cơ bản với cây AVL là thêm node hoặc xóa node khỏi cây cũng giống với cây nhị phân tìm kiếm, chỉ có sự khác biệt là ta cần duy trì sự cân bằng của cây (sự khác biệt về chiều cao giữa cây con bên trái và cây con bên phải của các node không được vượt quá 1).

Ưu điểm của cây AVL: Hiệu năng tìm kiếm luôn được đảm bảo kể cả trong trường hợp xấu nhất (bằng O(logN)).

Nhược điểm: Khi chèn phần tử hoặc xóa phần tử khỏi cây thì cần thêm một thao tác đó là giữ cho cây cân bằng.

Hệ số cân bằng (Balance Factor)

Gọi B là giá trị của ( chiều cao của cây con bên trái – chiều cao của cây con bên phải)

Để duy trì sự khác biệt về chiều cao giữa cây con trài và cây con phải ở mỗi node nhỏ hơn hoặc bằng 1, mỗi node sẽ được lưu một giá trị B. Giá trị này được gọi là hệ số cân bằng, những node có trị tuyệt đối của hệ số cân bằng vượt quá 1 thì cần được điều chỉnh lại.

Hệ số cân bằng của các node ở mức cuối cùng (node lá) luôn luôn bằng không.

Hình 1: Hệ số cân bằng của các node trong cây nhị phân

Các phép quay AVL

Khi có một yếu tố gây ra sự mất cân bằng của cây, AVL sẽ thực hiện quá trình tự điều chỉnh để lấy lại sự cân bằng bởi các phép quay, bao gồm:

Quay trái
Quay phải
Quay trái – phải
Quay phải – trái

Ta sẽ đi vào tìm hiểu chi tiết cách hoạt động của từng phép quay. Để đơn giản hóa vấn đề ta sẽ xét những cây có hai node.

Phép quay trái

Trong trường hợp cây ở trạng thái không cân bằng khi một node được chèn vào làm con phải của một cây có một node gốc và một node con phải. Lúc này ta phải thực hiện phép quay trái để đưa cây trở lại trạng thái cân bằng.

Hình 2: Phép quay trái

Ở ví dụ trên, node A trở thành node không cân bằng khi có một node chèn vào cây con bên phải của nó. Chúng ta thực hiện phép quay trái bởi đưa node A trở thành con trái của node B, để đưa cây về trạng thái cân bằng.

Phép quay phải

Trong trường hợp cây ở trạng thái không cân bằng khi một node được chèn vào làm con trái của một cây có một node gốc và một node con trái. Lúc này ta phải thực hiện phép quay phải để đưa cây trở lại trạng thái cân bằng.

Hình 3: Phép quay phải

Ở ví dụ trên, khi thực hiện phép quay phải ta đưa node A (node mất cân bằng) trở thành con phải của node B.

Phép quay trái – phải

Phép quay kết hợp có đôi chút phức tạp hơn so với các phép quay trái và quay phải ở trên. Với phép quay trái-phải, ta sẽ thực hiện việc quay trái trước và quay phải sau đó.

Trạng thái	Thao tác
	Khi một node được chèn vào làm con phải của cây con trái. Điều này làm cho node C bị mất cân bằng. Trong tình huống như vậy ta phải thực hiện phép quay kết hợp trái – phải, để đưa cây trở về trạng thái cân bằng.
	Đầu tiên, trên cây con trái của node C, ta sẽ thực hiện phép quay trái để khiến A trở thành con trái của B.
	Sau khi thực hiện xong một phép quay trái, cây vẫn chưa ở trạng thái cân bằng. Để đưa cây trở về trạng thái cân bằng, ta cần tiếp tục thực hiện một phép quay phải.
	Phép quay phải sẽ đưa B trở thành node gôc mới. Node C trở thành con phải của B.
	Sau phép quay kết hợp, cây đã có trạng thái cân bằng.

Phép quay phải-trái

Phép quay này là kết hợp của phép quay phải và theo sau bởi một phép quay trái.

Trạng thái	Thao tác
	Khi một node được chèn vào làm con trái của cây con phải. Điều này làm cho node A bị mất cân bằng. Trong tình huống như vậy ta phải thực hiện phép quay kết hợp phải – trái, để đưa cây trở về trạng thái cân bằng.
	Đầu tiên, trên cây con phải của node A, ta sẽ thực hiện phép quay phải để khiến C trở thành con phải của B.
	Sau khi thực hiện xong một phép quay phải, cây vẫn chưa ở trạng thái cân bằng. Để đưa cây trở về trạng thái cân bằng, ta cần tiếp tục thực hiện một phép quay trái.
	Phép quay trái tiếp theo sẽ đưa B trở thành node gôc mới. Node A trở thành con trái của B.
	Sau phép quay kết hợp, cây đã có trạng thái cân bằng.

Thêm ví dụ khi chèn phần tử vào cây AVL

Hình dưới đây thể hiện quá trình chèn phần tử vào trong cây nhị phân làm phá vỡ sự cân bằng của cây AVL. Nếu node có giá trị 3 được thêm vào, sẽ có một node có hệ số cân bằng bằng 1 xuất hiện, nhưng ta chưa cần phải điều chỉnh vì hệ số cân bằng chưa vượt quá 1.

Khi node có giá trị bằng 2 được thêm vào sẽ dẫn đến trong cây xuất hiện một node có hệ số cân bằng bằng 2. Lúc này ta cần điều chỉnh để đưa cây về trạng thái cân bằng.

Hình 2: Quá trình chèn dữ liệu làm phá vỡ cân bằng

Quá trính điều chỉnh mất cân bằng

Hình dưới đây mô tả quá trình điều trỉnh lại cây đã bị mất cân bằng khi một node mới được thêm vào bên trái của một node lá.

Hình 3: Điều chỉnh cân bằng khi một node được thêm vào bên trái node lá

Khi node có giá trị bằng 1 được thêm vào cây, các hệ số cân bằng bị phá vỡ.

Ta cần đi tìm node đầu tiên mà hệ số cân bằng bị phá vỡ bởi thực hiện tìm kiếm từ node lá và điều chỉnh lại bằng cách thực hiện một phép quay phải trên cây con có node gốc là node vừa được tìm thấy. Sau phép quay này cây trở về trạng thái cân bằng.

Ta luôn đảm bảo cây được đưa về trạng thái cân bằng sau chỉ một lần điều chỉnh, vì ta thực hiện việc kiểm tra, điều chỉnh sau mỗi lần thêm node vào cây.

Hình dưới đây mô tả quá trình điều trỉnh lại cây đã bị mất cân bằng khi một node mới được thêm vào bên phải của một node lá.

Hình 3: Điều chỉnh cân bằng khi một node được thêm vào bên phải node lá

Khi node có giá trị bằng 3 được thêm vào cây, các hệ số cân bằng trong cây bị phá vỡ.

Ở trường hợp này ta phải thực hiện phép quay kết hợp trái phải.

Các bước thực hiện giống như đã được mô tả ở trên.

Kết luận

Trong bài học này tôi đã giới thiệu các khái niệm cơ bản về cây cân bằng, hệ số cân bằng và các phép quay để đưa cây AVL trở lại trạng thái cân bằng khi nó bị phá vỡ bởi một yếu tố nào đó như việc chèn dữ liệu vào cây.

Trong thực tế còn có các trường hợp khác có thể dẫn đến phá vỡ sự cân bằng của cây như xóa node khỏi cây AVL. Để đưa cây về trạng thái cân bằng sau khi xóa node có đôi phần phức tạp hơn so với trường hợp chèn node vào cây và sẽ được giới thiệu trong bài học sau.

Uncategorized

Cây cân bằng