C++AVL樹*

圖 7-29   有 grandChild 的左旋操作在二叉搜索樹章節(jié)中，我們提到了在多次插入和刪除操作后，二叉搜索樹可能退化為鏈表。這種情況下，所有操作的時間復(fù)雜度將從 O(log?n) 惡化為 O(n)。

如圖 7-24 所示，經(jīng)過兩次刪除節(jié)點操作，這個二叉搜索樹便會退化為鏈表。

圖 7-24   AVL 樹在刪除節(jié)點后發(fā)生退化

再例如，在圖 7-25 的完美二叉樹中插入兩個節(jié)點后，樹將嚴(yán)重向左傾斜，查找操作的時間復(fù)雜度也隨之惡化。

圖 7-25   AVL 樹在插入節(jié)點后發(fā)生退化

G. M. Adelson-Velsky 和 E. M. Landis 在其 1962 年發(fā)表的論文 "An algorithm for the organization of information" 中提出了「AVL 樹」。論文中詳細描述了一系列操作，確保在持續(xù)添加和刪除節(jié)點后，AVL 樹不會退化，從而使得各種操作的時間復(fù)雜度保持在 O(log?n) 級別。換句話說，在需要頻繁進行增刪查改操作的場景中，AVL 樹能始終保持高效的數(shù)據(jù)操作性能，具有很好的應(yīng)用價值。

7.5.1   AVL 樹常見術(shù)語

AVL 樹既是二叉搜索樹也是平衡二叉樹，同時滿足這兩類二叉樹的所有性質(zhì)，因此也被稱為「平衡二叉搜索樹 balanced binary search tree」。

1.   節(jié)點高度

由于 AVL 樹的相關(guān)操作需要獲取節(jié)點高度，因此我們需要為節(jié)點類添加 ?height? 變量。

/* AVL 樹節(jié)點類 */
struct TreeNode {
    int val{};          // 節(jié)點值
    int height = 0;     // 節(jié)點高度
    TreeNode *left{};   // 左子節(jié)點
    TreeNode *right{};  // 右子節(jié)點
    TreeNode() = default;
    explicit TreeNode(int x) : val(x){}
};

“節(jié)點高度”是指從該節(jié)點到最遠葉節(jié)點的距離，即所經(jīng)過的“邊”的數(shù)量。需要特別注意的是，葉節(jié)點的高度為 0 ，而空節(jié)點的高度為 -1 。我們將創(chuàng)建兩個工具函數(shù)，分別用于獲取和更新節(jié)點的高度。

avl_tree.cpp

/* 獲取節(jié)點高度 */
int height(TreeNode *node) {
    // 空節(jié)點高度為 -1 ，葉節(jié)點高度為 0
    return node == nullptr ? -1 : node->height;
}

/* 更新節(jié)點高度 */
void updateHeight(TreeNode *node) {
    // 節(jié)點高度等于最高子樹高度 + 1
    node->height = max(height(node->left), height(node->right)) + 1;
}

2.   節(jié)點平衡因子

節(jié)點的「平衡因子 balance factor」定義為節(jié)點左子樹的高度減去右子樹的高度，同時規(guī)定空節(jié)點的平衡因子為 0 。我們同樣將獲取節(jié)點平衡因子的功能封裝成函數(shù)，方便后續(xù)使用。

avl_tree.cpp

/* 獲取平衡因子 */
int balanceFactor(TreeNode *node) {
    // 空節(jié)點平衡因子為 0
    if (node == nullptr)
        return 0;
    // 節(jié)點平衡因子 = 左子樹高度 - 右子樹高度
    return height(node->left) - height(node->right);
}

Note

設(shè)平衡因子為 f ，則一棵 AVL 樹的任意節(jié)點的平衡因子皆滿足 ?1≤f≤1 。

AVL 樹旋轉(zhuǎn)

AVL 樹的特點在于“旋轉(zhuǎn)”操作，它能夠在不影響二叉樹的中序遍歷序列的前提下，使失衡節(jié)點重新恢復(fù)平衡。換句話說，旋轉(zhuǎn)操作既能保持“二叉搜索樹”的性質(zhì)，也能使樹重新變?yōu)椤捌胶舛鏄洹薄?/p>

