浅析AVL树
1.為什么提出AVL樹
學習完搜索二叉樹以后，我們應該想到一個問題，如果我們的搜索二叉樹的趨向于單鏈的形式，類似于：
2.二叉平衡樹概念和結構
?
為了解決上述問題，所以提出了一個概念，叫做二叉平衡樹。
二叉平衡樹，相對于二叉搜索樹，引入了一個叫做平衡因子的概念。
平衡因子：平衡因子就是右子樹的深度-左子樹的深度。
二叉平衡樹的規則是：每一個節點的平衡因子的絕對值都要小于2。
所以我們需要給一個平衡因子。
二叉平衡樹的結構：
template<typename K,typename V> struct AVLBinaryTreeNode {typedef AVLBinaryTreeNode<K, V> Node;AVLBinaryTreeNode(const K& key,const V& value):_left(NULL),_right(NULL), _parent(NULL),_key(key), _bf(0), _value(value){}Node* _left;Node* _right;Node* _parent;int _bf; //來保存右子樹高度-左子樹高度,平衡因子。K _key;V _value; };
3.二叉平衡樹的平衡化旋轉
對于二叉平衡樹來說，最重要的就是它的旋轉算法，因為他要保證所有節點的平衡因子保持在0，1，-1，所以當平衡因子為2或者-2的時候，我們需要調整，這個時候就引入了旋轉這個概念。
例如：
比如上面的這個例子，我們可以看出來在這我們的3已經不滿足二叉平衡樹的條件了，所以在這里我們應該進行旋轉。
另外在這里需要知道，對于葉子節點，它的平衡因子都是0。
單旋轉
首先我們來看單旋轉，單旋轉分為兩種情況：左單旋和右單旋
示例代碼：
//左旋void _RotateL(Node *parent){assert(parent);Node* SubR = parent->_right;Node* SubRL = SubR->_left;parent->_right = SubRL;if (SubRL)SubRL->_parent = parent;Node * ppNode = parent->_parent; //記錄根的父親 SubR->_left = parent; parent->_parent = SubR;if (ppNode==NULL) //考慮根節點的情況{_root = SubR;SubR->_parent = NULL;}else{if (ppNode->_left == parent) //判斷旋轉以后的根應該鏈接在根的父親的那邊{ppNode->_left = SubR;}else{ppNode->_right = SubR;}SubR->_parent = ppNode;}parent->_bf = SubR->_bf = 0; //重置平衡因子} //右旋void _RotateR(Node *parent){Node *SubL = parent->_left;Node *SubLR = SubL->_right;parent->_left = SubLR;if (SubLR) {SubLR->_parent = parent;}Node* ppNode = parent->_parent; //記錄根節點父親SubL->_right = parent;parent->_parent = SubL;if (ppNode == NULL) //考慮根節點情況{_root = SubL;SubL->_parent = NULL;}else{if (ppNode->_left == parent) //判斷旋轉以后的根應該鏈接在根的父親的那邊{ppNode->_left = SubL;}else{ppNode->_right = SubL;}SubL->_parent = ppNode;}parent->_bf = SubL->_bf = 0; //重置平衡因子}雙旋轉
平衡二叉樹有時的旋轉是雙旋轉，雙旋轉有一個特點，就是他的parent節點和下一個節點平衡因子需要異號。
在這，根據sublr的平衡因子不同，分為了3種情況進行插入。接下來，我們對每一種情況進行分析，講解。
第一種情況：
是sublr的平衡因子為0，這個時候就可以把sublr當作一個要插入的葉子節點來理解，這樣subl的平衡因子為1，parentde平衡因子為-2，這樣，就構成了雙旋轉。
第二種情況:
sublr的平衡因子為-1，這個時候就是在sublr的左子樹進行插入節點操作，這樣，subl的平衡因子變為1，parent的平衡因子變為-2。
?
第三種情況：
第三種情況所說的就是sublr的平衡因子為1，這個時候插入點是sublr的右樹。這樣，subl的平衡因子變為1，parent的平衡因子變為-2。
上述的就是進行右左雙旋時的三種情況，我們可以畫一個表格總結下：
示例代碼：
//左右雙旋void _RotateLR(Node *parent){//進行雙旋轉的時候通過在這里的旋轉以后的根節點的bf進行判斷Node* SubL = parent->_left;Node* SubLR = SubL->_right;//計算旋轉以后的根節點的bfint bf = SubLR->_bf;_RotateL(SubL);_RotateR(parent);//如果bf為0，代表插入點就是這個節點，這個時候所有旋轉后的bf皆為0if (bf == 0){SubL->_bf = parent->_bf = 0;}//當bf為1時，這個時候相當于是在給bf的右樹插入，所以插入以后subL旋轉后的右邊高度為h，else if (bf == 1){SubL->_bf = -1;parent->_bf = 0;}//當bf為-1，這時相當于是給bf的左樹進行插入else{SubL->_bf = 0;parent->_bf = 1;}SubLR->_bf = 0;}右左雙旋轉
接下來我們進行另外一種雙旋轉的分析，右左雙旋，有了上面分析的基礎，我相信，下面的分析，你一看就能理解，通過單旋轉，我們就可以看到，旋轉是鏡像的
?
- subrl的bf==0
- subrl的bf==1
- subrl的bf==-1
由于右左旋轉和上述的左右旋轉分析的思路是一樣的，所以我也不就在太詳細的介紹了。
?
void _RotateRL(Node *parent){//雙旋轉根據插入不同進行調整pf，Node* SubR = parent->_right;Node* SubRL = SubR->_left;//根據最后的根節點的bf進行調整int bf = SubRL->_bf;_RotateR(SubR);_RotateL(parent);//當bf為0，代表插入的就是他這個節點，所有的bf都變作0if (bf == 0){parent->_bf = SubR->_bf = 0;}//當bf為-1，代表這時是在這個根的左樹插入，h-1高度變作h。else if (bf == -1){parent->_bf = 0;SubR->_bf = 1;}//當bf為1時，代表是在這個旋轉后的根的右樹插入，h-1的高度作h。else{parent->_bf = -1;SubR->_bf = 0;}SubRL->_bf = 0;}4.二叉平衡樹的插入和刪除
平衡二叉樹的插入算法，和搜索二叉樹的插入算法類似，依然是查找到為空的地方，然后進行創建新節點，進行插入，不過這里多了一個parent指針，所以要記得維護，又因為平衡二叉樹的特性，所以不能忘了要從插入節點向上檢查，確保向上始終為平衡二叉樹，否則，需要進行平衡化旋轉。
//插入算法 bool Insert(const K& key,const V& value){if (_root == NULL){_root = new Node(key, value);return true;}Node* parent = NULL;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key>key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);if (parent->_key > key){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){return true;}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){if (cur->_bf == 1){_RotateL(parent);return true;}else{_RotateRL(parent);//parent->_bf = _Height(parent->_right) - _Height(parent->_left);//_RotateRL(parent);return true;}}if (parent->_bf == -2){if (cur->_bf == 1){_RotateLR(parent);//旋轉完以后必須進行重新對parent配置_bf//parent->_bf = _Height(parent->_right) - _Height(parent->_left);return true;}else{_RotateR(parent);return true;}}}}return true;}至于刪除算法，因為刪除的很復雜，在書上看到的是如果在你刪除的節點數少與一半的時候，這個時候推薦使用懶惰刪除，
規則就是：簡單的標記要刪除的節點是為已刪除。然后在查找等例程里面都人為的忽視標記過的節點。如果標記刪除的節點大于總數一半，就進行一次遍歷，刪除所有標記節點。
5.二叉平衡樹的查找
AVL樹的
bool Find(const K& key){if (_root == NULL)return false;Node *cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key>cur->_key){cur = cur->_right;}else{return true;}}return false;}查找和搜索二叉樹的類似，在這里我就不多說了，直接曬代碼。因為在你插入中已經有這方面的邏輯了。
6.總結
AVL樹是為了解決二叉搜素樹中類似鏈式的樹的時間復雜度太高的問題，如果采用了AVL樹，大致時間復雜度都可以變為O（logN），這樣就更加高效了。AVL樹種最關鍵的就是它的旋轉，分為單旋轉和多旋轉。AVL樹是后續學習紅黑樹的基礎。
#pragma once#include<iostream> #include<cstdlib> #include<cassert>using namespace std;template<typename K,typename V> struct AVLBinaryTreeNode {typedef AVLBinaryTreeNode<K, V> Node;AVLBinaryTreeNode(const K& key,const V& value):_left(NULL),_right(NULL), _parent(NULL),_key(key), _bf(0), _value(value){}Node* _left;Node* _right;Node* _parent;int _bf; //來保存左右子樹的高度差,平衡因子。K _key;V _value; };template<typename K, typename V> class AVLBinaryTree { public:typedef AVLBinaryTreeNode<K, V> Node; public://構造函數AVLBinaryTree():_root(NULL){}//析構函數~AVLBinaryTree(){_DestoryTree(_root);}//拷貝構造AVLBinaryTree(const AVLBinaryTree<K, V> & a){_root = _Copy(_root);}//現代寫法賦值AVLBinaryTree<K,V>operator =(const AVLBinaryTree<K,V>& d){if (this != &d){AVLBinaryTree<K，V> tmp(d);std::swap(tmp._root,_root);}return *this;}//插入節點bool Insert(const K& key,const V& value){if (_root == NULL){_root = new Node(key, value);return true;}Node* parent = NULL;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key>key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);if (parent->_key > key){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){return true;}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){if (cur->_bf == 1){_RotateL(parent);return true;}else{_RotateRL(parent);//parent->_bf = _Height(parent->_right) - _Height(parent->_left);//_RotateRL(parent);return true;}}if (parent->_bf == -2){if (cur->_bf == 1){_RotateLR(parent);//旋轉完以后必須進行重新對parent配置_bf//parent->_bf = _Height(parent->_right) - _Height(parent->_left);return true;}else{_RotateR(parent);return true;}}}}return true;}//查找節點bool Find(const K& key){if (_root == NULL)return false;Node *cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key>cur->_key){cur = cur->_right;}else{return true;}}return false;}//判斷是否為AVL樹//bool IsAVLBinaryTree()//{// return _IsAVLBinaryTree(_root);//}bool IsAVLBinaryTree(){int depth = 0;return _IsAVLBinaryTree(_root, depth);}//中序遍歷void Inorderprint(){_Inorderprint(_root); cout << endl;}//得到高度size_t Height() const{_Height(_root);} protected://拷貝構造二叉樹Node* _Copy(Node *root){Node * NewNode = NULL;if (root != NULL){NewNode = new Node(root->_value);NewNode->_left = _Copy(root->_left);NewNode->_right = _Copy(root->_right);}return NewNode;}//樹的高度size_t _Height(Node *root){if (root == NULL)return 0;size_t lheight = _Height(root->_left) + 1;size_t rheight = _Height(root->_right) + 1;return lheight > rheight ? lheight : rheight;}//判斷二叉樹是否為平衡二叉樹/*bool _IsAVLBinaryTree(Node *root){if (root==NULL){return true;}int heightorder = abs((int)(_Height(root->_right) - _Height(root->_left)));return ((heightorder<2)&&(_IsAVLBinaryTree(root->_left))&& (_IsAVLBinaryTree(root->_right)));}*///判斷二叉樹是否為平衡二叉樹，優化版本bool _IsAVLBinaryTree(Node *root, int & depth){//如果為空，往父節點返if (root == NULL){depth = 0;return true;}//記錄左節點和右節點深度int left = 0;int right = 0;//采取傳引用的方式，下層遞歸進行對深度修改以后會影響上一層if (_IsAVLBinaryTree(root->_left, left) && _IsAVLBinaryTree(root->_right, right)){//計算平衡因子int pf = right - left;//判斷平衡因子是否合法if (pfIsInvaild(pf)){//合法就讓自身加上子樹的深度，然后因為是傳引用，所以當遞歸回到上一層的時候，上層中的right和left就是左右子樹的深度depth = 1 + (right > left ? right : left);return true;}}return false;}//判斷平衡因子是否合法bool pfIsInvaild(const int& pf){return abs(pf) < 2;}//中序遞歸遍歷void _Inorderprint(Node *root){if (root == NULL){return;}_Inorderprint(root->_left);cout << root->_key<<" ";cout << root->_bf << endl;_Inorderprint(root->_right);}//銷毀AVL樹Node* _DestoryTree(Node*& root){if (root != NULL){root->_left = _DestoryTree(root->_left);root->_right = _DestoryTree(root->_right);delete root;root = NULL;}return root;}//左旋void _RotateL(Node *parent){assert(parent);Node* SubR = parent->_right;Node* SubRL = SubR->_left;parent->_right = SubRL;if (SubRL)SubRL->_parent = parent;Node * ppNode = parent->_parent; //記錄根的父親 SubR->_left = parent; parent->_parent = SubR;if (ppNode==NULL) //考慮根節點的情況{_root = SubR;SubR->_parent = NULL;}else{if (ppNode->_left == parent) //判斷旋轉以后的根應該鏈接在根的父親的那邊{ppNode->_left = SubR;}else{ppNode->_right = SubR;}SubR->_parent = ppNode;}parent->_bf = SubR->_bf = 0; //重置平衡因子}//先左旋后右旋//void _RotateLR(Node *parent)//{// Node* SubL = parent->_left;// Node* SubLR = SubL->_right;// SubL->_right = SubLR->_left;// if (SubLR->_left)// SubL->_right->_parent = SubL;// SubLR->_left = SubL;// SubL->_parent = SubLR;// parent->_left = SubLR;// SubLR->_parent = parent;// //判斷SubLR的左子樹是否存在，如果存在，在調整過程當中，需要進行bf的調整// //SubLR的left最后是變成了SubL的left，所以當pf為1時，這個時候調整過去，SubL的pf就是左樹比右樹大。// if (SubLR->_bf <= 0)// SubL->_bf = 0;// else// SubL->_bf = -1;// parent->_left = SubLR->_right;// if (SubLR->_right)// {// parent->_left->_parent = parent;// }// Node *ppnode = parent->_parent;// SubLR->_right = parent;// parent->_parent = SubLR;// if (ppnode == NULL)// {// _root = SubLR;// SubLR->_parent = NULL;// }// else// {// if (parent == ppnode->_left)// {// ppnode->_left = SubLR;// }// else// {// ppnode->_right = SubLR;// }// SubLR->_parent = ppnode;// }// //同上，這是看SubLR的right是否存在。// if (SubLR->_bf == -1)// parent->_bf = 1;// else// parent->_bf = 0;// SubLR->_bf = 0;//}void _RotateLR(Node *parent){//進行雙旋轉的時候通過在這里的旋轉以后的根節點的bf進行判斷Node* SubL = parent->_left;Node* SubLR = SubL->_right;//計算旋轉以后的根節點的bfint bf = SubLR->_bf;_RotateL(SubL);_RotateR(parent);//如果bf為0，代表插入點就是這個節點，這個時候所有旋轉后的bf皆為0if (bf == 0){SubL->_bf = parent->_bf = 0;}//當bf為1時，這個時候相當于是在給bf的右樹插入，所以插入以后subL旋轉后的右邊高度為h，else if (bf == 1){SubL->_bf = -1;parent->_bf = 0;}//當bf為-1，這時相當于是給bf的左樹進行插入else{SubL->_bf = 0;parent->_bf = 1;}SubLR->_bf = 0;}//先右旋后左旋//void _RotateRL(Node *parent)//{// Node *SubR = parent->_right;// Node *SubRL = SubR->_left;// //右旋// SubR->_left = SubRL->_right;// if (SubRL->_right)// SubR->_right->_parent = SubR;// parent->_right = SubRL;// SubRL->_parent = parent;// SubRL->_right = SubR;// SubR->_parent = SubRL;// if (SubRL->_bf >= 0)// SubR->_bf = 0;// else// SubR->_bf = 1;// //左旋// parent->_right = SubRL->_left;// if (SubRL->_left)// parent->_right->_parent = parent;// Node *ppNode = parent->_parent;// SubRL->_left = parent;// parent->_parent = SubRL;// if (ppNode == NULL)// {// _root = SubRL;// SubRL->_parent = NULL;// }// else// {// if (ppNode->_left == parent)// {// ppNode->_left = SubRL;// }// else// {// ppNode->_right = SubRL;// }// SubRL->_parent = ppNode;// }// if (SubRL->_bf == 1)// parent->_bf = -1;// else// parent->_bf = 0;//}//右旋void _RotateRL(Node *parent){//雙旋轉根據插入不同進行調整pf，Node* SubR = parent->_right;Node* SubRL = SubR->_left;//根據最后的根節點的bf進行調整int bf = SubRL->_bf;_RotateR(SubR);_RotateL(parent);//當bf為0，代表插入的就是他這個節點，所有的bf都變作0if (bf == 0){parent->_bf = SubR->_bf = 0;}//當bf為-1，代表這時是在這個根的左樹插入，h-1高度變作h。else if (bf == -1){parent->_bf = 0;SubR->_bf = 1;}//當bf為1時，代表是在這個旋轉后的根的右樹插入，h-1的高度作h。else{parent->_bf = -1;SubR->_bf = 0;}SubRL->_bf = 0;}//右旋void _RotateR(Node *parent){Node *SubL = parent->_left;Node *SubLR = SubL->_right;parent->_left = SubLR;if (SubLR) {SubLR->_parent = parent;}Node* ppNode = parent->_parent; //記錄根節點父親SubL->_right = parent;parent->_parent = SubL;if (ppNode == NULL) //考慮根節點情況{_root = SubL;SubL->_parent = NULL;}else{if (ppNode->_left == parent) //判斷旋轉以后的根應該鏈接在根的父親的那邊{ppNode->_left = SubL;}else{ppNode->_right = SubL;}SubL->_parent = ppNode;}parent->_bf = SubL->_bf = 0; //重置平衡因子} protected:Node* _root; };?
總結
- 上一篇： 机器学习实战教程（四）：朴素贝叶斯基础篇
- 下一篇： 搜索二叉树