Khóa học CTDL và GT

Bài 32.3. Cây AVL và cân bằng

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Ở các bài trước, chúng ta đã tìm hiểu về Cây Tìm kiếm Nhị phân (Binary Search Tree - BST) - một cấu trúc dữ liệu cực kỳ hữu ích cho việc tìm kiếm, thêm, và xóa dữ liệu một cách hiệu quả với độ phức tạp trung bình là O(log n). Tuy nhiên, chúng ta cũng đã thấy rằng hiệu suất tuyệt vời này chỉ đạt được khi cây ở trạng thái cân bằng (hoặc gần cân bằng).

Vấn đề của Cây Tìm kiếm Nhị phân "Bình thường"

Nhắc lại một chút về BST: thời gian thực hiện các thao tác cơ bản phụ thuộc vào chiều cao của cây. Nếu cây cân bằng hoàn hảo, chiều cao là O(log n), cho hiệu suất tìm kiếm/thêm/xóa tối ưu. Nhưng nếu dữ liệu được thêm vào theo một trình tự nhất định (ví dụ: luôn tăng dần hoặc giảm dần), cây có thể bị lệch (skewed), trở thành một danh sách liên kết (linked list) về mặt cấu trúc. Khi đó, chiều cao cây là O(n), và mọi thao tác sẽ mất O(n) thời gian ở trường hợp xấu nhất.

Điều này thật không mong muốn! Chúng ta cần một cách để đảm bảo cây luôn giữ được trạng thái cân bằng hoặc gần cân bằng một cách tự động sau mỗi lần thêm hoặc xóa.

Giải pháp: Cây AVL

Đây chính là lúc Cây AVL (AVL Tree) bước vào sân khấu. Được đặt tên theo các nhà phát minh Adelson-Velsky và Landis, Cây AVL là loại Cây Tìm kiếm Nhị phân Tự cân bằng (Self-Balancing Binary Search Tree) đầu tiên được giới thiệu.

Điểm đặc biệt của Cây AVL là nó luôn duy trì tính chất: đối với bất kỳ nút nào trong cây, chiều cao của cây con bên trái và cây con bên phải của nút đó chỉ chênh lệch nhau tối đa là 1.

Yếu tố Cân bằng (Balance Factor)

Để kiểm tra tính chất này một cách dễ dàng, chúng ta định nghĩa Yếu tố Cân bằng (Balance Factor) của một nút như sau:

Balance Factor (nút) = Chiều cao của cây con bên trái của nút - Chiều cao của cây con bên phải của nút

Theo định nghĩa của Cây AVL, yếu tố cân bằng của mọi nút trong cây phải thuộc tập {-1, 0, 1}.

• Yếu tố cân bằng = 0: Cây con bên trái và bên phải có chiều cao bằng nhau.
• Yếu tố cân bằng = 1: Cây con bên trái cao hơn cây con bên phải 1 đơn vị.
• Yếu tố cân bằng = -1: Cây con bên phải cao hơn cây con bên trái 1 đơn vị.

Nếu yếu tố cân bằng của một nút là 2 hoặc -2 (hoặc lớn hơn/nhỏ hơn), thì cây con gốc tại nút đó đã bị mất cân bằng và cần được "sửa chữa".

Duy trì Cân bằng: Phép Quay (Rotations)

Khi chúng ta thêm hoặc xóa một nút trong Cây AVL, cây có thể bị mất cân bằng tại một hoặc nhiều nút trên đường đi từ nút được thêm/xóa lên đến gốc. Để khôi phục lại tính chất AVL, chúng ta sử dụng các thao tác gọi là phép quay (rotations).

Có bốn loại phép quay cơ bản, được nhóm thành hai loại chính:

1. Phép quay đơn (Single Rotations):

   • Quay phải (Right Rotation): Được sử dụng khi cây con bên trái của một nút bị mất cân bằng (Yếu tố cân bằng > 1), và sự mất cân bằng xảy ra ở cây con bên trái của nút con bên trái đó (trường hợp "trái-trái", LL - Left-Left).
   • Quay trái (Left Rotation): Được sử dụng khi cây con bên phải của một nút bị mất cân bằng (Yếu tố cân bằng < -1), và sự mất cân bằng xảy ra ở cây con bên phải của nút con bên phải đó (trường hợp "phải-phải", RR - Right-Right).

