【C++游記】AVL樹

楓の個人主頁

你不能改變過去，但你可以改變未來

算法/C++/數據結構/C

Hello，這里是小楓。C語言與數據結構和算法初階兩個板塊都更新完畢，我們繼續來學習C++的內容呀。C++是接近底層有比較經典的語言，因此學習起來注定枯燥無味，西游記大家都看過吧~，我希望能帶著大家一起跨過九九八十一難，降伏各類難題，學會C++，我會盡我所能，以通俗易懂、幽默風趣的方式帶給大家形象生動的知識，也希望大家遇到困難不退縮，遇到難題不放棄，學習師徒四人的精神！！！故此得名【C++游記】

?話不多說，讓我們一起進入今天的學習吧~~~??

一、AVL 樹的概念

為什么 AVL 樹高度差不要求為 0？

二、AVL 樹的實現

2.1 AVL 樹的結構

2.2 AVL 樹的插入

2.2.1 插入過程概述

2.2.2 平衡因子更新規則

2.2.3 插入及平衡因子更新代碼實現

2.3 旋轉操作

2.3.1 旋轉原則

2.3.2 右單旋

2.3.3 左單旋

2.3.4 左右雙旋

2.3.5 右左雙旋

2.4 AVL 樹的查找

2.5 AVL 樹平衡檢測

?三、結語

一、AVL 樹的概念

AVL 樹是最先發明的自平衡二叉查找樹，它要么是一顆空樹，要么具備下列性質的二叉搜索樹：左右子樹都是 AVL 樹，且左右子樹的高度差的絕對值不超過 1。AVL 樹是一種高度平衡的搜索二叉樹，通過控制高度差來維持平衡。

AVL 樹得名于它的發明者 G. M. Adelson-Velsky 和 E. M. Landis（兩位前蘇聯科學家），他們在 1962 年的論文《An algorithm for the organization of information》中發表了這一數據結構。

在 AVL 樹實現中，我們引入平衡因子 (balance factor) 的概念。每個結點都有一個平衡因子，其值等于右子樹的高度減去左子樹的高度，因此任何結點的平衡因子只能是 0、1 或 - 1。平衡因子就像一個風向標，能方便我們觀察和控制樹是否平衡。

為什么 AVL 樹高度差不要求為 0？

可能有人會疑惑，為什么 AVL 樹要求高度差不超過 1 而不是 0 呢？0 不是更平衡嗎？

其實并非不想這樣設計，而是在某些情況下無法做到高度差為 0。例如，當樹有 2 個結點、4 個結點等情況時，高度差最好就是 1，無法做到高度差為 0。

AVL 樹的整體結點數量和分布與完全二叉樹類似，高度可以控制在logN，因此增刪查改的效率也可以控制在O(logN)，相比普通二叉搜索樹有了本質的提升。

二、AVL 樹的實現

2.1 AVL 樹的結構

AVL 樹的結點結構需要包含鍵值對、左右孩子指針、父節點指針以及平衡因子。具體定義如下：

template<class K, class V>
struct AVLTreeNode
{// 需要parent指針，后續更新平衡因子會用到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:// 各種成員函數實現...
private:Node* _root = nullptr;
};

2.2 AVL 樹的插入

2.2.1 插入過程概述

AVL 樹插入一個值的過程大致如下：

按二叉搜索樹規則插入新結點
從新增結點到根結點的路徑上更新祖先結點的平衡因子（最壞情況要更新到根，有些情況更新到中間即可停止）
若更新平衡因子過程中沒有出現問題，則插入結束
若更新過程中出現不平衡，對不平衡子樹進行旋轉處理。旋轉后會降低子樹高度，不會再影響上一層，插入結束

2.2.2 平衡因子更新規則

更新原則：

平衡因子 = 右子樹高度 - 左子樹高度
只有子樹高度變化才會影響當前結點平衡因子
若新增結點在 parent 的右子樹，parent 的平衡因子 ++；若在左子樹，parent 的平衡因子 --
parent 所在子樹的高度是否變化決定了是否繼續往上更新

更新停止條件：

若更新后 parent 的平衡因子等于 0（變化為 - 1->0 或 1->0）：說明更新前 parent 子樹一邊高一邊低，新增結點插入在低的那邊，插入后 parent 所在子樹高度不變，不會影響 parent 的父親結點的平衡因子，更新結束
若更新后 parent 的平衡因子等于 1 或 - 1（變化為 0->1 或 0->-1）：說明更新前 parent 子樹兩邊一樣高，插入后一邊高一邊低，子樹符合平衡要求但高度增加了 1，會影響 parent 的父親結點的平衡因子，需要繼續向上更新
若更新后 parent 的平衡因子等于 2 或 - 2（變化為 1->2 或 - 1->-2）：說明更新前 parent 子樹一邊高一邊低，新增結點插入在高的那邊，破壞了平衡，需要旋轉處理。旋轉后子樹高度恢復，不需要繼續往上更新
更新到根結點，若根的平衡因子是 1 或 - 1 也停止

