一、AVL树的概念

二、AVL树的实现

1、AVL树的节点

key,vaule的二叉搜索树，需要用三叉链，多定义的父亲指针用来更新平衡因子

template<class K,class V>
struct AVLTreeNode
{pair<k, v> _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;//banlance factor平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};

2、 AVL的插入的过程

3、平衡因子的更新

	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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}//更新平衡因子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){//高度差大于1，进行旋转//右单旋，左边高if (parent->_bf == -2 && cur->_bf == -1)RotateR(parent);else if (parent->_bf == 2 && cur->_bf == 1)//纯粹的右边高，进行左单旋RotateL(parent);else if (parent->_bf == -2 && cur->_bf == 1)//进行左右双旋{RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//进行右左双旋{RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}

三、旋转

1、持搜索树的规则
2、让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

1、右单旋

左边的高度大于右边时右旋转

	//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* ppNode = parent->_parent;parent->_left = subLR;subL->_right = parent;if (subLR)subLR->_parent = parent;parent->_parent = subL;subL->_parent = ppNode;if (ppNode == nullptr){_root = subL;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}}parent->_bf = 0;subL->_bf = 0;}

2、左单旋

右边高进行左单旋

//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* ppNode = parent->_parent;parent->_right = subRL;subR->_left = parent;if (subRL)subRL->_parent = parent;parent->_parent = subR;subR->_parent = ppNode;if (ppNode == nullptr){_root = subR;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}}parent->_bf = 0;subR->_bf = 0;}

3、右左双旋

//左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0){subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else{assert(false);}
}

4、右左双旋

	//右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}else{assert(false);}}

四、AVL树平衡检测

bool IsBalanceTree()
{return _IsBalanceTree(_root) != -1;
}int _IsBalanceTree(Node* root){if (root == nullptr)return 0;int left = _IsBalanceTree(root->_left);if (left == -1)return -1;int right = _IsBalanceTree(root->_right);if (right == -1)return -1;int dif = right - left;if (abs(dif) >= 2){cout << root->_kv.first << "高度异常" << endl;return -1;}if (dif != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return - 1;}return abs(left - right) < 2 ? max(left, right) + 1 : -1;}

五、AVL树查找

	Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first > key){cur = cur->_left;}else if (cur->_kv.first < key){cur = cur->_right;}elsereturn cur;}return nullptr;}