1、AVL樹的概念

二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當(dāng)于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法：當(dāng)向二叉搜索樹中插入新結(jié)點(diǎn)后，如果能保證每個(gè)結(jié)點(diǎn)的左右子樹高度之差的絕對(duì)值不超過1(需要對(duì)樹中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。

AVL樹實(shí)現(xiàn)這里我們引入一個(gè)平衡因子(balance factor)的概念，每個(gè)結(jié)點(diǎn)都有一個(gè)平衡因子，任何結(jié)點(diǎn)的平衡因子等于右子樹的高度減去左子樹的高度，也就是說任何結(jié)點(diǎn)的平衡因子等于0/1/-1，AVL樹并不是必須要平衡因子，但是有了平衡因子可以更方便我們?nèi)ミM(jìn)?觀察和控制樹是否平衡，就像一個(gè)風(fēng)向標(biāo)一樣。

一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：
1、它的左右子樹都是AVL樹。
2、左右子樹高度之差(簡(jiǎn)稱平衡因子)的絕對(duì)值不超過1(-1/0/1)。

平衡因子的計(jì)算我們統(tǒng)一用右邊高度減去左邊高度，后面的實(shí)現(xiàn)也是如此。當(dāng)然也可以反過來。

思考一下為什么AVL樹是高度平衡搜索二叉樹，要求高度差不超過1，而不是高度差是0呢？0不是更好的平衡嗎？畫畫圖分析我們發(fā)現(xiàn)，不是不想這樣設(shè)計(jì)，而是有些情況是做不到高度差是0的。比如一棵樹是2個(gè)結(jié)點(diǎn)，4個(gè)結(jié)點(diǎn)等情況下，高度差最好就是1，無法作為高度差是0。而如果高度差是2/3/4…呢？也是不行的，因?yàn)檫@樣在插入刪除時(shí)的旋轉(zhuǎn)調(diào)整將會(huì)非常麻煩。

下面對(duì)AVL樹的效率進(jìn)行分析：

---

2、AVL樹的結(jié)構(gòu)

節(jié)點(diǎn)的結(jié)構(gòu)是三叉鏈，需要存儲(chǔ)父節(jié)點(diǎn)的指針，還需要存儲(chǔ)bf平衡因子變量。存儲(chǔ)父節(jié)點(diǎn)的指針是為了在更新平衡因子的時(shí)候可以快速找到父節(jié)點(diǎn)。
然后我們這里就直接實(shí)現(xiàn)key/value模型了，所以需要兩個(gè)模板參數(shù)，分別用K、V來表示，通過pair存儲(chǔ)。

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:private:Node* _root = nullptr;
};

---

3、AVL樹的插入

3.1、大概過程

這里的插入代碼和我們之前寫的二叉搜索樹是類似的，只不過由于插入之后平衡因子可能發(fā)生變化，例如變成2/-2，那么就需要調(diào)整平衡并更新平衡因子，所以比二叉搜索樹多了一步更新平衡因子的過程。

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return false;}Node* parent = nullptr;Node* cur = _root;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->_right = cur;elseparent->_left = cur;cur->_parent = parent;// 更新平衡因子// ...return true;
}

---

3.2、更新平衡因子

更新規(guī)則：
1、新增節(jié)點(diǎn)在父節(jié)點(diǎn)的左側(cè)，父節(jié)點(diǎn)的平衡因子--。
2、新增節(jié)點(diǎn)在父節(jié)點(diǎn)的右側(cè)，父節(jié)點(diǎn)的平衡因子++。
3、更新后父節(jié)點(diǎn)的平衡因子==0，說明父節(jié)點(diǎn)所在的子樹高度沒有發(fā)生變化，不會(huì)影響祖先，不用再沿著到根節(jié)點(diǎn)的路徑往上更新，更新結(jié)束。
4、更新后父節(jié)點(diǎn)的平衡因子==1/-1，說明父節(jié)點(diǎn)所在的子樹高度發(fā)生了變化，會(huì)影響祖先，需要沿著到根節(jié)點(diǎn)的路徑往上更新。
5、更新后父節(jié)點(diǎn)的平衡因子==2/-2，說明父節(jié)點(diǎn)所在的子樹高度變化并且不平衡，需要對(duì)父節(jié)點(diǎn)所在的子樹旋轉(zhuǎn)并更新平衡因子。由于旋轉(zhuǎn)后父節(jié)點(diǎn)所在子樹高度并沒有增加，所以不需要再向上更新，更新結(jié)束。
6、若更新到根節(jié)點(diǎn)，則停止。