2.2.3 插入及平衡因子更新代碼實現

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false; // 鍵已存在，插入失敗}}// 插入新結點cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent){// 更新當前parent的平衡因子if (cur == parent->_left)parent->_bf--;elseparent->_bf++;// 根據平衡因子判斷后續操作if (parent->_bf == 0){// 平衡因子為0，子樹高度不變，更新結束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 平衡因子為1或-1，子樹高度增加，繼續向上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 平衡因子為2或-2，子樹不平衡，需要旋轉處理break;}else{// 平衡因子異常，程序出錯assert(false);}}// 若需要旋轉處理if (parent){if (parent->_bf == 2){if (parent->_right->_bf == 1){// 右右情況，左單旋RotateL(parent);}else if (parent->_right->_bf == -1){// 右左情況，右左雙旋RotateRL(parent);}else{assert(false);}}else if (parent->_bf == -2){if (parent->_left->_bf == -1){// 左左情況，右單旋RotateR(parent);}else if (parent->_left->_bf == 1){// 左右情況，左右雙旋RotateLR(parent);}else{assert(false);}}}return true;
}

2.3 旋轉操作

2.3.1 旋轉原則

旋轉操作需要遵循兩個原則：

保持搜索樹的規則（即旋轉后仍滿足二叉搜索樹的性質）
讓旋轉的樹從不平衡變為平衡，同時降低旋轉樹的高度

旋轉總共分為四種：左單旋、右單旋、左右雙旋、右左雙旋。

2.3.2 右單旋

右單旋適用于 "左左" 情況，即 parent 的平衡因子為 - 2，且其左孩子的平衡因子為 - 1。

旋轉核心步驟：

將 parent 的左孩子（subL）的右子樹（subLR）變為 parent 的左子樹
將 parent 變為 subL 的右子樹
更新相關結點的父指針
若 parent 是根結點，則更新根指針為 subL；否則將 subL 與 parent 的父結點連接
重置 parent 和 subL 的平衡因子為 0

右單旋代碼實現：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 將subL的右子樹變為parent的左子樹parent->_left = subLR;if (subLR)subLR->_parent = parent;// 保存parent的父節點Node* parentParent = parent->_parent;// 將parent變為subL的右子樹subL->_right = parent;parent->_parent = subL;// 處理與parent的父節點的連接if (parentParent == nullptr){// parent是根節點_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}// 重置平衡因子parent->_bf = subL->_bf = 0;
}

2.3.3 左單旋

左單旋適用于 "右右" 情況，即 parent 的平衡因子為 2，且其右孩子的平衡因子為 1。

旋轉核心步驟：

將 parent 的右孩子（subR）的左子樹（subRL）變為 parent 的右子樹
將 parent 變為 subR 的左子樹
更新相關結點的父指針
若 parent 是根結點，則更新根指針為 subR；否則將 subR 與 parent 的父結點連接
重置 parent 和 subR 的平衡因子為 0

左單旋代碼實現：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;// 將subR的左子樹變為parent的右子樹parent->_right = subRL;if (subRL)subRL->_parent = parent;// 保存parent的父節點Node* parentParent = parent->_parent;// 將parent變為subR的左子樹subR->_left = parent;parent->_parent = subR;// 處理與parent的父節點的連接if (parentParent == nullptr){// parent是根節點_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}// 重置平衡因子parent->_bf = subR->_bf = 0;
}

2.3.4 左右雙旋

左右雙旋適用于 "左右" 情況，即 parent 的平衡因子為 - 2，且其左孩子的平衡因子為 1。

旋轉核心步驟：

先以 parent 的左孩子（subL）為旋轉點進行左單旋
再以 parent 為旋轉點進行右單旋
根據 subL 的右孩子（subLR）的平衡因子，調整相關結點的平衡因子

左右雙旋代碼實現：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf; // 保存subLR的平衡因子，用于后續調整// 先對subL進行左單旋RotateL(parent->_left);// 再對parent進行右單旋RotateR(parent);// 根據subLR的平衡因子調整各節點的平衡因子if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{assert(false); // 平衡因子異常}
}

2.3.5 右左雙旋

右左雙旋適用于 "右左" 情況，即 parent 的平衡因子為 2，且其右孩子的平衡因子為 - 1。

旋轉核心步驟：

先以 parent 的右孩子（subR）為旋轉點進行右單旋
再以 parent 為旋轉點進行左單旋
根據 subR 的左孩子（subRL）的平衡因子，調整相關結點的平衡因子

右左雙旋代碼實現：

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf; // 保存subRL的平衡因子，用于后續調整// 先對subR進行右單旋RotateR(parent->_right);// 再對parent進行左單旋RotateL(parent);// 根據subRL的平衡因子調整各節點的平衡因子if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false); // 平衡因子異常}
}

2.4 AVL 樹的查找

AVL 樹的查找操作與普通二叉搜索樹的查找邏輯相同，由于 AVL 樹的高度平衡特性，查找效率為O(logN)。

查找代碼實現：

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{// 找到對應鍵，返回節點return cur;}}// 未找到return nullptr;
}

2.5 AVL 樹平衡檢測

為了驗證實現的 AVL 樹是否合格，我們可以通過檢查左右子樹高度差以及結點的平衡因子來進行驗證。

平衡檢測相關代碼：

// 計算樹的高度
int _Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}// 檢測是否為平衡樹
bool _IsBalanceTree(Node* root)
{// 空樹也是AVL樹if (nullptr == root)return true;// 計算當前節點的平衡因子（右子樹高度 - 左子樹高度）int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 檢查平衡因子是否符合要求if (abs(diff) >= 2){cout << root->_kv.first << "高度差異常" << endl;return false;}// 檢查記錄的平衡因子是否與計算值一致if (root->_bf != diff){cout << root->_kv.first << "平衡因子異常" << endl;return false;}// 遞歸檢查左右子樹return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

測試代碼：

void TestAVLTree1()
{
AVLTree<int, int> t;
// 常規的測試?例
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的帶有雙旋場景的測試?例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
}