C++數據結構之AVL樹如何實現

C++數據結構之AVL樹如何實現

AVL樹是一種自平衡的二叉搜索樹，由Adelson-Velsky和Landis在1962年提出。它的特點是每個節點的左右子樹高度差不超過1，因此能夠保證在最壞情況下，查找、插入和刪除操作的時間復雜度為O(log n)。本文將介紹如何在C++中實現AVL樹。

1. AVL樹的基本結構

AVL樹的節點結構通常包含以下幾個部分：

• 數據域：存儲節點的值。
• 左子樹指針：指向左子樹的根節點。
• 右子樹指針：指向右子樹的根節點。
• 高度：記錄當前節點的高度，用于平衡因子的計算。

struct AVLNode {
    int data;
    AVLNode* left;
    AVLNode* right;
    int height;

    AVLNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};

2. AVL樹的基本操作

2.1 獲取節點高度

為了計算平衡因子，我們需要一個函數來獲取節點的高度。如果節點為空，則高度為0。

int getHeight(AVLNode* node) {
    if (node == nullptr) return 0;
    return node->height;
}

2.2 計算平衡因子

平衡因子是節點的左子樹高度減去右子樹高度。如果平衡因子的絕對值大于1，則需要進行旋轉操作來恢復平衡。

int getBalanceFactor(AVLNode* node) {
    if (node == nullptr) return 0;
    return getHeight(node->left) - getHeight(node->right);
}

2.3 更新節點高度

在插入或刪除節點后，需要更新節點的高度。

void updateHeight(AVLNode* node) {
    if (node == nullptr) return;
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
}

2.4 旋轉操作

AVL樹通過旋轉操作來恢復平衡。主要有四種旋轉方式：左旋、右旋、左右旋和右左旋。

2.4.1 左旋

左旋用于處理右子樹過高的情況。

AVLNode* leftRotate(AVLNode* y) {
    AVLNode* x = y->right;
    AVLNode* T2 = x->left;

    x->left = y;
    y->right = T2;

    updateHeight(y);
    updateHeight(x);

    return x;
}

2.4.2 右旋

右旋用于處理左子樹過高的情況。

AVLNode* rightRotate(AVLNode* x) {
    AVLNode* y = x->left;
    AVLNode* T2 = y->right;

    y->right = x;
    x->left = T2;

    updateHeight(x);
    updateHeight(y);

    return y;
}

2.4.3 左右旋

左右旋用于處理左子樹的右子樹過高的情況。

AVLNode* leftRightRotate(AVLNode* z) {
    z->left = leftRotate(z->left);
    return rightRotate(z);
}

2.4.4 右左旋

右左旋用于處理右子樹的左子樹過高的情況。

AVLNode* rightLeftRotate(AVLNode* z) {
    z->right = rightRotate(z->right);
    return leftRotate(z);
}

2.5 插入節點

插入節點的過程與普通二叉搜索樹類似，但在插入后需要檢查平衡因子并進行相應的旋轉操作。

AVLNode* insert(AVLNode* root, int val) {
    if (root == nullptr) return new AVLNode(val);

    if (val < root->data) {
        root->left = insert(root->left, val);
    } else if (val > root->data) {
        root->right = insert(root->right, val);
    } else {
        return root; // 不允許插入重復值
    }

    updateHeight(root);

    int balance = getBalanceFactor(root);

    // 左子樹過高
    if (balance > 1) {
        if (val < root->left->data) {
            return rightRotate(root);
        } else {
            return leftRightRotate(root);
        }
    }

    // 右子樹過高
    if (balance < -1) {
        if (val > root->right->data) {
            return leftRotate(root);
        } else {
            return rightLeftRotate(root);
        }
    }

    return root;
}

2.6 刪除節點

刪除節點的過程也與普通二叉搜索樹類似，但在刪除后需要檢查平衡因子并進行相應的旋轉操作。

AVLNode* deleteNode(AVLNode* root, int val) {
    if (root == nullptr) return root;

    if (val < root->data) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->data) {
        root->right = deleteNode(root->right, val);
    } else {
        if (root->left == nullptr || root->right == nullptr) {
            AVLNode* temp = root->left ? root->left : root->right;
            if (temp == nullptr) {
                temp = root;
                root = nullptr;
            } else {
                *root = *temp;
            }
            delete temp;
        } else {
            AVLNode* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }

    if (root == nullptr) return root;

    updateHeight(root);

    int balance = getBalanceFactor(root);

    // 左子樹過高
    if (balance > 1) {
        if (getBalanceFactor(root->left) >= 0) {
            return rightRotate(root);
        } else {
            return leftRightRotate(root);
        }
    }

    // 右子樹過高
    if (balance < -1) {
        if (getBalanceFactor(root->right) <= 0) {
            return leftRotate(root);
        } else {
            return rightLeftRotate(root);
        }
    }

    return root;
}

3. 總結

AVL樹通過旋轉操作來保持樹的平衡，從而保證了查找、插入和刪除操作的高效性。本文介紹了如何在C++中實現AVL樹的基本操作，包括插入、刪除和旋轉操作。通過理解和掌握這些基本操作，可以更好地應用AVL樹來解決實際問題。