【C++】AVL樹（旋轉、平衡因子）

🌈個人主頁：秦jh_-CSDN博客
🔥?系列專欄：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

???

前言

AVL樹的概念

?節點

插入

AVL樹的旋轉?

新節點插入較高左子樹的左側---左左：右單旋?

新節點插入較高右子樹的右側---右右：左單旋

新節點插入較高左子樹的右側---左右：先左單旋再右單旋

?新節點插入較高右子樹的左側---右左：先右單旋再左單旋

AVL樹的驗證?

?AVL樹的性能

完整代碼

前言

????💬 hello! 各位鐵子們大家好哇。

? ? ? ? ? ? ?今日更新了AVL樹的相關內容
????🎉 歡迎大家關注🔍點贊👍收藏??留言📝

AVL樹的概念

?二叉搜索樹雖可以縮短查找的效率，但如果數據有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下。

解決方案：當向二叉搜索樹中插入新結點后，如果能保證每個結點的左右子樹高度之差的絕對值不超過1(需要對樹中的結點進行調整)，即可降低樹的高度，從而減少平均搜索長度。

它的左右子樹都是AVL樹
左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)

如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。

插入的總體原則：

?按照搜索樹規則插入
更新插入節點的祖先節點的平衡因子。
如果插入在父親左邊，父親的平衡因子--。
如果插入在父親右邊，父親的平衡因子++。
父親平衡因子==0，則父親所在子樹高度不變，不再繼續往上更新，插入結束。
父親平衡因子==1or-1，父親所在子樹高度變了，繼續往上更新。
父親平衡因子==2or-2，父親所在子樹已經不平衡了，需要旋轉處理。

?節點

插入

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;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->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//更新平衡因子while (parent) {if (cur == parent->_left){parent->_bf--;}else{parent->_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){//當前子樹出問題了，需要旋轉平衡一下break;}else{//理論而言不可能出現該情況assert(false);}}return true;}

上面是插入的大體流程，旋轉操作還未給出。

AVL樹的旋轉?

如果在一棵原本是平衡的AVL樹中插入一個新節點，可能造成不平衡，此時必須調整樹的結構，使之平衡化。根據節點插入位置的不同，AVL樹的旋轉分為四種：

新節點插入較高左子樹的左側---左左：右單旋?

這里以抽象圖進行分析，因為具體的情況有很多種，無法畫出。

注意：a子樹的情況必須是插入后會引發祖先節點的更新，而不是只是內部變化。如下圖情況就不符合要求。

旋轉流程：新節點插入在a樹中，導致以60為根的二叉樹不平衡。所以就要右單旋。

右單旋：把60的左子樹高度減少，即把60取出來，讓30的右子樹變成60的左子樹，再把以60為根的樹變成30的右子樹。30成為新的根。

	void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) //節點可能為空subLR->_parent = parent;subL->_right = parent; //舊父節點變成subL的右節點Node* ppNode = parent->_parent;  //該不平衡節點可能不是根節點，所以要找到它的父節點parent->_parent = subL;				if (parent == _root)   //如果該節點是根節點{_root = subL;		_root->_parent = nullptr;}else  //不平衡節點只是一棵子樹{if (ppNode->_left == parent)  //如果舊父節點等于爺爺節點的左節點，新父節點為爺爺節點的左節點{ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;	//新父節點指向爺爺節點。}parent->_bf = subL->_bf = 0;  //只需要修改這兩個的平衡因子}

新節點插入較高右子樹的右側---右右：左單旋

參考右單旋。

左單旋和右單旋的調用如下圖：

新節點插入較高左子樹的右側---左右：先左單旋再右單旋

單旋用在一邊一直高的情況。雙旋是先一邊高再另一邊高的情況。

雙旋的的原理就是把折線變成直線，再像處理直線一樣旋轉。

雙旋可以復用單旋，但雙旋主要要搞清平衡因子的變化。

第一種情況：?

