Khóa học CTDL và GT

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

// Định nghĩa cấu trúc Node cho cây AVL
struct Node {
    int key;
    Node *left;
    Node *right;
    int height; // Lưu trữ độ cao của cây con gốc là node này

    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

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

// Hàm lấy giá trị lớn nhất (dùng cho tính độ cao)
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Hàm lấy hệ số cân bằng (Balance Factor) của một nút
// BF = height(left) - height(right)
int getBalanceFactor(Node *N) {
    if (N == nullptr)
        return 0;
    return height(N->left) - height(N->right);
}

// Hàm thực hiện xoay phải (Right Rotation)
//   y                               x
//  / \     Right Rotation (y)      /  \
// x   T3   ------------------>   T1    y
// / \                                 / \
//T1  T2                              T2  T3
Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

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

    // Cập nhật độ cao sau khi xoay
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Trả về gốc mới
    return x;
}

// Hàm thực hiện xoay trái (Left Rotation)
//     x                              y
//    / \     Left Rotation (x)      / \
//   T1  y    ----------------->    x   T3
//      / \                        / \
//     T2  T3                     T1  T2
Node *leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

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

    // Cập nhật độ cao sau khi xoay
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Trả về gốc mới
    return y;
}

// Hàm chèn một nút mới vào cây AVL
Node *insert(Node *node, int key) {
    // 1. Thực hiện chèn như cây tìm kiếm nhị phân 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 độ cao của nút hiện tại (sau khi đệ quy trở về)
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. Lấy hệ số cân bằng để kiểm tra
    int balance = getBalanceFactor(node);

    // 4. Nếu nút này mất cân bằng, có 4 trường hợp cần xử lý

    // Trường hợp Left-Left (LL): Chèn vào cây con trái của cây con trái
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // Trường hợp Right-Right (RR): Chèn vào cây con phải của cây con phải
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // Trường hợp Left-Right (LR): Chèn vào cây con phải của cây con trái
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left); // Xoay trái cây con trái
        return rightRotate(node);            // Sau đó xoay phải nút hiện tại
    }

    // Trường hợp Right-Left (RL): Chèn vào cây con trái của cây con phải
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right); // Xoay phải cây con phải
        return leftRotate(node);             // Sau đó xoay trái nút hiện tại
    }

    // Nếu không mất cân bằng, trả về nút (không thay đổi)
    return node;
}

// Hàm duyệt cây theo thứ tự giữa (Inorder Traversal) để kiểm tra
void inorderTraversal(Node *root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->key << " (BF=" << getBalanceFactor(root) << ", H=" << root->height << ") ";
        inorderTraversal(root->right);
    }
}

// Hàm hiển thị cây theo cấu trúc hơi trực quan (dùng cho debug)
void printTree(Node* root, int space = 0, int height = 10) {
    if (root == nullptr) return;
    space += height;
    printTree(root->right, space);
    std::cout << std::endl;
    for (int i = height; i < space; i++) std::cout << " ";
    std::cout << root->key << "(h=" << root->height << ", bf=" << getBalanceFactor(root) << ")\n";
    printTree(root->left, space);
}


int main() {
    Node *root = nullptr;
    int keys[] = {10, 20, 15, 25, 5};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int key : keys) {
        root = insert(root, key);
        std::cout << "\n--- Sau khi chen " << key << " ---" << std::endl;
        // inorderTraversal(root); // Có thể dùng inorder để kiểm tra thứ tự
        printTree(root); // Hoặc dùng printTree để xem cấu trúc
        std::cout << std::endl;
    }

    std::cout << "\n--- Cay AVL cuoi cung (Inorder Traversal) ---" << std::endl;
    inorderTraversal(root);
    std::cout << std::endl;

    // Cần thêm hàm giải phóng bộ nhớ nếu chạy lâu hoặc với nhiều dữ liệu
    // (Ví dụ này đơn giản nên bỏ qua phần giải phóng)

    return 0;
}

// ... (Cần include các hàm và cấu trúc Node từ ví dụ trên) ...

