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