雙旋的結果：60的左邊給了30的右邊，60的右邊給了90的左邊，30和90分別成為60的左右，60成為根。

上圖是插入b引起的旋轉，當插入c時是第二種情況，如下圖：

上面兩種插入位置的不同，導致最終的平衡因子不同。

第三種情況：

h==0時，60就是新增節點，最終的平衡因子也不同。

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right; int bf = subLR->_bf;  //記錄未旋轉前subLR的平衡因子RotateL(parent->_left);  RotateR(parent);if (bf == -1)  //如果bf為-1，即插入在subLR的左邊{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1) //插入在subLR的右邊{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

?新節點插入較高右子樹的左側---右左：先右單旋再左單旋

參考左右雙旋，注意，這里也要討論那三種情況。?

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

AVL樹的驗證?

AVL樹是在二叉搜索樹的基礎上加入了平衡性的限制，因此要驗證AVL樹，可以分兩步：

驗證其為二叉搜索樹。如果中序遍歷可得到一個有序的序列，就說明為二叉搜索樹
驗證其為平衡樹。每個節點子樹高度差的絕對值不超過1(注意節點中如果沒有平衡因子) 節點的平衡因子是否計算正確?

?因為root是私有的，又因為需要遞歸檢查每棵子樹是否平衡，所以可以寫一個私有的_IsBalance方法，通過公有的IsBalance方法來調用。

?AVL樹的性能

AVL樹是一棵絕對平衡的二叉搜索樹，其要求每個節點的左右子樹高度差的絕對值都不超過1，這樣可以保證查詢時高效的時間復雜度，即O(logN)。?但是如果要對AVL樹做一些結構修改的操作，性能非常低下，比如：插入時要維護其絕對平衡，旋轉的次數比較多，更差的是在刪除時，有可能一直要讓旋轉持續到根的位置。因此：如果需要一種查詢高效且有序的數據結構，而且數據的個數為靜態的(即不會改變)，可以考慮AVL樹，但一個結構經常修改，就不太適合。紅黑樹在經常進行增刪的結構中性能比AVL樹更優。

完整代碼

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;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->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//更新平衡因子while (parent) {if (cur == parent->_left){parent->_bf--;}else{parent->_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) //左邊高，右單旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1)//右邊高，左單旋{RotateL(parent);}else if (parent->_bf == 2 && cur->_bf == -1){ RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent); }break;}else{//理論而言不可能出現該情況assert(false);}}return true;}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;}void InOrder(){_InOrder(_root);cout << endl;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) //節點可能為空subLR->_parent = parent;subL->_right = parent; //舊父節點變成subL的右節點Node* ppNode = parent->_parent;  //該不平衡節點可能不是根節點，所以要找到它的父節點parent->_parent = subL;				if (parent == _root)   //如果該節點是根節點{_root = subL;		_root->_parent = nullptr;}else  //不平衡節點只是一棵子樹{if (ppNode->_left == parent)  //如果舊父節點等于爺爺節點的左節點，新父節點為爺爺節點的左節點{ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;	//新父節點指向爺爺節點。}parent->_bf = subL->_bf = 0;  //只需要修改這兩個的平衡因子}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right; int bf = subLR->_bf;  //記錄未旋轉前subLR的平衡因子RotateL(parent->_left);  RotateR(parent);if (bf == -1)  //如果bf為-1，即插入在subLR的左邊{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1) //插入在subLR的右邊{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}bool IsBalance(){return _IsBalance(_root);}int Height() //樹的高度{return _Height(_root);}int Size()  //插入的節點個數{return _Size(_root);}private:int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root) {if (root == nullptr) return true;int	leftHeight = _Height(root->_left);int	rightHeight = _Height(root->_right);//如果不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//檢查平衡因子是否正確if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root=nullptr; 
};void AVLTreeTest1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int,int> t1;for (auto e : a){t1.Insert({e,e});cout <<"Insert:"<<e<<"->"<< t1.IsBalance() << endl;}t1.InOrder();	cout << t1.IsBalance() << endl;
}