Bài tập

Cây AVL (AVL Tree) - Tăng cường hiệu quả với tìm kiếm

avatar
Huy Erick
00:00 12/04/2024

Bạn đã từng nghe đến cây AVL (AVL Tree) chưa? Cây AVL là một cây tìm kiếm nhị phân tự cân bằng với hiệu suất vượt trội so với cây tìm kiếm nhị phân thông...

Bạn đã từng nghe đến cây AVL (AVL Tree) chưa? Cây AVL là một cây tìm kiếm nhị phân tự cân bằng với hiệu suất vượt trội so với cây tìm kiếm nhị phân thông thường. Trong bài viết này, chúng ta sẽ tìm hiểu về cây AVL và phần quan trọng nhất của nó - Insertion (Thao tác thêm).

1. Tại sao lại sử dụng cây AVL?

Khi nói về cây AVL, không thể không nhắc đến cây BST (Binary Search Tree). Cây AVL là sự nâng cấp của cây BST, vì vậy nếu bạn chưa biết về cây BST, hãy đọc bài viết về cây tìm kiếm nhị phân trước khi tiếp tục.

Cây BST có một điểm yếu là nếu ta thêm các phần tử theo thứ tự tăng dần (hoặc giảm dần), cây sẽ trở thành một danh sách liên kết. Khi đó, thuật toán tìm kiếm trên cây sẽ có độ phức tạp là O(n) chứ không phải O(log n) như trong trường hợp cây không bị lệch.

Xem thêm:

2. Cây AVL là gì?

Cây AVL là cây nhị phân tìm kiếm cân bằng, có độ chênh lệch giữa chiều cao của cây con bên trái và cây con bên phải không vượt quá 1. Điều này có nghĩa là tất cả các cây con của mọi nút trong cây AVL đều cân bằng về chiều cao.

Để hiểu rõ hơn về cách xây dựng cây AVL, các bạn cần nắm vững các yếu tố sau:

  • Khái niệm "chiều cao" của một nút và cách tính.
  • Các kỹ thuật quay cây AVL.
  • Các trường hợp cây bị lệch.

3. Xây dựng cây AVL

Trước tiên, chúng ta cần định nghĩa kiểu dữ liệu cho các nút trong cây AVL. Mỗi nút bao gồm các trường như: data (dữ liệu), left (con trái), right (con phải), height (chiều cao).

Chiều cao của một nút chính là số lượng các nút trên một đường dẫn từ nút đó đến nút NULL. Và theo quy ước, nút NULL có chiều cao bằng 0.

Để xây dựng cây AVL, chúng ta cần thực hiện các bước sau đây:

  1. Thực hiện thao tác Insert (thêm mới) vào cây.
  2. Cập nhật chiều cao của các nút trong cây.
  3. Kiểm tra các trường hợp cây bị lệch và thực hiện các kỹ thuật quay cây để cân bằng cây.

4. Các trường hợp cây bị lệch

Khi làm việc với cây AVL, chúng ta phải xử lý các trường hợp cây bị lệch để đảm bảo cây vẫn cân bằng. Dưới đây là các trường hợp phổ biến:

  1. Trường hợp "Trái trái" (Left left): Đây là trường hợp cây bị lệch sang bên trái.

    • Xảy ra khi: chiều cao của nút con trái lớn hơn chiều cao của nút con phải và giá trị nút mới thêm vào nhỏ hơn giá trị của nút con trái.
    • Xử lý: thực hiện kỹ thuật quay phải để cân bằng cây.

  2. Trường hợp "Trái phải" (Left right): Đây là trường hợp cây bị lệch sang bên trái một chút.

    • Xảy ra khi: chiều cao của nút con trái lớn hơn chiều cao của nút con phải và giá trị nút mới thêm vào lớn hơn giá trị của nút con trái.
    • Xử lý: thực hiện kỹ thuật quay trái trên nút con trái, sau đó thực hiện kỹ thuật quay phải để cân bằng cây.

  3. Trường hợp "Phải phải" (Right right): Đây là trường hợp cây bị lệch sang bên phải.

    • Xảy ra khi: chiều cao của nút con phải lớn hơn chiều cao của nút con trái và giá trị nút mới thêm vào lớn hơn giá trị của nút con phải.
    • Xử lý: thực hiện kỹ thuật quay trái để cân bằng cây.

  4. Trường hợp "Phải trái" (Right left): Đây là trường hợp cây bị lệch sang bên phải một chút.

    • Xảy ra khi: chiều cao của nút con phải lớn hơn chiều cao của nút con trái và giá trị nút mới thêm vào nhỏ hơn giá trị của nút con phải.
    • Xử lý: thực hiện kỹ thuật quay phải trên nút con phải, sau đó thực hiện kỹ thuật quay trái để cân bằng cây.

5. Thao tác Insert (thêm mới)

Để thêm mới một nút vào cây AVL, chúng ta cần thực hiện các bước sau đây:

  1. Thực hiện thao tác Insert (thêm mới) vào cây AVL.
  2. Cập nhật chiều cao của các nút trong cây.
  3. Kiểm tra và xử lý các trường hợp cây bị lệch để đảm bảo cây vẫn cân bằng.

Dưới đây là một ví dụ về chương trình Insertion trong cây AVL:

// Khởi tạo cây
Node* tree = NULL;

// Thêm các phần tử vào cây
tree = Insert(tree, 18);
tree = Insert(tree, 12);
tree = Insert(tree, 30);
tree = Insert(tree, 25);
tree = Insert(tree, 69);
tree = Insert(tree, 23);

// In cây ra console
print2D(tree);

Kết quả console:

      69 (1)
    30 (2)
  25 (3)
23 (1)
18 (2)
    12 (1)

Cảm ơn bạn đã đọc bài viết. Hy vọng rằng những thông tin trên sẽ giúp bạn hiểu rõ hơn về cây AVL và đồng thời cải thiện hiệu suất của thuật toán tìm kiếm trong ứng dụng của mình. Nếu bạn muốn tìm hiểu thêm về các cấu trúc dữ liệu khác, hãy truy cập vào Geeks for Geeks - AVL Tree.

Thân mến.

BÀI LIÊN QUAN
1