AVL樹本質(zhì)上是一顆二叉搜索樹，但是它和普通的二叉搜索樹不同的是它的每一個結(jié)點的兩個子樹的高度差不超過一，所以AVL樹也叫做平衡二叉樹，如果刪除或者插入一個結(jié)點使其高度差變化，就要對其進(jìn)行旋轉(zhuǎn)再使它平衡。這樣就解決了二叉搜索樹鏈表化后（類似下圖第三種情況）中各類操作中的時間復(fù)雜度的提高的狀況。
和普通的二叉搜索樹一樣，AVL樹的結(jié)點中包含左右孩子結(jié)點，key值與value值，不同的是AVL樹中為了方便旋轉(zhuǎn)還添加了_parent（父節(jié)點），最后還有最重要的 _bf（平衡因子：右子樹高度-左子樹高度），用來判斷AVL是否平衡。當(dāng)平衡因子大于等于二的時候就說明該結(jié)點不平衡需要旋轉(zhuǎn)操作。
template<class K,class V>struct AVLTreeNode{ AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; K _key; V _value; int _bf; AVLTreeNode(const K& key, const V& value) :_left(NULL) ,_right(NULL) ,_parent(NULL) ,_key(key) ,_value(value) ,_bf(0) {}};旋轉(zhuǎn)操作是AVL樹在插入或者刪除操作后要維持其平衡的一種手段。對于一個平衡的結(jié)點（-1<=_bf<=1）來說，由于任意的結(jié)點最多有兩個孩子，當(dāng)插入或者刪除一個結(jié)點之后，其高度差有可能會變?yōu)?或者-2，此時失去平衡。具體可分為如下幾種情況： 
第一種和第二種情況為對稱的兩種情況，以右旋為例，如下圖：
以插入一個結(jié)點舉例，當(dāng)d結(jié)點為插入結(jié)點時，插入后發(fā)現(xiàn)a的_bf變?yōu)?2，AVL樹失去平衡，而a的左子樹b結(jié)點的平衡因子為-1，此時整棵樹就應(yīng)該向右旋轉(zhuǎn)即順時針旋轉(zhuǎn)。
具體操作即讓b作為根結(jié)點同時也是a的父結(jié)點，a下移稱為b的右孩子，e結(jié)點按照二叉搜索樹的性質(zhì)，key值比b的key值大又比a的key值小，所以把他放在a的左孩子。 
代碼實現(xiàn)
void RotateR(Node* parent) {//右旋 Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = subL; if (parent == _root) { _root = subL; _root->_parent = NULL; } else { if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } parent->_bf = subL->_bf = 0; }第三種情況和第四種情況也為對稱，以左右旋轉(zhuǎn)為例，如下圖： 還是以插入一個結(jié)點為例，當(dāng)插入結(jié)點在d位置時，發(fā)現(xiàn)a的_bf為-2，而其左孩子的 _bf為1，這時我們發(fā)現(xiàn)單次的旋轉(zhuǎn)無法達(dá)到平衡，要經(jīng)過兩次旋轉(zhuǎn)。 具體操作即先以b為根結(jié)點進(jìn)行左旋，使e成為b的父結(jié)點，再根據(jù)二叉搜索樹的性質(zhì)，使d成為b結(jié)點的右孩子。旋轉(zhuǎn)完成后則變成了第一種情況，再進(jìn)行一次右旋轉(zhuǎn)，最后得到平衡樹。 
AVL樹在插入的時候與二叉搜索樹相同，區(qū)別是在插入之后需要更新平衡因子，如果插入后AVL樹失衡，則要進(jìn)行相應(yīng)的旋轉(zhuǎn)來保持AVL樹的平衡。
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) {//找到要插入結(jié)點的父節(jié)點位置 if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key>cur->_key) { parent = cur; cur = cur->_right; } else { return false; } } //插入新結(jié)點 cur = new Node(key, value); if (key < parent->_key) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } while (parent) {//調(diào)整平衡因子 if (parent->_left == cur) parent->_bf -= 1; else parent->_bf += 1; if (parent->_bf == 0) break; else if (parent->_bf == 1 || parent->_bf == -1) {//父結(jié)點的平衡因子變化，繼續(xù)向上更新 cur = parent; parent = cur->_parent; } else if (parent->_bf == 2 ||parent->_bf ==-2) { if (parent->_bf == 2) { if (parent->_bf == 2) { if (cur->_bf == 1) { RotateL(parent); } else { RotateRL(parent); } } else { if (cur->_bf == -1) { RotateR(parent); } else { RotateLR(parent); } } break; } } } }其實AVL樹的刪除操作與二叉搜索樹基本相同，區(qū)別是AVL樹在刪除后，要從其真正刪除結(jié)點的父結(jié)點向上調(diào)整平衡。并且要注意在刪除操作中時刻調(diào)整每個結(jié)點的平衡因子。 
如圖：假定要刪除的結(jié)點為紅色結(jié)點，而在二叉搜索樹的刪除操作中，是把藍(lán)色結(jié)點替換掉紅色結(jié)點，真正刪除的是藍(lán)色結(jié)點，所以此時就應(yīng)該從黃色結(jié)點的位置向上一層層調(diào)整平衡。
bool Remove(const K& key) { return _Remove(_root,key); } bool _Remove(Node* root,const K& key) {//與二叉搜索樹的刪除基本相同 if (root == NULL) return false; if (key < root->_key) { root->_bf += 1; return _Remove(root->_left, key); } else if (key>root->_key) { root->_bf -= 1; return _Remove(root->_right, key); } else { Node* del = root; if (root->_left == NULL) { root->_right->_parent = root->_parent; root = root->_right; } else if (root->_right == NULL) { root->_left->_parent = root->_parent; root = root->_left; } else { Node* subLeft = root->_right; while (subLeft->_left) { subLeft = subLeft->_left; } root->_key = subLeft->_key; root->_value = subLeft->_value; del = subLeft; subLeft = subLeft->_right; while (del->_parent) {//調(diào)整平衡，從要被真正delete的那個結(jié)點開始向上調(diào)整 if (del->_parent->_bf == 2 || del->_parent->_bf == -2) { if (del->_parent->_bf == 2) { if (del->_bf == 1) RotateL(del->_parent); else RotateRL(del->_parent); } else { if (del->_parent->_bf == -2) { if (del->_bf == 1) RotateR(del->_parent); else RotateLR(del->_parent); } } } else return true; } } delete del; return true; } }在這里我們給出了兩種方式來判斷，第一種方式是通過求樹的每個結(jié)點左右孩子的高度來計算平衡因子。
bool IsBalance() {//判斷是否平衡 return _IsBalance(_root); } size_t _Depth(Node* root) {//求深度 if (root == NULL) return 0; size_t leftDepth = _Depth(root->_left); size_t rightDepth = _Depth(root->_right); return leftDepth < rightDepth ? rightDepth+1 : leftDepth+1; } bool _IsBalance(Node* root) {//時間復(fù)雜度O(N2) if (root == NULL) return true; size_t leftH = _Depth(root->_left); size_t rightH = _Depth(root->_right); if ((rightH - leftH) != root->_bf) { cout << "平衡因子異常：" << root->_key << endl; } return abs(rightH - leftH) <= 1 && _IsBalance(root->_left) && _IsBalance(root->_right); }第二種是直接在尋找每個節(jié)點左右葉結(jié)點的同時計算其平衡因子。這樣大大的提高了效率。使時間復(fù)雜度大大減小。
bool IsBalanceOP() {//判斷是否平衡 size_t depth= 0; return _IsBalanceOP(_root,depth); } bool _IsBalanceOP(Node* root, size_t& depth) {//時間復(fù)雜度O(N) if (root == NULL) { depth = 0; return true; } size_t leftDepth, rightDepth; if (_IsBalanceOP(root->_left, leftDepth) && _IsBalanceOP(root->_right, rightDepth)) { depth = leftDepth < rightDepth ? rightDepth + 1 : leftDepth + 1; return abs(leftDepth - rightDepth) < 2; } }新聞熱點
疑難解答
圖片精選