---

3.3、更新平衡因子代碼

while (parent)
{if (parent->_left == cur){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){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(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);}
}

正常情況下，節(jié)點(diǎn)的平衡因子要么是0，±1，±2，不會(huì)是其他值，但是說不準(zhǔn)我們寫的代碼有bug，所以對(duì)于其他值我們直接assert終止程序。

---

3.4、左單旋

代碼如下：

void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;parent->_right = curleft;if (curleft) curleft->_parent = parent;cur->_left = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;
}

---

3.5、右單旋

代碼如下：

void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;parent->_left = curright;if (curright)curright->_parent = parent;cur->_right = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;
}

---

3.6、右左雙旋

代碼如下：

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

這里bf==0這種情況不需要寫，包括bf==1和bf==-1這兩種情況中平衡因子=0的也不需要賦值，只需要寫出平衡因子不為0的賦值，因?yàn)樵谖覀儗懙淖笮陀倚瘮?shù)中已經(jīng)將平衡因子修改為0了。
這里我們?nèi)N情況分別寫出來是為了對(duì)應(yīng)上圖的分析，寫出來更加清晰、好理解。

---

3.7、左右雙旋

代碼如下：

void RotateLR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){curright->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else if (bf == -1){curright->_bf = 0;cur->_bf = 0;parent->_bf = 1;}else if (bf == 1){curright->_bf = 0;cur->_bf = -1;parent->_bf = 0;}else{assert(false);}
}

---

4、AVL樹的刪除

代碼如下：

bool Erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < key){parent = cur;cur = cur->_right;}else if (cur->_kv.first > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr)	// 左邊為空{if (_root == cur){_root = cur->_right;if (_root)_root->_parent = nullptr;delete cur;return true;}}else if (cur->_right == nullptr) // 右邊為空{if (_root == cur){_root = cur->_left;if (_root)_root->_parent = nullptr;delete cur;return true;}}else // 左右都不為空，尋找替換節(jié)點(diǎn){parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}cur->_kv.first = leftMax->_kv.first;cur->_kv.second = leftMax->_kv.second;cur = leftMax;}break;}}// 找不到直接返回if (cur == nullptr) return false;Node* del = cur;Node* delParent = parent;while (parent){if (parent->_left == cur){	parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){cur = parent;parent = parent->_parent;}else if (parent->_bf == 1 || parent->_bf == -1){break;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2){if (parent->_left->_bf == 0){cur = parent->_left;RotateR(parent);cur->_bf = 1;parent->_bf = -1;break;}else if (parent->_left->_bf == -1){cur = parent->_left;RotateR(parent);}else // parent->_left->_bf == 1;{cur = parent->_left->_right;RotateLR(parent);}}else // parent->_bf == 2{if (parent->_right->_bf == 0){cur = parent->_right;RotateL(parent);cur->_bf = -1;parent->_bf = 1;break;}else if (parent->_right->_bf == 1){cur = parent->_right;RotateL(parent);}else{cur = parent->_right->_left;RotateRL(parent);}}parent = cur->_parent;}else{assert(false);}}cur = del, parent = delParent;if (cur->_left == nullptr){if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;if (cur->_right)cur->_right->_parent = parent;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;if (cur->_left)cur->_left->_parent = parent;}delete cur;return true;
}

---

5、AVL樹的查找

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;elsereturn cur;}return nullptr;
}

---

6、AVL樹的平衡檢測(cè)

