【C++筆記】AVL樹的深度剖析

🔥個人主頁：大白的編程日記

🔥專欄：C++筆記

---

前言

哈嘍，各位小伙伴大家好!上期我們講了map和set的深度剖析。今天我們來講一下AVL樹的深度剖析。話不多說，我們進入正題！向大廠沖鋒

一. AVL樹的概念

• 定義
  AVL樹是最先發明的自平衡?叉查找樹，AVL是一顆空樹，或者具備下列性質的?叉搜索樹：它的左右子樹都是AVL樹，且左右子樹的高度差的絕對值不超過1。AVL樹是?顆高度平衡搜索?叉樹，通過控制高度差去控制平衡。
  注意是所有的子樹都滿足高度差絕對值不超過1。
• 發明者
  AVL樹得名于它的發明者G. M. Adelson-Velsky和E. M. Landis是兩個前蘇聯的科學家，他們在1962年的論文《An algorithm for the organization of information》中發表了它。
• 平衡因子
  AVL樹實現這里我們引入?個平衡因子(balance factor)的概念，每個結點都有?個平衡因子，任何結點的平衡因子等于右子樹的高度減去左子樹的高度，也就是說任何結點的平衡因子等于0/1/-1，AVL樹并不是必須要平衡因子，但是有了平衡因子可以更方便我們去進行觀察和控制樹是否平衡，就像?個風向標?樣。

• 高度差
  思考?下為什么AVL樹是高度平衡搜索?叉樹，要求?度差不超過1，而不是高度差是0呢？0不是更好的平衡嗎？畫畫圖分析我們發現，不是不想這樣設計，而是有些情況是做不到高度差是0的。比如?棵樹是2個結點，4個結點等情況下，高度差最好就是1，無法做到高度差是0
• 對比二叉搜索樹
  AVL樹整體結點數量和分布和完全?叉樹類似，高度可以控制在 ，那么增刪查改的效率也可以控制在logn ，相比?叉搜索樹有了本質的提升。
  

二.AVL樹的實現

2.1 AVL樹的結構

這里我們為了旋轉時需要用到父親節點，所以我們就是一個三叉鏈的結構。
同時我們引入了平衡因子，方便我們控制高度差。

template<class k, class v>
struct AVLNode
{using node = AVLNode<k, v>;k _key;v _value;node* left;//左節點node* right;//右節點node* parent;//父親節點int bf;//平衡因子AVLNode(const k& key, const v& value):_key(key), _value(value), left(nullptr), right(nullptr),parent(nullptr),bf(0){}
};
template<class k, class v>
class AVLTree
{using node = AVLNode<k, v>;private:node* _root = nullptr;
};

2.2 AVL樹的插入

二叉搜索樹還是按照二叉搜索樹的規則插入。
但是插入后要更新平衡因子，如果高度差超過1那么就旋轉。

• 插入
  插入一個值按二叉搜索樹規則進行插入。
  插入的節點，左右為空所以平衡因子為0.

• 更新平衡因子
  新增結點以后，只會影響祖先結點的高度，也就是可能會影響部分祖先結點的平衡因子，所以更新從新增結點->根結點路徑上的平衡因子，實際中最壞情況下要更新到根，有些情況更新到中間就可以停止了，具體情況我們下面再詳細分析。

• 結束
  更新平衡因子過程中沒有出現問題，則插入結束。

• 旋轉
  更新平衡因子過程中出現不平衡，對不平衡子樹旋轉，旋轉后本質調平衡的同時，本質降低了子樹的高度，保持原來的高度，不會再影響上一層，所以插入結束。

2.3 平衡因子更新

更新原則：

• 平衡因子 = 右子樹高度-左子樹高度

• 只有子樹高度變化才會影響當前結點平衡因子。

• 插入結點，會增加高度，所以新增結點在parent的右子樹，parent的平衡因子++，新增結點在parent的左子樹，parent平衡因子–。

• parent所在子樹的高度是否變化決定了是否會繼續往上更新
  如果當前子樹高度沒有變化，那當前子樹往上的祖先節點的平衡因子也不會變化
  更新結束。

更新停止條件：

• 更新后parent的平衡因子等于0，更新中parent的平衡因子變化為-1->0 或者 1->0，說明更新前parent子樹?邊高?邊低，新增的結點插入在低的那邊，插入后parent所在的子樹高度不變，不會影響parent的?親結點的平衡因子，更新結束。

• 更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子變化為0->1 或者 0->-1，說明更新前parent子樹兩邊?樣高，新增的插入結點后，parent所在的子樹?邊高?邊低，parent所在的子樹符合平衡要求，但是高度增加了1，會影響parent的?親結點的平衡因子，所以要繼續向上更新。