2. Phép quay đôi (Double Rotations):

   • Quay trái-phải (Left-Right Rotation): Được sử dụng khi cây con bên trái của một nút bị mất cân bằng (Yếu tố cân bằng > 1), nhưng sự mất cân bằng xảy ra ở cây con bên phải của nút con bên trái đó (trường hợp "trái-phải", LR - Left-Right). Đây là sự kết hợp của Quay trái (trên nút con bên trái) và sau đó Quay phải (trên nút hiện tại).
   • Quay phải-trái (Right-Left Rotation): Được sử dụng khi cây con bên phải của một nút bị mất cân bằng (Yếu tố cân bằng < -1), nhưng sự mất cân bằng xảy ra ở cây con bên trái của nút con bên phải đó (trường hợp "phải-trái", RL - Right-Left). Đây là sự kết hợp của Quay phải (trên nút con bên phải) và sau đó Quay trái (trên nút hiện tại).

Hãy xem xét chi tiết hơn về cách các phép quay này hoạt động.

Minh họa Phép quay (Conceptual - Không dùng hình ảnh)

Tưởng tượng một nút gốc y bị mất cân bằng.

• Quay phải (Right Rotation):

  • Xảy ra khi y mất cân bằng do nhánh trái quá nặng (BF(y) > 1), và nút chèn/xóa xảy ra trong cây con trái của y->left. Trường hợp đơn giản nhất là LL, nơi y->left cũng nặng về bên trái (BF(y->left) >= 0).
  • Gọi x = y->left.
  • Mục tiêu: Biến x thành gốc mới của cây con này.
  • Cách thực hiện:
    • x trở thành nút gốc mới.
    • Cây con bên phải của x (gọi là T2) trở thành cây con bên trái của y.
    • y trở thành cây con bên phải của x.
  • Cấu trúc trước: y (gốc), trái x, phải T3. x (con của y), trái T1, phải T2. (T1, T2, T3 là các cây con)
  • Cấu trúc sau: x (gốc mới), trái T1, phải y. y (con của x), trái T2, phải T3.
  • Phép quay phải giữ nguyên tính chất BST: mọi khóa trong T1 < khóa của x, mọi khóa trong T2 < khóa của y (và > khóa của x), mọi khóa trong T3 > khóa của y.

• Quay trái (Left Rotation):

  • Ngược lại với Quay phải. Xảy ra khi x mất cân bằng do nhánh phải quá nặng (BF(x) < -1), và sự mất cân bằng xảy ra trong cây con phải của x->right. Trường hợp đơn giản nhất là RR, nơi x->right cũng nặng về bên phải (BF(x->right) <= 0).
  • Gọi y = x->right.
  • Mục tiêu: Biến y thành gốc mới của cây con này.
  • Cách thực hiện:
    • y trở thành nút gốc mới.
    • Cây con bên trái của y (gọi là T2) trở thành cây con bên phải của x.
    • x trở thành cây con bên trái của y.
  • Cấu trúc trước: x (gốc), trái T1, phải y. y (con của x), trái T2, phải T3.
  • Cấu trúc sau: y (gốc mới), trái x, phải T3. x (con của y), trái T1, phải T2.
  • Phép quay trái giữ nguyên tính chất BST.

• Quay trái-phải (Left-Right Rotation):

  • Xảy ra khi y mất cân bằng do nhánh trái quá nặng (BF(y) > 1), nhưng sự mất cân bằng xảy ra trong cây con bên phải của y->left. Trường hợp LR, nơi y->left nặng về bên phải (BF(y->left) < 0).
  • Cách thực hiện:
    1. Thực hiện Quay trái trên cây con bên trái của y (tức là trên y->left). Thao tác này chuyển trường hợp LR thành trường hợp LL.
    2. Sau đó, thực hiện Quay phải trên y (gốc ban đầu).

