AVL树
简介：
- 当搜索二叉树退化为单支树时，搜索效率极低，为了使搜索效率高，建立平衡搜索二叉树就需要AVLTree这样的平衡树来解决。
- 如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。
- 根据节点插入位置的不同，AVL树的旋转分为四种：
1. 新节点插入较高左子树的左侧 --- 左左：右单旋
即： 对60 进行右单旋2. 新节点插入较高右子树的右侧 --- 右右：左单旋
即： 对30 进行左单旋3. 新节点插入较高左子树的右侧 --- 左右：先左单旋再右单旋
将双旋变成单旋后再旋转，即： 先对 30 进行左单旋，然后再对 90 进行右单旋 ，旋转完成后再考虑平衡因子的更新。4. 新节点插入较高右子树的左侧 --- 右左：先右单旋再左单旋
将双旋变成单旋后再旋转，即： 先对90 进行右单旋，然后再对30 进行左单旋 ，旋转完成后再考虑平衡因子的更新。总结：假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR当pSubR的平衡因子为1时，执行左单旋当pSubR的平衡因子为-1时，执行右左双旋2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL当pSubL的平衡因子为-1是，执行右单旋当pSubL的平衡因子为1时，执行左右双旋旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。5.代码实现：#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <string> #include <assert.h> using namespace std;//二叉搜索树BinarySearchTree //struct BinarySearchTreeNodetemplate<class K,class V> struct AVLTreeNode {AVLTreeNode<K,V>* _left;//一定不要写成BSTreeNode*<K> _left; 这样编译器无法识别AVLTreeNode<K,V>* _right;AVLTreeNode<K,V>* _parent;pair<K, V> _kv;//右子树-左子树的高度差int _bf; // balance factor 平衡因子 // AVL树并没有规定必须要设计平衡因子 只是一个实现的选择，方便控制平衡AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){} };template<class K, class V> class AVLTree {typedef struct AVLTreeNode<K, V> Node; public:bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_bf = 0;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;}}//准备从parent插入cur = new Node(kv);if (parent->_kv.first > kv.first)//插左子树{parent->_left = cur;}else//插右子树{parent->_right = cur;}cur->_parent = parent;//新插入的节点指向parent 与父亲相连 （之所以在树节点中设置_parent是为了更新平衡因子方便，可以更快捷的搜索到父亲节点）//更新平衡因子while (parent)// 不要疏忽写成while (cur); 最远可能更新到 根的平衡因子{if (cur==parent->_left){parent->_bf--;}else{parent->_bf++;}// -1 0 | 1 0 // / \ / \ | / \ / \// 0 插入右边 0 0 | 0 插入左边 0 0 if (parent->_bf == 0) //插入节点后填上矮的那边， parent_bf: 由-1 or 1 -->> 0 高度不变，更新结束{break;}//插入节点后：// 若parent_bf: 由0 -->> -1 or 1高度改变，继续更新 // 若parent_bf:由-1 or 1 -->> -2 or 2 子树出现不平衡，需要旋转处理（左单旋/右单旋/左右双旋/右左双旋）else if (parent->_bf == 1 || parent->_bf == -1) //插入节点后导致一边变高了,parent_bf: 由0 -->> -1 or 1 高度改变，继续更新parent_bf (子树的高度变了，继续更新祖先){// 0 0 | 0 0 // / \ / \ | / \ / \// 0 0 插入右边 0 1 | 0 0 插入左边 -1 0 // \ \ | / / // 0 | 0cur = cur->_parent;parent = parent->_parent;// 0 1 | 0 -1 // / \ / \ | / \ / \// 0 1 更新parent_bf 0 1 | -1 0 更新parent_bf -1 0 //直到更新到根节点的祖先时才结束 （_root->_parent==nullptr 进不到while(cur){}循环里，所以结束） // \ \ | / / // 0 0 | 0 0}else if (parent->_bf == 2 || parent->_bf == -2)//插入节点后导致本来高一边又变高了，出现了parent_bf=±2,parent_bf: 由-1 or 1 -->> -2 or 2 子树出现不平衡，需要旋转处理（左单旋/右单旋/左右双旋/右左双旋）{//直线插入：单旋 折线插入：双旋//直线插入：单旋// a(1) a(2) b(0) | a(-1) a(-2) b(0) // / \ / \ / \ | / \ / \ / \// b(0) b(1) a左单旋,更新平衡因子 a(0) c(0) | b(0) b(-1) a右单旋,更新平衡因子 c(0) a(0) // \ \ \ | / / / // c(0) | c(0) if (parent->_bf == 2 && cur->_bf == 1) // 左单旋{RotateL(parent);//parent左单旋,更新平衡因子}else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋{RotateR(parent);//parent右单旋,更新平衡因子}//折线插入：双旋//①c为新增节点（左右双旋和右左双旋）// a(-1) a(-2) a(-2) c(0) | a(1) a(2) a(2) c(0) // / \ / \ / \ / \ | / \ / \ / \ / \ // b(0) b(1) b先左单旋 c(-1) a再右单旋 b(0) a(0) 更新平衡因子| b(0) b(-1) b先右单旋 c(1) a再左单旋 a(0) b(0) 更新平衡因子// / \ / \ / \ \ / \ | / \ / \ / \ \ / // c(0) b(0) | c(0) b(0) // / \ | / c的右给b的左 / c的左给a的右 // 上叙情况节点c为新增节点 不管左右双旋 还是右左双旋 最后节点平衡因子都被更新为0 //②c不是新增节点（左右双旋的两种情况最后的平衡椅子更新都不一样）// a(-1) a(-2)// / \ / \ a(-2) e(0)// b(0) d(0) b(1) d(0) / \ / \ // / \ / \ / \ / \ e(-2) d(0) b(0) a(1) //g(0) e(0) h(0) j(0) g(-1)e(-1) h(0) j(0) b先左单旋 / \ / \ a再右单旋 / \ / \ 更新后a的平衡因子为1，b的平衡因子为0，e的平衡因子为0// / / \ / / \ b(0) c(0) h(0) j(0) g(-1) f(-1) c(0) d(0)//i(0)f(0)c(0) i(0) f(-1) c(0) / \ / / / \ // / g(-1) f(-1) i(0) Q(0) h(0) j(0)// Q(0) / / // i(0) Q(0)// a(-1) a(-2)// / \ / \ a(-2) e(0)// b(0) d(0) b(1) d(0) / \ / \ // / \ / \ / \ / \ e(-1) d(0) b(-1) a(0) //g(0) e(0) h(0) j(0) g(-1)e(1) h(0) j(0) b先左单旋 / \ / \ a再右单旋 / \ / \ 更新后a的平衡因子为0，b的平衡因子为-1，e的平衡因子为0// / / \ / / \ b(0) c(-1)h(0) j(0) g(-1) f(-1) c(-1) d(0)//i(0)f(0)c(0) i(0) f(0) c(-1) / \ / / / / \ // / g(-1) f(0)Q(0) i(0) Q(0) h(0) j(0)// Q(0) / // i(0) // 上叙情况节点c不是新增节点,Q是新增节点 左右双旋/右左双旋 最后节点平衡因子的更新：左右双旋/右左双旋是不同的。上方仅介绍了左右双旋，方法一样//③c不是新增节点,q是新增节点（右左双旋的两种情况最后的平衡椅子更新都不一样，与左右双旋的方法一样这里不在介绍）// a(1) a(2) a(2) e(0) // / \ / \ / \ / \ // b(0) d(0) b(0) d(-1) b(0) e(1) a(0) d(1) // / \ / \ d先右旋 / \ a再左旋 / \ / \ 更新后a的平衡因子为0，d的平衡因子为1，e的平衡因子为0// e(0) c(1) e(-1) c(0) q(0) d(1) b(0) q(0) c(0)// / / \// q(0) c(0)// a(1) a(2) a(2) e(0) // / \ / \ / \ / \// b(0) d(0) b(0) d(-1) b(0) e(2) a(-1) d(0) // / \ / \ d先右旋 / \ a再左旋 / \ / \ 更新后a的平衡因子为-1，d的平衡因子为0，e的平衡因子为0// e(0) c(1) e(1) c(-1) d(0) b(0) q(0) c(0)// \ / \// q(0) q(0 c(0) // // //折线插入：双旋else if (parent->_bf == -2 && cur->_bf == 1) // 左右单旋{RotateLR(parent);//从parent处左右双旋}else if (parent->_bf == 2 && cur->_bf == -1) // 右左单旋{RotateRL(parent);//从parent处右左双旋}break;}else{assert(false);// 插入之前AVL树就存在不平衡的子树，|平衡因子| >= 2的节点 直接断言报错}}return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalanceTree(){return _IsBalanceTree(_root);}int Height(){return _Height(_root);}private:Node* _root = nullptr;void RotateL(Node* parent)//左单旋{Node* ppNode = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;//subR->_parent = nullptr; //不可以只写这一句 如果parent是根 必须要更新_root; 加上 _root = subR;}else{if (parent == ppNode->_left){ppNode->_left = subR;}else //parent == ppNode->_right{ppNode->_right = subR;}subR->_parent = ppNode;}//更新平衡因子parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent)//右单旋{Node* ppNode = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent= parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;//subR->_parent = nullptr; //不可以只写这一句 如果parent是根 必须要更新_root; 加上 _root = subR;}else{if (parent == ppNode->_left){ppNode->_left = subL;}else //parent == ppNode->_right{ppNode->_right = subL;}subL->_parent = ppNode;}//更新平衡因子parent->_bf = 0;subL->_bf = 0;}void RotateLR(Node* parent)//左右双旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);//RotateL(parent->_left);RotateR(parent);//更新平衡因子if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else{//subLR->_bf 旋转之前就有问题assert(false);}}void RotateRL(Node* parent)//右左双旋{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);//RotateL(parent->_right);RotateL(parent);//更新平衡因子if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else{//subRL->_bf 旋转之前就有问题assert(false);}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int lh = _Height(root->_left);//lh leftheight 左树高度int rh = _Height(root->_right);//rh rightheight 右树高度return lh > rh ? lh + 1 : rh + 1;}bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "节点平衡因子异常" << endl;return false;}if (diff != root->_bf){cout << root->_kv.first << "节点平衡因子不符合实际" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left)&& _IsBalanceTree(root->_right);} };void TestAVLTree1() {//int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };int a[] = { 30,29,28,27,26,25,24,11,8,7,6,5,4,3,2,1 };AVLTree<int, int> t;for (auto e : a){t.insert(make_pair(e, e));}t.InOrder();cout<<t.IsBalanceTree()<<endl; } void TestAVLTree2() {int a[] = { 30,29,28,27,26,25,24,11,8,7,6,5,4,3,2,1 };AVLTree<int, int> t;for (auto e : a){bool res = t.insert(make_pair(e, e));if (res){cout << "Inserted: " << e << endl;}else{cout << "Failed to insert: " << e << endl;}}t.InOrder();cout << t.IsBalanceTree() << endl; }int main() {//TestAVLTree1();TestAVLTree2();return 0; }//插入节点后：// 若parent_bf: 由0 -->> -1 or 1高度改变，继续更新 // 若parent_bf:由-1 or 1 -->> -2 or 2 子树出现不平衡，需要旋转处理（左单旋/右单旋/左右双旋/右左双旋）else if (parent->_bf == 1 || parent->_bf == -1) //插入节点后导致一边变高了,parent_bf: 由0 -->> -1 or 1 高度改变，继续更新parent_bf (子树的高度变了，继续更新祖先){// 0 0 | 0 0 // / \ / \ | / \ / \// 0 0 插入右边 0 1 | 0 0 插入左边 -1 0 // \ \ | / / // 0 | 0cur = cur->_parent;parent = parent->_parent;// 0 1 | 0 -1 // / \ / \ | / \ / \// 0 1 更新parent_bf 0 1 | -1 0 更新parent_bf -1 0 //直到更新到根节点的祖先时才结束 （_root->_parent==nullptr 进不到while(cur){}循环里，所以结束） // \ \ | / / // 0 0 | 0 0}else if (parent->_bf == 2 || parent->_bf == -2)//插入节点后导致本来高一边又变高了，出现了parent_bf=±2,parent_bf: 由-1 or 1 -->> -2 or 2 子树出现不平衡，需要旋转处理（左单旋/右单旋/左右双旋/右左双旋）{//直线插入：单旋 折线插入：双旋//直线插入：单旋// a(1) a(2) b(0) | a(-1) a(-2) b(0) // / \ / \ / \ | / \ / \ / \// b(0) b(1) a左单旋,更新平衡因子 a(0) c(0) | b(0) b(-1) a右单旋,更新平衡因子 c(0) a(0) // \ \ \ | / / / // c(0) | c(0) if (parent->_bf == 2 && cur->_bf == 1) // 左单旋{RotateL(parent);//parent左单旋,更新平衡因子}else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋{RotateR(parent);//parent右单旋,更新平衡因子}//折线插入：双旋//①c为新增节点（左右双旋和右左双旋）// a(-1) a(-2) a(-2) c(0) | a(1) a(2) a(2) c(0) // / \ / \ / \ / \ | / \ / \ / \ / \ // b(0) b(1) b先左单旋 c(-1) a再右单旋 b(0) a(0) 更新平衡因子| b(0) b(-1) b先右单旋 c(1) a再左单旋 a(0) b(0) 更新平衡因子// / \ / \ / \ \ / \ | / \ / \ / \ \ / // c(0) b(0) | c(0) b(0) // / \ | / c的右给b的左 / c的左给a的右 // 上叙情况节点c为新增节点 不管左右双旋 还是右左双旋 最后节点平衡因子都被更新为0 //②c不是新增节点（左右双旋的两种情况最后的平衡椅子更新都不一样）// a(-1) a(-2)// / \ / \ a(-2) e(0)// b(0) d(0) b(1) d(0) / \ / \ // / \ / \ / \ / \ e(-2) d(0) b(0) a(1) //g(0) e(0) h(0) j(0) g(-1)e(-1) h(0) j(0) b先左单旋 / \ / \ a再右单旋 / \ / \ 更新后a的平衡因子为1，b的平衡因子为0，e的平衡因子为0// / / \ / / \ b(0) c(0) h(0) j(0) g(-1) f(-1) c(0) d(0)//i(0)f(0)c(0) i(0) f(-1) c(0) / \ / / / \ // / g(-1) f(-1) i(0) Q(0) h(0) j(0)// Q(0) / / // i(0) Q(0)// a(-1) a(-2)// / \ / \ a(-2) e(0)// b(0) d(0) b(1) d(0) / \ / \ // / \ / \ / \ / \ e(-1) d(0) b(-1) a(0) //g(0) e(0) h(0) j(0) g(-1)e(1) h(0) j(0) b先左单旋 / \ / \ a再右单旋 / \ / \ 更新后a的平衡因子为0，b的平衡因子为-1，e的平衡因子为0// / / \ / / \ b(0) c(-1)h(0) j(0) g(-1) f(-1) c(-1) d(0)//i(0)f(0)c(0) i(0) f(0) c(-1) / \ / / / / \ // / g(-1) f(0)Q(0) i(0) Q(0) h(0) j(0)// Q(0) / // i(0) // 上叙情况节点c不是新增节点,Q是新增节点 左右双旋/右左双旋 最后节点平衡因子的更新：左右双旋/右左双旋是不同的。上方仅介绍了左右双旋，方法一样//③c不是新增节点,q是新增节点（右左双旋的两种情况最后的平衡椅子更新都不一样，与左右双旋的方法一样这里不在介绍）// a(1) a(2) a(2) e(0) // / \ / \ / \ / \ // b(0) d(0) b(0) d(-1) b(0) e(1) a(0) d(1) // / \ / \ d先右旋 / \ a再左旋 / \ / \ 更新后a的平衡因子为0，d的平衡因子为1，e的平衡因子为0// e(0) c(1) e(-1) c(0) q(0) d(1) b(0) q(0) c(0)// / / \// q(0) c(0)// a(1) a(2) a(2) e(0) // / \ / \ / \ / \// b(0) d(0) b(0) d(-1) b(0) e(2) a(-1) d(0) // / \ / \ d先右旋 / \ a再左旋 / \ / \ 更新后a的平衡因子为-1，d的平衡因子为0，e的平衡因子为0// e(0) c(1) e(1) c(-1) d(0) b(0) q(0) c(0)// \ / \// q(0) q(0 c(0) // // //折线插入：双旋