• 更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子變化為1->2 或者 -1->-2，說明更新前parent子樹?邊高?邊低，新增的插入結點在高的那邊，parent所在的子樹高的那邊更高了，破壞了平衡，parent所在的子樹不符合平衡要求，需要旋轉處理，旋轉的目標有兩個：1、把parent子樹旋轉平衡。2、降低parent子樹的高度，恢復到插入結點以前的高度。所以旋轉后也不需要繼續往上更新，插入結束。

• 不斷更新，更新到根，跟的平衡因子是1或-1也停停止了。

三.旋轉

3.1旋轉的原則

旋轉的原則如下：

1. 保持搜索樹的規則
2. 讓旋轉的樹從不滿足變平衡，其次降低旋轉樹的高度
   旋轉總共分為四種，左單旋/右單旋/左右雙旋/右左雙旋。
   說明：下面的圖中，有些結點我們給的是具體值，如10和5等結點，這里是為了方便講解，實際中是什么值都可以，只要大小關系符合搜索樹的性質即可。

3.2右單旋

旋轉時我們需要注意保持二叉搜索樹的性質。
同時注意父親節點和平衡因子的更新。
注意旋轉后子樹的高度不變，平衡因子向上更新停止。

	void RoRateR( node* parent)//右單旋{node* subL = parent->left;node* subLR = subL->right;node* pparnet = parent->parent;parent->left = subLR;if (subLR){subLR->parent = parent;//修改父節點}subL->right = parent;parent->parent = subL;if (pparnet == nullptr)//parent就是根節點{_root = subL;subL->parent = nullptr;}else{if (pparnet->left == parent)//確定parent節點是左還是右{pparnet->left = subL;}else {pparnet->right = subL;}subL->parent = pparnet;//修改父節點}subL->bf = parent->bf = 0;//更新平衡因子}

3.3左單旋

左單旋和右單旋類似。

void RoRateL( node* parent)//左單旋
{node* subR = parent->right;node* subRL = subR->left;node* pparnet = parent->parent;parent->right = subRL;if (subRL)//防止subRL為空{subRL->parent = parent;//修改父節點}subR->left = parent;parent->parent = subR;if (pparnet==nullptr)//parent就是根節點{_root = subR;subR->parent = nullptr;}else{if (pparnet->left == parent)//確定parent節點是左還是右{pparnet->left = subR;}else {pparnet->right = subR;}subR->parent = pparnet;//修改父節點}subR->bf = parent->bf = 0;//更新平衡因子
}

3.4左右雙旋

左右雙旋的就是先左單旋再右單旋。
同時注意平衡因子的更新即可。

更新條件：parent->bf == -2 && cur->bf == 1

void RoRateLR( node* parent)//左右雙旋
{node* subL = parent->left;node* subLR = subL->right;int bf = subLR->bf;//先記錄插入后的平衡因子RoRateL(subL);RoRateR(parent);if (bf == 0)//分情況討論{parent->bf = 0;subL->bf = 0;subLR->bf = 0;}else if (bf == 1){parent->bf = 0;subL->bf = -1;subLR->bf = 0;}else if (bf == -1){parent->bf = 1;subL->bf = 0;subLR->bf = 0;}else{assert(false);}
}

3.5右左雙旋

右左雙旋情況和左右雙旋類似，這里就不過多贅述了。

更新條件：parent->bf == 2 && cur->bf == -1

3.6AVL樹的插入

結合前面的知識我們就可以寫出二叉搜索樹的插入了。

