1.什么是AVL樹

AVL樹也叫二叉搜索平衡樹
因為二叉搜索樹如果插入順序是有序的，那么這棵樹的查找效率將會是O(N)，所以說在實際情況下，二叉搜索很少被使用
為了解決這個缺點，誕生了AVL樹

左右子樹都是AVL樹，左右子樹高度差絕對值（平衡因子值）不超過1（平衡因子值不一定是1，這只是一種實現方案）

一顆高度不平衡的樹：

一顆AVL樹：

一般的二叉搜索樹在插入新節點以及刪除節點時，都有可能會破壞樹的平衡，所以AVL樹需要對插入以及刪除接口做修改，每次插入刪除時，都要檢測一下當前的樹時候符合AVL樹，如果不符合，要做出相應的調整措施
由于AVL樹的這種特殊性質，使得它的查找效率是百分百的O(logn)

2.AVL樹的實現

2.1節點類和基本結構

template<class K, class V>
struct AVLTreeNode //AVL樹節點
{AVLTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}//用三叉鏈,方便更新祖先的平衡因子AVLTreeNode<K,V>* _left;AVLTreeNode<K,V>* _right;AVLTreeNode<K,V>* _parent;pair<K, V> _kv;//存儲的數據int _bf;//balance factor平衡因子
};

_left：指向左子樹
_right：指向右子樹
_parent：指向父節點
_bf：平衡因子
_kv：存儲的鍵值對

template<class K,class V>
struct AVLTree //AVL樹
{typedef AVLTreeNode<K, V> Node;
private:Node* _root;//定義一個根節點
};

2.2插入

插入有三個步驟：

1. 按照二叉搜索樹規則插入節點
2. 插入完成后更新平衡因子
3. 若平衡因子不正確需要采取措施

更新平衡因子規則:

1. 新增在右，父親的平衡因子_bf加一
   新增在左，父親的平衡因子_bf減一
2. 更新完成后,父親的_bf == 1 || -1，說明父親插入前的_bf一定是0,插入后左右子樹一邊高一邊低，需要繼續向上更新平衡因子

3. 更新完成后父親的bf==0，說明父親在插入前的_bf是1/-1,并且插入后兩邊高度一致，不需要繼續往上更新
   

4. 更新完成后父親的_bf == 2 || -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(kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}//找到了位置cur，開辟空間cur = new Node(kv);//父親指向子if(kv.first > parent->_kv.first){	parent->_right = cur;}else{parent->_left = cur;}//子指向父cur->_parent = parent;//插入完成，檢查平衡因子//沿插入位置cur向上更新平衡因子while(parent)//parent需要不斷向上更新{	if(cur == parent->right){parent->_bf++;}else{parent->_bf--;}//不用向上更新if(parent->_bf == 0){	break;}//高度出現變化，向上更新平衡因子else if(parent->_bf == 1 || parent->_bf == -1){	parent = parent->parent;cur = cur->parent;}else if(parent->_bf == 2){//parent所在的子樹不平衡了,需要旋轉處理//后面會處理這處}}
}

2.3旋轉處理

2.3.1左單旋

2.3.2右單旋

2.3.3左右雙旋

2.3.4右左雙旋

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_+left;parent->_right = subRL;if(subRL){subRL->_parent = parent;}Node* parentparent = parent->_parent;subR->_left = parent;parent->_parent = subR;if(parent == _root){_root = subR;subR->_parent = nullptr;}else{if(parentparent->_left = parent){parentparent->_left = subR;}else{parentparent->_right = subR;}subR->_parent = parentparent;}subR->_bf = parent->_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 (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);subLR->_bf = 0;if (bf == 1){parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subL->_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){subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;}else assert(false);
}