我們將平衡因子絕對值 >1 的節(jié)點稱為“失衡節(jié)點”。根據(jù)節(jié)點失衡情況的不同，旋轉(zhuǎn)操作分為四種：右旋、左旋、先右旋后左旋、先左旋后右旋。下面我們將詳細介紹這些旋轉(zhuǎn)操作。

1.   右旋

如圖 7-26 所示，節(jié)點下方為平衡因子。從底至頂看，二叉樹中首個失衡節(jié)點是“節(jié)點 3”。我們關(guān)注以該失衡節(jié)點為根節(jié)點的子樹，將該節(jié)點記為 ?node? ，其左子節(jié)點記為 ?child? ，執(zhí)行“右旋”操作。完成右旋后，子樹已經(jīng)恢復(fù)平衡，并且仍然保持二叉搜索樹的特性。

圖 7-26   右旋操作步驟

如圖 7-27 所示，當(dāng)節(jié)點 child 有右子節(jié)點（記為 grandChild ）時，需要在右旋中添加一步：將 grandChild 作為 node 的左子節(jié)點。

圖 7-27   有 grandChild 的右旋操作

“向右旋轉(zhuǎn)”是一種形象化的說法，實際上需要通過修改節(jié)點指針來實現(xiàn)，代碼如下所示。

avl_tree.cpp

/* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {
    TreeNode *child = node->left;
    TreeNode *grandChild = child->right;
    // 以 child 為原點，將 node 向右旋轉(zhuǎn)
    child->right = node;
    node->left = grandChild;
    // 更新節(jié)點高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋轉(zhuǎn)后子樹的根節(jié)點
    return child;
}

2.   左旋

相應(yīng)的，如果考慮上述失衡二叉樹的“鏡像”，則需要執(zhí)行圖 7-28 所示的“左旋”操作。

圖 7-28   左旋操作

同理，如圖 7-29 所示，當(dāng)節(jié)點 child 有左子節(jié)點（記為 grandChild ）時，需要在左旋中添加一步：將 grandChild 作為 node 的右子節(jié)點。

圖 7-29   有 grandChild 的左旋操作

可以觀察到，右旋和左旋操作在邏輯上是鏡像對稱的，它們分別解決的兩種失衡情況也是對稱的。基于對稱性，我們只需將右旋的實現(xiàn)代碼中的所有的 left 替換為 right ，將所有的 right 替換為 left ，即可得到左旋的實現(xiàn)代碼。

avl_tree.cpp

/* 左旋操作 */
TreeNode *leftRotate(TreeNode *node) {
    TreeNode *child = node->right;
    TreeNode *grandChild = child->left;
    // 以 child 為原點，將 node 向左旋轉(zhuǎn)
    child->left = node;
    node->right = grandChild;
    // 更新節(jié)點高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋轉(zhuǎn)后子樹的根節(jié)點
    return child;
}

3.   先左旋后右旋

對于圖 7-30 中的失衡節(jié)點 3 ，僅使用左旋或右旋都無法使子樹恢復(fù)平衡。此時需要先對 child 執(zhí)行“左旋”，再對 node 執(zhí)行“右旋”。

圖 7-30   先左旋后右旋

4.   先右旋后左旋

如圖 7-31 所示，對于上述失衡二叉樹的鏡像情況，需要先對 ?child? 執(zhí)行“右旋”，然后對 ?node? 執(zhí)行“左旋”。

圖 7-31   先右旋后左旋

5.   旋轉(zhuǎn)的選擇

圖 7-32 展示的四種失衡情況與上述案例逐個對應(yīng)，分別需要采用右旋、左旋、先右后左、先左后右的旋轉(zhuǎn)操作。

圖 7-32   AVL 樹的四種旋轉(zhuǎn)情況

如下表所示，我們通過判斷失衡節(jié)點的平衡因子以及較高一側(cè)子節(jié)點的平衡因子的正負號，來確定失衡節(jié)點屬于圖 7-32 中的哪種情況。

表 7-3   四種旋轉(zhuǎn)情況的選擇條件

為了便于使用，我們將旋轉(zhuǎn)操作封裝成一個函數(shù)。有了這個函數(shù)，我們就能對各種失衡情況進行旋轉(zhuǎn)，使失衡節(jié)點重新恢復(fù)平衡。

