1.AVL樹

1.AVL的概念

AVL樹可以是一個空樹。
它的左右子樹都是AVL樹，且左右子樹的高度差的絕對值不超過1。AVL樹是一顆高度平衡搜索二叉樹，通過控制高度差去控制平衡。
AVL樹整體結點數量和分布和完全二叉樹類似，高度可以控制在 log^N ，那么增刪查改的效率也可以控制在O(log^N ) ，相比二叉搜索樹有了本質的提升。

2.平衡因子

結點的平衡因子=右子樹的高度減去左子樹的高度，也就是說任何結點的平衡因子等于0/1/-1，AVL樹并不是必須要平衡因子，但是有了平衡因子可以更方便我們去進行觀察和控制樹是否平衡，就像?個風向標一樣。
為什么AVL樹是高度平衡搜索二叉樹，要求高度差不超過1，而不是高度差是0呢？
因為例如二和四個結點無法達到0.

2.AVl樹的實現

2.1AVL樹的結構

template<class K, class V>
struct AVLTreeNode
{// 需要parent指針，后續更新平衡因?可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://...
private:Node * _root = nullptr;
};

2.2AVL樹的插入

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}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;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因?while (parent){// 更新平衡因?if (cur == parent->_left)parent->_bf--;elseparent->_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){// 不平衡了，旋轉處理break;}else{assert(false);}}return true;
}

2.3 旋轉

2.3.1 旋轉的原則

保持搜索樹的規則
讓旋轉的樹從不滿足變平衡，其次降低旋轉樹的高度
旋轉總共分為四種，左單旋/右單旋/左右雙旋/右左雙旋。