• Quay phải-trái (Right-Left Rotation):

  • Xảy ra khi x mất cân bằng do nhánh phải quá nặng (BF(x) < -1), nhưng sự mất cân bằng xảy ra trong cây con bên trái của x->right. Trường hợp RL, nơi x->right nặng về bên trái (BF(x->right) > 0).
  • Cách thực hiện:
    1. Thực hiện Quay phải trên cây con bên phải của x (tức là trên x->right). Thao tác này chuyển trường hợp RL thành trường hợp RR.
    2. Sau đó, thực hiện Quay trái trên x (gốc ban đầu).

Sau mỗi phép quay, chiều cao của các nút liên quan và yếu tố cân bằng của chúng cần được cập nhật.

Cài đặt Cây AVL bằng C++

Chúng ta sẽ xây dựng cây AVL với các thao tác thêm (insertion) và xóa (deletion) điển hình.

Đầu tiên, định nghĩa cấu trúc nút:

#include <iostream>
#include <algorithm> // For std::max

// Định nghĩa cấu trúc nút của Cây AVL
struct Node {
    int key;
    Node *left;
    Node *right;
    int height; // Chiều cao của cây con gốc tại nút này

    // Constructor
    Node(int val) : key(val), left(nullptr), right(nullptr), height(1) {}
};

Các hàm phụ trợ: tính chiều cao và yếu tố cân bằng, cập nhật chiều cao.

// Hàm lấy chiều cao của nút
int height(Node *N) {
    if (N == nullptr)
        return 0;
    return N->height;
}

// Hàm tính yếu tố cân bằng của nút
int getBalanceFactor(Node *N) {
    if (N == nullptr)
        return 0;
    return height(N->left) - height(N->right);
}

// Hàm cập nhật chiều cao của nút (dựa vào chiều cao của các nút con)
void updateHeight(Node *N) {
    if (N != nullptr)
        N->height = 1 + std::max(height(N->left), height(N->right));
}

Tiếp theo, cài đặt các phép quay đơn giản:

// Hàm thực hiện phép quay phải (Right Rotation)
// y là nút gốc của cây con bị mất cân bằng bên trái (LL hoặc LR)
Node *rightRotate(Node *y) {
    Node *x = y->left; // x là nút con trái của y
    Node *T2 = x->right; // T2 là cây con phải của x

    // Thực hiện quay
    x->right = y;
    y->left = T2;

    // Cập nhật chiều cao của các nút liên quan
    // Nút y ở dưới nên chiều cao của y cần được cập nhật trước
    updateHeight(y);
    // Nút x ở trên nên chiều cao của x được cập nhật sau
    updateHeight(x);

    // Trả về gốc mới của cây con đã quay (bây giờ là x)
    return x;
}

// Hàm thực hiện phép quay trái (Left Rotation)
// x là nút gốc của cây con bị mất cân bằng bên phải (RR hoặc RL)
Node *leftRotate(Node *x) {
    Node *y = x->right; // y là nút con phải của x
    Node *T2 = y->left; // T2 là cây con trái của y

    // Thực hiện quay
    y->left = x;
    x->right = T2;

    // Cập nhật chiều cao của các nút liên quan
    // Nút x ở dưới nên chiều cao của x cần được cập nhật trước
    updateHeight(x);
    // Nút y ở trên nên chiều cao của y được cập nhật sau
    updateHeight(y);

    // Trả về gốc mới của cây con đã quay (bây giờ là y)
    return y;
}

Bây giờ là phần quan trọng: Cài đặt hàm insert. Hàm này sẽ hoạt động tương tự như BST thông thường ở phần đệ quy xuống, nhưng khi đệ quy trở về, nó sẽ kiểm tra yếu tố cân bằng và thực hiện các phép quay nếu cần.