// Hàm tìm nút có giá trị nhỏ nhất trong một cây con (dùng khi xóa nút có 2 con)
Node *minValueNode(Node *node) {
    Node *current = node;
    // Duyệt xuống tận cùng bên trái để tìm nút nhỏ nhất
    while (current && 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
Node *deleteNode(Node *root, int key) {
    // 1. Thực hiện xóa như cây tìm kiếm nhị phân 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 { // Tìm thấy nút cần xóa (key == root->key)
        // Trường hợp 1: Nút lá hoặc chỉ có một con
        if (root->left == nullptr || root->right == nullptr) {
            Node *temp = root->left ? root->left : root->right;

            // Trường hợp không có con (là nút lá)
            if (temp == nullptr) {
                temp = root;
                root = nullptr; // Nút gốc trở thành null
            } else // Trường hợp có một con
                *root = *temp; // Copy 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 đã xóa / nút con cũ
        } else { // Trường hợp 2: 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)
            Node *temp = minValueNode(root->right);

            // Copy nội dung (key) của nút nhỏ nhất vào nút hiện tại
            root->key = temp->key;

            // Xóa nút nhỏ nhất trong cây con phải (nó chắc chắn là nút lá hoặc có 1 con)
            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, không cần cân bằng
    if (root == nullptr)
        return root;

    // 2. Cập nhật độ cao của nút hiện tại
    root->height = 1 + max(height(root->left), height(root->right));

    // 3. Lấy hệ số cân bằng
    int balance = getBalanceFactor(root);

    // 4. Nếu nút này mất cân bằng, thực hiện các phép xoay

    // Trường hợp Left-Left (LL) - Cây con trái bị nặng và cân bằng hoặc nặng về trái
    if (balance > 1 && getBalanceFactor(root->left) >= 0)
        return rightRotate(root);

    // Trường hợp Left-Right (LR) - Cây con trái bị nặng và nặng về phải
    if (balance > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // Trường hợp Right-Right (RR) - Cây con phải bị nặng và cân bằng hoặc nặng về phải
    if (balance < -1 && getBalanceFactor(root->right) <= 0)
        return leftRotate(root);

    // Trường hợp Right-Left (RL) - Cây con phải bị nặng và nặng về trái
    if (balance < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    // Nếu không mất cân bằng, trả về gốc
    return root;
}


// Hàm duyệt cây theo thứ tự giữa (Inorder Traversal) để kiểm tra (copy lại cho đầy đủ)
void inorderTraversal(Node *root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->key << " (BF=" << getBalanceFactor(root) << ", H=" << root->height << ") ";
        inorderTraversal(root->right);
    }
}

// Hàm hiển thị cây theo cấu trúc hơi trực quan (dùng cho debug) (copy lại cho đầy đủ)
void printTree(Node* root, int space = 0, int height = 10) {
    if (root == nullptr) return;
    space += height;
    printTree(root->right, space);
    std::cout << std::endl;
    for (int i = height; i < space; i++) std::cout << " ";
    std::cout << root->key << "(h=" << root->height << ", bf=" << getBalanceFactor(root) << ")\n";
    printTree(root->left, space);
}


int main() {
    Node *root = nullptr;
    int keys_insert[] = {9, 5, 10, 0, 6, 11, -1, 1, 2};
    int n_insert = sizeof(keys_insert) / sizeof(keys_insert[0]);

    for (int key : keys_insert) {
        root = insert(root, key);
    }

    std::cout << "--- Cay AVL sau khi chen tat ca ---" << std::endl;
    printTree(root);
    std::cout << "\n";

    int keys_delete[] = {10, 5, 9}; // Cac khoa can xoa

    for (int key : keys_delete) {
        std::cout << "\n--- Xoa nut " << key << " ---" << std::endl;
        root = deleteNode(root, key);
        printTree(root);
        std::cout << "\n";
    }

    std::cout << "\n--- Cay AVL cuoi cung sau khi xoa (Inorder Traversal) ---" << std::endl;
    inorderTraversal(root);
    std::cout << std::endl;

    // Can them ham giai phong bo nho

    return 0;
}

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

// Định nghĩa cấu trúc Node (giống như trên, bỏ qua phần height và xoay vì chỉ kiểm tra)
struct Node {
    int key;
    Node *left;
    Node *right;

    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

// Hàm trợ giúp đệ quy kiểm tra đồng thời tính BST và tính cân bằng AVL
// Hàm này trả về chiều cao của cây con gốc là node,
// hoặc trả về một giá trị đặc biệt (ví dụ: -2) nếu cây con không hợp lệ (vi phạm BST hoặc AVL)
int checkAVLAndGetHeight(Node* node) {
    // Trường hợp cơ sở: nút rỗng
    if (node == nullptr) {
        return 0; // Chiều cao của cây rỗng là 0
    }

    // Đệ quy kiểm tra cây con trái
    int leftHeight = checkAVLAndGetHeight(node->left);
    // Nếu cây con trái không hợp lệ, trả về ngay
    if (leftHeight == -2) {
        return -2;
    }

    // Đệ quy kiểm tra cây con phải
    int rightHeight = checkAVLAndGetHeight(node->right);
    // Nếu cây con phải không hợp lệ, trả về ngay
    if (rightHeight == -2) {
        return -2;
    }

    // Kiểm tra tính chất BST cục bộ:
    // Nút trái lớn nhất <= nút hiện tại < nút phải nhỏ nhất
    // (Cần cẩn thận với cách triển khai này, một cách tốt hơn là truyền min/max bound)
    // Thay vào đó, chúng ta có thể dùng duyệt inorder và kiểm tra thứ tự tăng dần
    // HOẶC kết hợp kiểm tra BST vào hàm này bằng cách truyền min/max allowed key.
    // Cách truyền min/max bound hiệu quả hơn:
    /*
    int checkAVLAndGetHeight(Node* node, int min_key, int max_key) {
        if (node == nullptr) return 0;
        // Check BST property
        if (node->key < min_key || node->key > max_key) return -2; // Vi pham BST

        int leftHeight = checkAVLAndGetHeight(node->left, min_key, node->key -1); // Cap nhat max_key cho nhanh trai
        if (leftHeight == -2) return -2;

        int rightHeight = checkAVLAndGetHeight(node->right, node->key + 1, max_key); // Cap nhat min_key cho nhanh phai
        if (rightHeight == -2) return -2;

        // Check AVL balance property
        if (std::abs(leftHeight - rightHeight) > 1) return -2; // Vi pham AVL balance

        // Return height if valid
        return std::max(leftHeight, rightHeight) + 1;
    }
    */

    // Cách đơn giản hơn (nhưng kém hiệu quả hơn) là kiểm tra BST riêng, hoặc giả định BST đúng và chỉ check balance
    // Nhưng yêu cầu là "tổng hợp", nên phải check cả hai.
    // Chúng ta sẽ dùng lại phương pháp truyền min/max cho chuẩn BST.

    // Kiểm tra tính chất cân bằng AVL tại nút hiện tại
    if (std::abs(leftHeight - rightHeight) > 1) {
        return -2; // Vi phạm tính chất cân bằng AVL
    }

    // Nếu cả hai cây con hợp lệ và nút hiện tại cân bằng, trả về chiều cao của nút hiện tại
    return std::max(leftHeight, rightHeight) + 1;
}

// Hàm kiểm tra xem một cây nhị phân có phải là cây tìm kiếm nhị phân hợp lệ hay không (phần riêng biệt nếu không dùng cách kết hợp trên)
// bool isBST(Node* node, int min_key, int max_key) {
//     if (node == nullptr) return true;
//     if (node->key < min_key || node->key > max_key) return false;
//     return isBST(node->left, min_key, node->key - 1) &&
//            isBST(node->right, node->key + 1, max_key);
// }

// Hàm kiểm tra xem một cây nhị phân có phải là cây AVL hợp lệ hoàn chỉnh hay không
bool isValidAVL(Node* root) {
    // Cách 1: Kiểm tra BST riêng, sau đó kiểm tra cân bằng riêng
    // Requires isBST and a separate checkHeight function that returns height or error

    // Cách 2: Kết hợp cả hai vào một hàm đệ quy trả về chiều cao hoặc báo lỗi
    // Chúng ta cần một hàm checkAVLAndGetHeightWithBSTCheck truyền min/max bound
    // Để đơn giản hóa ví dụ code trong blog, chúng ta sẽ sử dụng hàm checkAVLAndGetHeight
    // và NGẦM HIỂU rằng tính chất BST đã được đảm bảo bởi cấu trúc cây ban đầu
    // HOẶC coi đây là bài tập chỉ kiểm tra tính cân bằng AVL dựa trên chiều cao giả định đúng.
    // Tuy nhiên, bài tập tổng hợp nên cần check cả hai.
    // Let's implement the combined check with min/max bounds.

    // Hàm trợ giúp đệ quy kiểm tra đồng thời tính BST và tính cân bằng AVL (phiên bản đầy đủ)
    // Trả về chiều cao hoặc -2 nếu không hợp lệ
    auto checkAVLAndGetHeightWithBST =
        [](auto self, Node* node, int min_key, int max_key) -> int {
        // Trường hợp cơ sở: nút rỗng
        if (node == nullptr) {
            return 0; // Chiều cao của cây rỗng là 0
        }

        // Kiểm tra tính chất BST tại nút hiện tại
        if (node->key < min_key || node->key > max_key) {
            // std::cout << "Vi pham BST tai nut " << node->key << std::endl; // Debug
            return -2; // Vi phạm tính chất BST
        }

        // Đệ quy kiểm tra cây con trái
        int leftHeight = self(self, node->left, min_key, node->key - 1);
        // Nếu cây con trái không hợp lệ, trả về ngay
        if (leftHeight == -2) {
            return -2;
        }

        // Đệ quy kiểm tra cây con phải
        int rightHeight = self(self, node->right, node->key + 1, max_key);
        // Nếu cây con phải không hợp lệ, trả về ngay
        if (rightHeight == -2) {
            return -2;
        }

        // Kiểm tra tính chất cân bằng AVL tại nút hiện tại
        if (std::abs(leftHeight - rightHeight) > 1) {
             // std::cout << "Vi pham AVL balance tai nut " << node->key << ". BF = " << (leftHeight - rightHeight) << std::endl; // Debug
            return -2; // Vi phạm tính chất cân bằng AVL
        }

        // Nếu cả hai cây con hợp lệ và nút hiện tại cân bằng, trả về chiều cao của nút hiện tại
        return std::max(leftHeight, rightHeight) + 1;
    };

    // Bắt đầu kiểm tra từ gốc với giới hạn min/max ban đầu là vô cực
    return checkAVLAndGetHeightWithBST(checkAVLAndGetHeightWithBST, root, std::numeric_limits<int>::min(), std::numeric_limits<int>::max()) != -2;
}


// Hàm tạo một cây nhị phân MẤT CÂN BẰNG AVL (nhưng vẫn là BST) để kiểm tra
Node* createUnbalancedAVLTree() {
    Node* root = new Node(20);
    root->left = new Node(10);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->left->right = new Node(15);
    root->left->left->left = new Node(3); // Nút 3 gây mất cân bằng tại 10, rồi tại 20

    // Cây này là BST, nhưng nút 10 có balance factor 2, nút 20 có balance factor 2
    return root;
}

// Hàm tạo một cây nhị phân KHÔNG PHẢI BST (nhưng có thể trông cân bằng) để kiểm tra
Node* createNonBSTTree() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(3);
    root->left->right = new Node(12); // Lỗi BST: 12 ở cây con trái của 10 nhưng lớn hơn 10
    return root;
}


int main() {
    // Test case 1: Cây AVL hợp lệ (từ ví dụ chèn ban đầu)
    Node *avl_root = nullptr;
    int keys_insert[] = {10, 20, 15, 25, 5};
    for (int key : keys_insert) {
         // Cần sử dụng hàm insert từ ví dụ 1 để đảm bảo nó là AVL
         // Để test hàm isValidAVL, chúng ta sẽ tạo cây thủ công hoặc dùng hàm insert đầy đủ
         // Tạm dùng hàm insert từ ví dụ 1 (cần copy toàn bộ code struct Node và hàm insert)
         // Giả sử hàm insert đã có ở đây:
         // avl_root = insert(avl_root, key);
    }

    // Tạo cây AVL hợp lệ thủ công cho đơn giản ví dụ này
    Node* valid_avl = new Node(15);
    valid_avl->left = new Node(10);
    valid_avl->right = new Node(20);
    valid_avl->left->left = new Node(5);
    valid_avl->right->right = new Node(25);


    std::cout << "--- Kiem tra Cay AVL hop le 1 ---" << std::endl;
    if (isValidAVL(valid_avl)) {
        std::cout << "-> CAY HOP LE!" << std::endl;
    } else {
        std::cout << "-> CAY KHONG HOP LE!" << std::endl;
    }

    // Test case 2: Cây không phải AVL (mất cân bằng)
    Node* unbalanced_avl = createUnbalancedAVLTree();
     std::cout << "\n--- Kiem tra Cay mat can bang AVL ---" << std::endl;
    if (isValidAVL(unbalanced_avl)) {
        std::cout << "-> CAY HOP LE!" << std::endl;
    } else {
        std::cout << "-> CAY KHONG HOP LE! (Vi pham can bang AVL)" << std::endl;
    }

    // Test case 3: Cây không phải BST
    Node* non_bst = createNonBSTTree();
    std::cout << "\n--- Kiem tra Cay khong phai BST ---" << std::endl;
    if (isValidAVL(non_bst)) {
        std::cout << "-> CAY HOP LE!" << std::endl;
    } else {
        std::cout << "-> CAY KHONG HOP LE! (Vi pham tinh chat BST)" << std::endl;
    }

    // Can them ham giai phong bo nho cho tat ca cac cay da tao

    return 0;
}