void RoRateR( node* parent)//右單旋
{node* subL = parent->left;node* subLR = subL->right;node* pparnet = parent->parent;parent->left = subLR;if (subLR){subLR->parent = parent;//修改父節點}subL->right = parent;parent->parent = subL;if (pparnet == nullptr)//parent就是根節點{_root = subL;subL->parent = nullptr;}else{if (pparnet->left == parent)//確定parent節點是左還是右{pparnet->left = subL;}else {pparnet->right = subL;}subL->parent = pparnet;//修改父節點}subL->bf = parent->bf = 0;//更新平衡因子
}
void RoRateL( node* parent)//左單旋
{node* subR = parent->right;node* subRL = subR->left;node* pparnet = parent->parent;parent->right = subRL;if (subRL)//防止subRL為空{subRL->parent = parent;//修改父節點}subR->left = parent;parent->parent = subR;if (pparnet==nullptr)//parent就是根節點{_root = subR;subR->parent = nullptr;}else{if (pparnet->left == parent)//確定parent節點是左還是右{pparnet->left = subR;}else {pparnet->right = subR;}subR->parent = pparnet;//修改父節點}subR->bf = parent->bf = 0;//更新平衡因子
}
void RoRateLR( node* parent)//左右雙旋
{node* subL = parent->left;node* subLR = subL->right;int bf = subLR->bf;//先記錄插入后的平衡因子RoRateL(subL);RoRateR(parent);if (bf == 0)//分情況討論{parent->bf = 0;subL->bf = 0;subLR->bf = 0;}else if (bf == 1){parent->bf = 0;subL->bf = -1;subLR->bf = 0;}else if (bf == -1){parent->bf = 1;subL->bf = 0;subLR->bf = 0;}else{assert(false);}
}
void RoRateRL( node* parent)//右左雙旋
{node* subR = parent->right;node* subRL = subR->left;int bf = subRL->bf;//先記錄插入后的平衡因子RoRateR(subR);RoRateL(parent);if (bf == 0)//分情況討論{parent->bf = 0;subR->bf = 0;subRL->bf = 0;}else if (bf == 1){parent->bf = -1;subR->bf = 0;subRL->bf = 0;}else if (bf == -1){parent->bf = 0;subR->bf = 1;subRL->bf = 0;}else{assert(false);}
}
bool Insert(const k& x, const v& v)
{if (_root == nullptr)//插入根節點{_root = new node(x, v);return true;}node* cur = _root;node* parent = nullptr;//保留父親節點while (cur){/*介質不冗余*/if (x < cur->_key){parent = cur;cur = cur->left;}else if (x > cur->_key){parent = cur;cur = cur->right;}else{return false;}//介質冗余//if (x <= cur->_key)//相等插入到左子樹//{//	parent = cur;//	cur = cur->left;//}//else if (x > cur->_key)//{//	parent = cur;//	cur = cur->right;//}}cur = new node(x, v);if (x > parent->_key){parent->right = cur;}else//相等插入左子樹{parent->left = cur;}cur->parent = parent;while (parent){// 更新平衡因?if (cur == parent->left)parent->bf--;elseparent->bf++;if (parent->bf == 0){// 更新結束break;}else if (parent->bf == 1 || parent->bf == -1){// 繼續往上更新cur = parent;parent = parent->parent;}else if (parent->bf == 2 || parent->bf == -2)//旋轉{if (parent->bf == -2 && cur->bf == -1){RoRateR(parent);}else if (parent->bf == 2 && cur->bf == 1){RoRateL(parent);}else if (parent->bf == -2 && cur->bf == 1){RoRateLR(parent);}else if (parent->bf == 2 && cur->bf == -1){RoRateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}

3.7AVL樹的查找

在避免了二叉搜索樹退化為單叉樹的情況。
AVL樹的查找效率為O(logN).

四.AVL樹的檢測

4.1AVL樹檢測

AVL樹我們可以遞歸檢測每顆子樹的左右高度差是否不差過1即可。

void Inorder()
{_Inorder(_root);cout << endl;
}
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}
bool _IsBalanceTree(const node* root)
{// 空樹也是AVL樹if (nullptr == root)return true;// 計算pRoot結點的平衡因?：即pRoot左右?樹的?度差int leftHeight = _Height(root->left);int rightHeight = _Height(root->right);int diff = rightHeight - leftHeight;// 如果計算出的平衡因?與pRoot的平衡因?不相等，或者// pRoot平衡因子的絕對值超過1，則?定不是AVL樹if (abs(diff) >= 2){cout << root->_value << "高度差異常" << endl;return false;}if (root->bf != diff){cout << root->_key << "平衡因子異常" << endl;return false;}// pRoot的左和右如果都是AVL樹，則該樹?定是AVL樹return _IsBalanceTree(root->left) && _IsBalanceTree(root->right);
}
void _Inorder(const node* root)
{if (root == nullptr){return;}_Inorder(root->left);cout << root->_key << ":" << root->_value<<endl;_Inorder(root->right);
}
size_t Size()
{return _Size(_root);
}
size_t _Size(const node* parent)
{if (parent){return 1 + _Size(parent->left)+ _Size(parent->right);}else{return 0;}
}
size_t Height()
{return _Height(_root);
}
size_t _Height(const node* parent)
{if (parent){return 1 + max(_Height(parent->left), _Height(parent->right));}else{return 0;}
}

4.2 AVL樹的驗證

• 檢測一

void TestAVLTree1()
{AVL::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;
}

• 檢測二

void TestAVLTree2()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVL::AVLTree<int, int> t;for (auto e : v){t.Insert(e, e);}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalanceTree() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 確定在的值/*for (auto e : v){t.Find(e);}*/// 隨機值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}

后言

這就是AVL樹的深度剖析。大家自己好好消化！今天就分享到這！感謝各位的耐心垂閱！咱們下期見！拜拜~