avl_tree.cpp

/* 執(zhí)行旋轉(zhuǎn)操作，使該子樹重新恢復(fù)平衡 */
TreeNode *rotate(TreeNode *node) {
    // 獲取節(jié)點 node 的平衡因子
    int _balanceFactor = balanceFactor(node);
    // 左偏樹
    if (_balanceFactor > 1) {
        if (balanceFactor(node->left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    // 右偏樹
    if (_balanceFactor < -1) {
        if (balanceFactor(node->right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    // 平衡樹，無須旋轉(zhuǎn)，直接返回
    return node;
}

AVL 樹常用操作

1.   插入節(jié)點

AVL 樹的節(jié)點插入操作與二叉搜索樹在主體上類似。唯一的區(qū)別在于，在 AVL 樹中插入節(jié)點后，從該節(jié)點到根節(jié)點的路徑上可能會出現(xiàn)一系列失衡節(jié)點。因此，我們需要從這個節(jié)點開始，自底向上執(zhí)行旋轉(zhuǎn)操作，使所有失衡節(jié)點恢復(fù)平衡。

avl_tree.cpp

/* 插入節(jié)點 */
void insert(int val) {
    root = insertHelper(root, val);
}

/* 遞歸插入節(jié)點（輔助方法） */
TreeNode *insertHelper(TreeNode *node, int val) {
    if (node == nullptr)
        return new TreeNode(val);
    /* 1. 查找插入位置，并插入節(jié)點 */
    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);
    else
        return node;    // 重復(fù)節(jié)點不插入，直接返回
    updateHeight(node); // 更新節(jié)點高度
    /* 2. 執(zhí)行旋轉(zhuǎn)操作，使該子樹重新恢復(fù)平衡 */
    node = rotate(node);
    // 返回子樹的根節(jié)點
    return node;
}

2.   刪除節(jié)點

類似地，在二叉搜索樹的刪除節(jié)點方法的基礎(chǔ)上，需要從底至頂?shù)貓?zhí)行旋轉(zhuǎn)操作，使所有失衡節(jié)點恢復(fù)平衡。

avl_tree.cpp

/* 刪除節(jié)點 */
void remove(int val) {
    root = removeHelper(root, val);
}

/* 遞歸刪除節(jié)點（輔助方法） */
TreeNode *removeHelper(TreeNode *node, int val) {
    if (node == nullptr)
        return nullptr;
    /* 1. 查找節(jié)點，并刪除之 */
    if (val < node->val)
        node->left = removeHelper(node->left, val);
    else if (val > node->val)
        node->right = removeHelper(node->right, val);
    else {
        if (node->left == nullptr || node->right == nullptr) {
            TreeNode *child = node->left != nullptr ? node->left : node->right;
            // 子節(jié)點數(shù)量 = 0 ，直接刪除 node 并返回
            if (child == nullptr) {
                delete node;
                return nullptr;
            }
            // 子節(jié)點數(shù)量 = 1 ，直接刪除 node
            else {
                delete node;
                node = child;
            }
        } else {
            // 子節(jié)點數(shù)量 = 2 ，則將中序遍歷的下個節(jié)點刪除，并用該節(jié)點替換當(dāng)前節(jié)點
            TreeNode *temp = node->right;
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node); // 更新節(jié)點高度
    /* 2. 執(zhí)行旋轉(zhuǎn)操作，使該子樹重新恢復(fù)平衡 */
    node = rotate(node);
    // 返回子樹的根節(jié)點
    return node;
}

3.   查找節(jié)點

AVL 樹的節(jié)點查找操作與二叉搜索樹一致，在此不再贅述。

AVL 樹典型應(yīng)用

• 組織和存儲大型數(shù)據(jù)，適用于高頻查找、低頻增刪的場景。
• 用于構(gòu)建數(shù)據(jù)庫中的索引系統(tǒng)。
• 紅黑樹在許多應(yīng)用中比 AVL 樹更受歡迎。這是因為紅黑樹的平衡條件相對寬松，在紅黑樹中插入與刪除節(jié)點所需的旋轉(zhuǎn)操作相對較少，其節(jié)點增刪操作的平均效率更高。