Cân bằng cây: Cây AVL

4.1 Vấn đề của cây không cân bằng

Ở cây thông thường (không cân bằng), khi thêm phần tử có thể xuất hiện các hiệu ứng không mong muốn.

1. Tăng chiều cao của cây:

Trong cây không cân bằng, chiều cao có thể đạt đến n (ở đâu n là số lượng nút), điều này dẫn đến suy giảm hiệu suất.

Thời gian thực hiện các thao tác cơ bản (tìm kiếm, chèn, xóa) trong tình huống xấu nhất trở thành O(n).

2. Phân phối không đồng đều các nút:

Trong cây không cân bằng, một số cây con có thể chứa nhiều nút hơn rất nhiều so với các cây con khác, điều này dẫn đến việc sử dụng bộ nhớ không hiệu quả và tăng thời gian xử lý.

3. Hiệu suất thực hiện các thao tác bị giảm:

Trong cây không cân bằng, các thao tác tìm kiếm, chèn và xóa đòi hỏi nhiều thời gian hơn do chiều cao cây tăng lên.

Ví dụ về cây không cân bằng:

Trong ví dụ này, cây thực sự trở thành danh sách liên kết, và thời gian thực hiện các thao tác trở thành tuyến tính.

4.2 Định nghĩa cây AVL và các tính chất của nó

Cây AVL (được đặt theo tên của các nhà phát minh của nó, Adelson-Velsky và Landis) là một loại cây tìm kiếm nhị phân cân bằng, trong đó đối với bất kỳ nút nào, sự chênh lệch chiều cao của cây con trái và phải không vượt quá 1.

Các tính chất của cây AVL:

1. Tính cân bằng:

Sự chênh lệch chiều cao của cây con trái và phải của bất kỳ nút nào không vượt quá 1.

Điều này đảm bảo chiều cao của cây là O(log n), ở đâu n là số lượng nút, đảm bảo hiệu quả thực hiện các thao tác tìm kiếm, chèn và xóa.

2. Cây tìm kiếm nhị phân:

Cây AVL có tất cả các tính chất của cây tìm kiếm nhị phân: với bất kỳ nút nào, tất cả các khóa trong cây con trái nhỏ hơn khóa của nút, và tất cả các khóa trong cây con phải lớn hơn khóa của nút.

3. Cân bằng tự động:

Sau mỗi thao tác chèn hoặc xóa, cân bằng của cây được thực hiện để duy trì các tính chất của nó.

4.3 Ví dụ về cân bằng cây

Xoay vòng là các thao tác được thực hiện để khôi phục cân bằng trong cây AVL sau khi chèn hoặc xóa nút. Có bốn loại xoay vòng: xoay trái, xoay phải, xoay trái-phải và xoay phải-trái.

1. Xoay trái (Left Rotation):

Trong xoay trái, nút x được nâng lên, và nút con phải của nó y trở thành cha của nó. Cây con trái của y trở thành cây con phải của x.

2. Xoay phải (Right Rotation):

Trong xoay phải, nút x được nâng lên, và nút con trái của nó y trở thành cha của nó. Cây con phải của y trở thành cây con trái của x.

3. Xoay trái-phải (Left-Right Rotation):

Đầu tiên thực hiện xoay trái trên nút con trái, sau đó thực hiện xoay phải trên chính nút đó.

4. Xoay phải-trái (Right-Left Rotation):

Đầu tiên thực hiện xoay phải trên nút con phải, sau đó thực hiện xoay trái trên chính nút đó.

4.4 Các thao tác chính trong cây AVL

Các thao tác chính trong cây AVL bao gồm chèn, xóa và tìm kiếm.

Chèn (Insertion)

Cần chèn một nút mới vào cây AVL và cân bằng nó, nếu cần thiết.

Các bước:

1. Chèn nút:
   • Bắt đầu từ gốc cây và đệ quy tìm vị trí thích hợp cho nút mới, so sánh giá trị của nó với các nút hiện tại.
   • Chèn nút mới vào vị trí tìm thấy, như trong cây tìm kiếm nhị phân thông thường.
2. Cập nhật chiều cao:
   • Sau khi chèn, cập nhật chiều cao của tất cả các nút trên đường từ nút mới đến gốc.
3. Cân bằng cây:
   • Kiểm tra cân bằng của từng nút trên đường từ nút mới đến gốc.
   • Nếu cân bằng của bất kỳ nút nào bị phá vỡ (sự chênh lệch chiều cao của cây con trái và phải lớn hơn 1), thực hiện xoay tương ứng để khôi phục cân bằng.

Ví dụ:

2. Xóa (Deletion)

Cần xóa một nút từ cây AVL và cân bằng nó, nếu cần thiết.

Các bước:

1. Tìm và xóa nút:

• Bắt đầu từ gốc cây và đệ quy tìm nút để xóa.
• Xóa nút như trong cây tìm kiếm nhị phân thông thường:
• Nếu nút là lá, chỉ cần xóa nó.
• Nếu nút có một con, thay thế nút bằng con của nó.
• Nếu nút có hai con, tìm nút nhỏ nhất trong cây con phải (hoặc lớn nhất trong cây con trái), sao chép giá trị của nó vào nút bị xóa và đệ quy xóa nút nhỏ nhất trong cây con phải.

2. Cập nhật chiều cao:

• Sau khi xóa, cập nhật chiều cao của tất cả các nút trên đường từ nút bị xóa đến gốc.

3. Cân bằng cây:

• Kiểm tra cân bằng của từng nút trên đường từ nút bị xóa đến gốc.
• Nếu cân bằng của bất kỳ nút nào bị phá vỡ, thực hiện xoay tương ứng để khôi phục cân bằng.

Ví dụ:

3. Tìm kiếm (Search)

Cần tìm nút với giá trị nhất định trong cây AVL.

Các bước:

1. Tìm kiếm đệ quy:

• Bắt đầu từ gốc cây và so sánh đệ quy giá trị cần tìm với các nút hiện tại.
• Nếu giá trị nhỏ hơn nút hiện tại, chuyển đến cây con trái.
• Nếu giá trị lớn hơn nút hiện tại, chuyển đến cây con phải.
• Nếu giá trị trùng với nút hiện tại, trả về nút này.

Ví dụ: