1. AVL树的概念AVL树是最先发明的自平衡二叉搜索树。AVL树是一棵空树或是一棵具有以下性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树是一棵高度平衡搜索二叉树通过控制高度差去控制平衡。平衡因子每个结点都有一个平衡因子任何结点的平衡因子都等于其右子树的高度减去左子树的高度任何结点的平衡因子一定等于-1/0/1AVL树整体结点数量和分布与完全二叉树类似高度可以控制在logN增删查改的效率也可以控制在O(logN)2.AVL树的实现2.1 AVL树的结构templateclassK,classVstructAVLTreeNode{pairK,V_kv;AVLTreeNode*_left;AVLTreeNode*_right;AVLTreeNode*_parent;int_bf;// 平衡因子AVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)// 新增结点的平衡因子一定是0{}};templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;public:// ...private:Node*_rootnullptr;};2.2 AVL树的插入2.2.1 AVL树插入一个值的大概过程插入一个值按二叉搜索树的规则进行插入。插入结点后只会影响其祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新从新增结点-根节点路径上的结点的平衡因子最坏情况下要更新到根。更新平衡因子过程中没有出现问题则插入结束。更新平衡因子过程中如果出现不平衡平衡因子2/-2需要对不平衡子树进行旋转。旋转调平衡的同时也降低了子树的高度不会再影响上一层则插入结束。2.2.2 平衡因子更新更新规则平衡因子 右子树高度 - 左子树高度只有子树高度变化才会影响当前结点平衡因子插入结点会增加高度所以新增节点在parent的右子树parent的平衡因子新增结点在parent的左子树平衡因子–parent的子树高度是否变化决定了是否继续往上更新更新停止条件更新后parent的平衡因子等于0说明parent子树高度不变不会影响parent父节点的平衡因子更新结束更新后parent的平衡因子等于1或-1parent所在子树符合平衡要求但高度增加了1会影响parent父节点的平衡因子所以要继续向上更新更新后parent的平衡因子等于2或-2说明AVL树的平衡被破坏需要进行旋转。旋转后parent所在子树高度降低所以旋转后也不需要继续向上更新插入结束2.2.3 插入结点及更新平衡因子代码实现// 插入boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;// 更新平衡因子while(parent){if(curparent-_left)parent-_bf--;elseparent-_bf;if(parent-_bf0){// 更新结束break;}elseif(parent-_bf-1||parent-_bf1){// 继续向上更新curparent;parentparent-_parent;}elseif(parent-_bf-2||parent-_bf2){// 旋转if(parent-_bf-2cur-_bf-1)RotateR(parent);elseif(parent-_bf2cur-_bf1)RotateL(parent);elseif(parent-_bf-2cur-_bf1)RotateLR(parent);elseif(parent-_bf2cur-_bf-1)RotateRL(parent);break;}else{assert(false);}}returntrue;}2.3 旋转2.3.1 旋转的原则保持搜索树的规则让旋转的树从不平衡到平衡其次降低树的高度旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋2.3.2 右单旋本图展示的是一棵以 10 为根的树a/b/c 抽象为三棵高度为 h 的子树(h 0)a/b/c 均满足 AVL 树的要求。10 可能是整棵树的根也可能是整棵树中局部的子树的根图中具体数值可以是任何值只要大小关系满足 AVL 树的要求即可。在 a 子树中插入一个新结点导致 a 子树的高度从 h 变为 h 1不断向上更新平衡因子导致 10 的平衡因子从 -1 变成 -2,10为根的树左右高度差超过1违法平衡规则。10 为根的树左边高需要往右边旋转控制两棵树的平衡。旋转核心步骤b 变为 5 的左子树10 变成 5 的右子树5 变成这棵树新的根符合搜索树的规则控制了平衡同时这棵树的高度恢复到了插入之前的 h 2符合旋转原则。旋转后不会影响上一层插入结束。2.3.3 右单旋代码实现void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; // 连接subLR与parent parent-_left subLR; // subLR不为空时才能更改其parent if (subLR) subLR-_parent parent; // 记录parent的原_parent Node* parentParent parent-_parent; // 连接subL与parent subL-_right parent; parent-_parent subL; // parent有可能是整棵树的根也可能是局部的子树 // 如果是整棵树的根要修改其_root if (parentParent nullptr) { _root subL; subL-_parent nullptr; } // 如果是局部的子树要与上一层连接 else { // 若parent为其原父节点的左孩子结点 // 则修改原父节点的左孩子为subL if (parent parentParent-_left) { parentParent-_left subL; } // 若parent为其原父节点的右孩子结点 // 则修改原父节点的右孩子为subL else { parentParent-_right subL; } // 将subL的父节点指针指向parent的原_parent subL-_parent parentParent; } // 此时parent和subL平衡更新平衡因子为0 subL-_bf parent-_bf 0; }2.3.4 左单旋本图展示的是一棵以 10 为根的树a/b/c 抽象为三棵高度为 h 的子树(h 0)a/b/c 均满足 AVL 树的要求。10 可能是整棵树的根也可能是整棵树中局部的子树的根图中具体数值可以是任何值只要大小关系满足 AVL 树的要求即可。在 a 子树中插入一个新结点导致 a 子树的高度从 h 变为 h 1不断向上更新平衡因子导致 10 的平衡因子从 1 变成 2,10为根的树左右高度差超过1违法平衡规则。10 为根的树右边高需要往左边旋转控制两棵树的平衡。旋转核心步骤b 变为 10 的右子树10 变成 15 的左子树15 变成这棵树新的根符合搜索树的规则控制了平衡同时这棵树的高度恢复到了插入之前的 h 2符合旋转原则。旋转后不会影响上一层插入结束。2.3.5 左单旋代码实现voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}subR-_bfparent-_bf0;}2.3.6 左右双旋新插入结点在失衡结点的左孩子的右子树上时需要进行左右双旋。根据旋转后平衡因子的变化可以分为三种情况h 1 时新增结点在 e 子树e 子树高度从 h - 1 变为 h并不断更新 8-5 - 10 的平衡因子引发旋转其中 8 的平衡因子为 -1旋转后 8 和 5 平衡因子为 010 平衡因子为 1h 1 时新增结点在 f 子树f 子树高度从 h - 1 变为 h并不断更新 8-5 - 10 的平衡因子引发旋转其中 8 的平衡因子为 1旋转后 8 和 10 平衡因子为 05 平衡因子为 -1h 0 时 a/b/c 都是空树 b 本身就是新增结点不断更新 5-10 平衡因子引发旋转其中 8 的平衡因子为 0旋转后 8 和 5 和 10 的平衡因子均为 02.3.7 左右双旋代码实现voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(subL);RotateR(parent);if(bf0){subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1){subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1){subL-_bf-1;subLR-_bf0;parent-_bf0;}else{assert(false);}}2.3.8 右左双旋新插入结点在失衡结点的右孩子的左子树上时需要进行右左双旋。根据旋转后平衡因子的变化可以分为三种情况h 1 时新增结点在 e 子树e 子树高度从 h - 1 变为 h并不断更新 12-15 - 10 的平衡因子引发旋转其中 12 的平衡因子为 -1旋转后 10 和 12 平衡因子为 015 平衡因子为 1h 1 时新增结点在 f 子树f 子树高度从 h - 1 变为 h并不断更新 12-15 - 10 的平衡因子引发旋转其中 12 的平衡因子为 1旋转后 15 和 12 平衡因子为 010 平衡因子为 -1h 0 时 a/b/c 都是空树 b 本身就是新增结点不断更新 15-10 平衡因子引发旋转其中 12 的平衡因子为 0旋转后 10 和 12 和 15 的平衡因子均为 02.3.9 右左双旋代码实现void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; RotateR(subR); RotateL(parent); if (bf 0) { subR-_bf 0; subRL-_bf 0; parent-_bf 0; } else if (bf -1) { subR-_bf 1; subRL-_bf 0; parent-_bf 0; } else if (bf 1) { subR-_bf 0; subRL-_bf 0; parent-_bf -1; } else { assert(false); } }2.4 AVL树查找AVL 树查找逻辑与二叉搜索树逻辑相同搜索效率为O(logN)Node* Find(const K key) { Node* cur _root; while (cur) { if (key cur-_kv.first) { cur cur-_right; } else if (key cur-_kv.first) { cur cur-_left; } else { return cur; } } return nullptr; }2.5 AVL 树平衡检测通过检查左右子树高度差可以验证AVL树是否合格同时可以检查平衡因子是否出现问题boolIsBalanceTree(){return_IsBalanceTree(_root);}bool_IsBalanceTree(Node*root){if(rootnullptr){// 空树也是AVL树returntrue;}intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);intdiffrightHeight-leftHeight;if(abs(diff)2){coutroot-_kv.first高度差异常endl;}if(diff!root-_bf){coutroot-_kv.first平衡因子异常endl;}// 左右子树都是AVL树则该树一定是AVL树return_IsBalanceTree(root-_left)_IsBalanceTree(root-_right);}