// Hàm thêm một nút mới vào cây AVL
// root: gốc hiện tại của cây con
// key: giá trị cần thêm
// Trả về gốc mới của cây con sau khi thêm và cân bằng
Node *insert(Node *node, int key) {
    // 1. Thực hiện chèn nút như trong BST thông thường
    if (node == nullptr)
        return new Node(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // Các khóa trùng lặp không được phép trong ví dụ này
        return node;

    // 2. Cập nhật chiều cao của nút hiện tại (sau khi chèn ở cây con)
    updateHeight(node);

    // 3. Lấy yếu tố cân bằng để kiểm tra xem nút này có bị mất cân bằng không
    int balanceFactor = getBalanceFactor(node);

    // 4. Nếu nút bị mất cân bằng, thực hiện các phép quay phù hợp

    // Trường hợp LL (Left-Left)
    // Mất cân bằng bên trái (balanceFactor > 1) và key được chèn vào cây con trái của nút con trái
    if (balanceFactor > 1 && key < node->left->key)
        return rightRotate(node);

    // Trường hợp RR (Right-Right)
    // Mất cân bằng bên phải (balanceFactor < -1) và key được chèn vào cây con phải của nút con phải
    if (balanceFactor < -1 && key > node->right->key)
        return leftRotate(node);

    // Trường hợp LR (Left-Right)
    // Mất cân bằng bên trái (balanceFactor > 1) nhưng key được chèn vào cây con phải của nút con trái
    if (balanceFactor > 1 && key > node->left->key) {
        node->left = leftRotate(node->left); // Quay trái nút con trái để chuyển thành LL
        return rightRotate(node); // Sau đó quay phải nút hiện tại
    }

    // Trường hợp RL (Right-Left)
    // Mất cân bằng bên phải (balanceFactor < -1) nhưng key được chèn vào cây con trái của nút con phải
    if (balanceFactor < -1 && key < node->right->key) {
        node->right = rightRotate(node->right); // Quay phải nút con phải để chuyển thành RR
        return leftRotate(node); // Sau đó quay trái nút hiện tại
    }

    // 5. Nếu không mất cân bằng, trả về con trỏ nút gốc hiện tại
    return node;
}

Giải thích code insert:

• Hàm insert đệ quy tương tự như BST. Khi tìm thấy vị trí thích hợp hoặc nút đã tồn tại, nó trả về nút mới hoặc nút hiện tại.
• Điểm khác biệt chính: Sau khi gọi đệ quy insert cho cây con (dòng node->left = insert(...) hoặc node->right = insert(...)), hàm sẽ thực hiện các bước sau:
  • Cập nhật chiều cao: Chiều cao của nút hiện tại (node) có thể đã thay đổi do cây con của nó thay đổi (do chèn hoặc do phép quay xảy ra ở tầng dưới).
  • Tính yếu tố cân bằng: Dựa vào chiều cao mới để kiểm tra balanceFactor.
  • Kiểm tra và quay: Nếu balanceFactor > 1 hoặc < -1, nghĩa là cây con gốc tại node đã bị mất cân bằng. Chúng ta kiểm tra thêm vị trí của key vừa chèn so với node->left (nếu BF > 1) hoặc node->right (nếu BF < -1) để xác định là trường hợp LL, RR, LR, hay RL và gọi phép quay (hoặc phép quay kép) tương ứng. Phép quay sẽ trả về gốc mới của cây con đã được cân bằng, và con trỏ liên kết từ nút cha sẽ được cập nhật (return rightRotate(node) hoặc return leftRotate(node)).
  • Nếu cây không mất cân bằng tại nút này (balanceFactor là -1, 0, hoặc 1), đơn giản là trả về nút hiện tại.
• Quá trình này lặp lại trên đường đệ quy trở về gốc, đảm bảo rằng mọi nút trên đường từ nút chèn đến gốc đều được kiểm tra và cân bằng nếu cần.

Ví dụ minh họa chèn

Hãy chèn các giá trị sau vào một cây AVL trống: 10, 20, 30, 40, 50, 25.

• Chèn 10: Cây: 10. Cân bằng.
• Chèn 20: Cây: 10 -> 20 (phải). Cân bằng.
• Chèn 30: Cây: 10 -> 20 -> 30. Nút 10 có BF = 0 - 2 = -2 (mất cân bằng RR).
  • Cần quay trái tại nút 10. Gốc mới là 20.
  • Cây sau quay: 20 (gốc), trái 10, phải 30. Cân bằng hoàn hảo.
• Chèn 40: Chèn vào phải 30. Cây: 20 -> 30 -> 40. Nút 20 có BF = 1 - 2 = -1 (cân bằng). Nút 30 có BF = 0 - 1 = -1 (cân bằng). Cây cân bằng.
• Chèn 50: Chèn vào phải 40. Cây: 20 -> 30 -> 40 -> 50. Nút 30 có BF = 0 - 2 = -2 (mất cân bằng RR).
  • Cần quay trái tại nút 30. Gốc mới là 40. 30 trở thành con trái của 40.
  • Cây sau quay (tại cây con gốc 30): 20 -> 40 (con phải của 20), 40 trái 30, 40 phải 50.
  • Kiểm tra lại nút 20: BF = 1 - 2 = -1. Cân bằng.
  • Cây cân bằng.
• Chèn 25: Chèn vào giữa 20 và 30. Cây: 20 (gốc), trái 10, phải 40. 40 trái 30, 40 phải 50. Chèn 25: 20 -> 40 -> 30 -> 25.
  • Đường đi chèn: 20 -> 40 -> 30 -> 25. Nút chèn 25.
  • Quay về 30: 30 có 25 bên trái. Cập nhật chiều cao 30. BF(30) = 1-0 = 1. Cân bằng.
  • Quay về 40: Cây con trái của 40 bây giờ gốc là 30 (đã có thêm 25). Cập nhật chiều cao 40. BF(40) = height(30) - height(50) = 2 - 1 = 1. Cân bằng.
  • Quay về 20: Cây con phải của 20 bây giờ gốc là 40 (đã có thêm 25 trong cây con của 40). Cập nhật chiều cao 20. BF(20) = height(10) - height(40) = 1 - 3 = -2. Mất cân bằng!
  • Nút 20 mất cân bằng bên phải (BF -2). Nút con phải của 20 là 40. Kiểm tra key 25 so với key của nút con phải 40: 25 < 40. Đây là trường hợp RL (Right-Left).
  • Thực hiện Quay phải trên nút con phải của 20 (tức là trên nút 40). Nút 40 có con trái 30, con phải 50. Key chèn 25 ở cây con trái của 40 (cụ thể là dưới 30). Quay phải 40: 30 (gốc mới của cây con này), trái 25, phải 40. 40 giữ con phải 50.
  • Cây con phải của 20 giờ là 30 (trái 25, phải 40). Nút 20 có con trái 10, con phải 30.
  • Tiếp theo, thực hiện Quay trái trên nút 20. 20 có con trái 10, con phải 30. Quay trái 20: 30 (gốc mới), trái 20, phải 40. 20 giữ con trái 10. 30 giữ con phải 40. 40 giữ con phải 50.
  • Cây sau quay kép: 30 (gốc), trái 20, phải 40. 20 trái 10. 40 phải 50.
  • Cây cân bằng trở lại.

Đây là cách các phép quay hoạt động để giữ cho cây AVL luôn cân bằng sau khi thêm.

Cài đặt Xóa (Deletion)

Xóa trong cây AVL phức tạp hơn một chút so với thêm. Nó cũng bắt đầu bằng việc tìm và xóa nút như trong BST thông thường. Sau khi xóa, chúng ta cũng phải đi ngược lên đường đệ quy để kiểm tra và cân bằng lại cây.

// Hàm tìm nút có giá trị nhỏ nhất trong cây con (dùng cho xóa nút có 2 con)
Node *minValueNode(Node *node) {
    Node *current = node;
    while (current->left != nullptr)
        current = current->left;
    return current;
}

// Hàm xóa một nút có key cho trước khỏi cây AVL
// root: gốc hiện tại của cây con
// key: giá trị cần xóa
// Trả về gốc mới của cây con sau khi xóa và cân bằng
Node *deleteNode(Node *root, int key) {
    // 1. Thực hiện xóa nút như trong BST thông thường
    if (root == nullptr)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else { // Nút cần xóa đã được tìm thấy
        // Trường hợp 1: Nút lá hoặc có 1 con
        if ((root->left == nullptr) || (root->right == nullptr)) {
            Node *temp = root->left ? root->left : root->right;

            // Trường hợp nút lá (temp == nullptr)
            if (temp == nullptr) {
                temp = root;
                root = nullptr; // root trở thành null
            } else // Trường hợp có 1 con
                *root = *temp; // Sao chép nội dung của con vào nút hiện tại

            delete temp; // Giải phóng bộ nhớ của nút cũ (temp trỏ tới)
        } else { // Trường hợp 2: Nút có 2 con
            // Tìm nút kế vị (inorder successor) - nút nhỏ nhất ở cây con phải
            Node *temp = minValueNode(root->right);

            // Sao chép giá trị của nút kế vị vào nút hiện tại
            root->key = temp->key;

            // Xóa nút kế vị (lúc này đã chuyển sang trường hợp 1 hoặc nút lá)
            root->right = deleteNode(root->right, temp->key);
        }
    }

    // Nếu cây chỉ còn 1 nút hoặc rỗng sau khi xóa, trả về ngay
    if (root == nullptr)
        return root;

    // 2. Cập nhật chiều cao của nút hiện tại (sau khi xóa ở cây con)
    updateHeight(root);

    // 3. Lấy yếu tố cân bằng để kiểm tra xem nút này có bị mất cân bằng không
    int balanceFactor = getBalanceFactor(root);

    // 4. Nếu nút bị mất cân bằng, thực hiện các phép quay phù hợp
    // Lưu ý: Sau khi xóa, sự mất cân bằng có thể lan truyền lên trên, và BF có thể là 2 hoặc -2.
    // Chúng ta cần kiểm tra BF của cây con để xác định trường hợp quay.

    // Trường hợp LL (Left-Left Imbalance)
    // Mất cân bằng bên trái (balanceFactor > 1)
    // và cây con trái nặng bên trái (BF(left child) >= 0)
    if (balanceFactor > 1 && getBalanceFactor(root->left) >= 0)
        return rightRotate(root);

    // Trường hợp LR (Left-Right Imbalance)
    // Mất cân bằng bên trái (balanceFactor > 1)
    // và cây con trái nặng bên phải (BF(left child) < 0)
    if (balanceFactor > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // Trường hợp RR (Right-Right Imbalance)
    // Mất cân bằng bên phải (balanceFactor < -1)
    // và cây con phải nặng bên phải (BF(right child) <= 0)
    if (balanceFactor < -1 && getBalanceFactor(root->right) <= 0)
        return leftRotate(root);

    // Trường hợp RL (Right-Left Imbalance)
    // Mất cân bằng bên phải (balanceFactor < -1)
    // và cây con phải nặng bên trái (BF(right child) > 0)
    if (balanceFactor < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    // 5. Nếu không mất cân bằng, trả về con trỏ nút gốc hiện tại
    return root;
}

Giải thích code deleteNode:

• Hàm này cũng là đệ quy.
• Phần 1: Xóa BST cơ bản: Giống như BST thông thường, nó tìm nút cần xóa. Nếu tìm thấy, nó xử lý 3 trường hợp (nút lá, 1 con, 2 con). Đặc biệt, khi xóa nút có 2 con, nó tìm nút kế vị (min value trong cây con phải), sao chép giá trị, và đệ quy xóa nút kế vị (nút kế vị chắc chắn chỉ có tối đa 1 con trái).
• Phần 2, 3, 4, 5: Cân bằng AVL: Sau khi việc xóa ở cây con hoàn tất và hàm đệ quy quay trở lại, chúng ta thực hiện các bước tương tự như khi chèn: cập nhật chiều cao của nút hiện tại, tính yếu tố cân bằng.
• Kiểm tra và quay: Nếu balanceFactor > 1 hoặc < -1, cây con gốc tại nút hiện tại bị mất cân bằng. Chúng ta kiểm tra yếu tố cân bằng của cây con bị lệch (root->left nếu BF > 1, root->right nếu BF < -1) để xác định chính xác trường hợp LL, RR, LR, hoặc RL và gọi phép quay phù hợp.
• Lưu ý quan trọng về xóa so với chèn: Khi chèn, chỉ một phép quay (hoặc quay kép) là đủ để khôi phục cân bằng cho toàn bộ cây trên đường đi lên. Khi xóa, có thể cần nhiều phép quay trên đường đi lên, vì việc xóa có thể làm giảm chiều cao của một nhánh, gây mất cân bằng ở các nút cha ở các tầng cao hơn. Tuy nhiên, logic kiểm tra và quay tại mỗi nút trên đường đi vẫn tương tự.

Cài đặt hàm hiển thị (Inorder Traversal)

Để kiểm tra xem cây còn giữ tính chất BST và các thao tác có đúng không, chúng ta dùng duyệt trung thứ tự (inorder traversal).

// Hàm duyệt cây theo thứ tự trung thứ tự (Inorder Traversal)
// Inorder traversal của BST luôn in ra các khóa theo thứ tự tăng dần
void inorder(Node *root) {
    if (root != nullptr) {
        inorder(root->left);
        std::cout << root->key << " ";
        inorder(root->right);
    }
}

Hàm Main để thử nghiệm

Kết hợp tất cả lại trong hàm main.

// Hàm main để thử nghiệm
int main() {
    Node *root = nullptr;

    /* Xây dựng cây bằng cách chèn các phần tử */
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25); // Chèn 25 gây ra mất cân bằng và quay kép LR/RL

    std::cout << "Cay AVL sau khi chen 10, 20, 30, 40, 50, 25 (inorder):" << std::endl;
    inorder(root);
    std::cout << std::endl;
    // Kết quả mong đợi: 10 20 25 30 40 50 (chứng tỏ vẫn là BST)

    /* Xoa cac phan tu */
    std::cout << "\nXoa 10..." << std::endl;
    root = deleteNode(root, 10);
    std::cout << "Cay AVL sau khi xoa 10 (inorder):" << std::endl;
    inorder(root);
    std::cout << std::endl;
    // Kiểm tra cân bằng sau xóa

    std::cout << "\nXoa 50..." << std::endl;
    root = deleteNode(root, 50);
    std::cout << "Cay AVL sau khi xoa 50 (inorder):" << std::endl;
    inorder(root);
    std::cout << std::endl;
    // Kiểm tra cân bằng sau xóa

    // Thêm nhiều phần tử hơn để kiểm tra cân bằng phức tạp hơn
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 35);
    root = insert(root, 45);
    std::cout << "\nChen them 5, 15, 35, 45 (inorder):" << std::endl;
    inorder(root);
    std::cout << std::endl;

    std::cout << "\nXoa 30 (nut goc hien tai)..." << std::endl;
    root = deleteNode(root, 30);
    std::cout << "Cay AVL sau khi xoa 30 (inorder):" << std::endl;
    inorder(root);
    std::cout << std::endl;

    // Lưu ý: Để trực quan hơn, bạn có thể viết hàm in cây dạng cấu trúc
    // nhưng điều đó khá phức tạp và ngoài phạm vi minh họa cân bằng

    // Giải phóng bộ nhớ (cần hàm xóa toàn bộ cây)
    // deleteTree(root); // Cần cài đặt hàm này để tránh rò rỉ bộ nhớ trong ứng dụng thực tế

    return 0;
}

Tại sao Cây AVL hiệu quả?

Nhờ cơ chế tự động cân bằng thông qua các phép quay, Cây AVL đảm bảo chiều cao của cây luôn là logarit so với số lượng nút n. Cụ thể, chiều cao tối đa của cây AVL với n nút là khoảng 1.44 log₂(n)*. Điều này có nghĩa là các thao tác tìm kiếm, thêm, và xóa luôn có độ phức tạp thời gian là O(log n) trong mọi trường hợp (trường hợp tốt nhất, trung bình, và xấu nhất).

So với BST thông thường có trường hợp xấu nhất là O(n), Cây AVL cung cấp sự đảm bảo về hiệu suất, rất quan trọng trong các ứng dụng cần thời gian phản hồi nhất quán.