bool IsBalance(){return IsBalance(_root);}int Height()
{return Height(_root);
}bool IsBalance(Node* root)
{if (root == nullptr) return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << "平衡因子異常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(leftHeight - rightHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);
}int Height(Node* root)
{if (root == nullptr) return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

通過IsBalance函數(shù)來判斷樹中的平衡因子計(jì)算是否正確，如果存在異常就會(huì)打印輸出信息。
同時(shí)為了計(jì)算平衡因子，需要求出左右高度然后相減，所以還需要實(shí)現(xiàn)Height函數(shù)獲取樹的高度。

---

7、AVL樹的其他函數(shù)

這里實(shí)現(xiàn)構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、賦值運(yùn)算符重載、析構(gòu)函數(shù)、中序遍歷函數(shù)?；旧项愃魄懊娴亩嫠阉鳂?。

AVLTree():_root(nullptr)
{}AVLTree(const AVLTree<K, V>& t):_root(nullptr)
{_root = Copy(t._root, nullptr);
}AVLTree<K, V>& operator=(AVLTree<K, V> t)
{swap(_root, t._root);return *this;
}~AVLTree()
{Destroy(_root);
}void InOrder()
{InOrder(_root);cout << endl;
}Node* Copy(Node* root, Node* parent)
{if (root == nullptr) return nullptr;Node* copy = new Node(root->_kv);copy->_bf = root->_bf;copy->_parent = parent;copy->_left = Copy(root->_left, copy);copy->_right = Copy(root->_right, copy);return copy;
}void Destroy(Node*& root)
{if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;
}void InOrder(Node* root)
{if (root == nullptr) return;InOrder(root->_left);cout << root->_kv.first << " ";InOrder(root->_right);
}

---

完整代碼

#pragma oncetemplate<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:AVLTree():_root(nullptr){}AVLTree(const AVLTree<K, V>& t):_root(nullptr){_root = Copy(t._root, nullptr);}AVLTree<K, V>& operator=(AVLTree<K, V> t){swap(_root, t._root);return *this;}~AVLTree(){Destroy(_root);}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return false;}Node* parent = nullptr;Node* cur = _root;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->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent){if (parent->_left == cur){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){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(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;}bool Erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < key){parent = cur;cur = cur->_right;}else if (cur->_kv.first > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr)	// 左邊為空{if (_root == cur){_root = cur->_right;if (_root)_root->_parent = nullptr;delete cur;return true;}}else if (cur->_right == nullptr) // 右邊為空{if (_root == cur){_root = cur->_left;if (_root)_root->_parent = nullptr;delete cur;return true;}}else // 左右都不為空，尋找替換節(jié)點(diǎn){parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}cur->_kv.first = leftMax->_kv.first;cur->_kv.second = leftMax->_kv.second;cur = leftMax;}break;}}// 找不到直接返回if (cur == nullptr) return false;Node* del = cur;Node* delParent = parent;while (parent){if (parent->_left == cur){	parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){cur = parent;parent = parent->_parent;}else if (parent->_bf == 1 || parent->_bf == -1){break;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2){if (parent->_left->_bf == 0){cur = parent->_left;RotateR(parent);cur->_bf = 1;parent->_bf = -1;break;}else if (parent->_left->_bf == -1){cur = parent->_left;RotateR(parent);}else // parent->_left->_bf == 1;{cur = parent->_left->_right;RotateLR(parent);}}else // parent->_bf == 2{if (parent->_right->_bf == 0){cur = parent->_right;RotateL(parent);cur->_bf = -1;parent->_bf = 1;break;}else if (parent->_right->_bf == 1){cur = parent->_right;RotateL(parent);}else{cur = parent->_right->_left;RotateRL(parent);}}parent = cur->_parent;}else{assert(false);}}cur = del, parent = delParent;if (cur->_left == nullptr){if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;if (cur->_right)cur->_right->_parent = parent;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;if (cur->_left)cur->_left->_parent = parent;}delete cur;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;elsereturn cur;}return nullptr;}bool IsBalance(){return IsBalance(_root);}int Height(){return Height(_root);}void InOrder(){InOrder(_root);cout << endl;}private:Node* Copy(Node* root, Node* parent){if (root == nullptr) return nullptr;Node* copy = new Node(root->_kv);copy->_bf = root->_bf;copy->_parent = parent;copy->_left = Copy(root->_left, copy);copy->_right = Copy(root->_right, copy);return copy;}void Destroy(Node*& root){if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}void InOrder(Node* root){if (root == nullptr) return;InOrder(root->_left);cout << root->_kv.first << " ";InOrder(root->_right);}bool IsBalance(Node* root){if (root == nullptr) return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << "平衡因子異常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(leftHeight - rightHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}int Height(Node* root){if (root == nullptr) return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;parent->_right = curleft;if (curleft) curleft->_parent = parent;cur->_left = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;parent->_left = curright;if (curright)curright->_parent = parent;cur->_right = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;	RotateR(cur);RotateL(parent);if (bf == 0){curleft->_bf = 0;parent->_bf = 0;cur->_bf = 0;}else if (bf == -1){curleft->_bf = 0;parent->_bf = 0;cur->_bf = 1;}else if (bf == 1){curleft->_bf = 0;parent->_bf = -1;cur->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){curright->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else if (bf == -1){curright->_bf = 0;cur->_bf = 0;parent->_bf = 1;}else if (bf == 1){curright->_bf = 0;cur->_bf = -1;parent->_bf = 0;}else{assert(false);}}
private:Node* _root = nullptr;
};