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

如圖 7-24 所示，經(jīng)過(guò)兩次刪除節(jié)點(diǎn)操作，這個(gè)二叉搜索樹(shù)便會(huì)退化為鏈表。

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

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

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

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

7.5.1   AVL 樹(shù)常見(jiàn)術(shù)語(yǔ)

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

1.   節(jié)點(diǎn)高度

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

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

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

avl_tree.cpp

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

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

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

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

avl_tree.cpp

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

Note

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

AVL 樹(shù)旋轉(zhuǎn)

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

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

1.   右旋

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

圖 7-26   右旋操作步驟

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

圖 7-27   有 grandChild 的右旋操作

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

avl_tree.cpp

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

2.   左旋

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

圖 7-28   左旋操作

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

圖 7-29   有 grandChild 的左旋操作

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

avl_tree.cpp

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

3.   先左旋后右旋

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

圖 7-30   先左旋后右旋

4.   先右旋后左旋

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

圖 7-31   先右旋后左旋

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

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

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

如下表所示，我們通過(guò)判斷失衡節(jié)點(diǎn)的平衡因子以及較高一側(cè)子節(jié)點(diǎn)的平衡因子的正負(fù)號(hào)，來(lái)確定失衡節(jié)點(diǎn)屬于圖 7-32 中的哪種情況。

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

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

avl_tree.cpp

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

AVL 樹(shù)常用操作

1.   插入節(jié)點(diǎn)

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

avl_tree.cpp

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

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

2.   刪除節(jié)點(diǎn)

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

avl_tree.cpp

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

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

3.   查找節(jié)點(diǎn)

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

AVL 樹(shù)典型應(yīng)用

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