一. 认识AVL树AVL树是最先发明的自平衡二叉查找树AVL是一颗空树或者具备下列性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树实现这里我们引入一个平衡因子balancefactor的概念每个结点都有一个平衡因子任何结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0 / 1 / -1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡类似于一个风向标不用平衡因子也可以实现AVL树但是那样会比较绕大差不差最终还是来控制高度。AVL树是高度平衡搜索二叉树要求高度差不超过1为什么不是高度差为0呢0不是更好的平衡吗我们用画图软件实践操作一下就会发现不是不想这样设计而是有些情况是做不到高度差是0的——比如一棵树是2个结点4个结点等情况下高度差最好就是1无法做到高度差是0——也就是说不是不想做而是做不到AVL树整体结点数量和分布和完全二叉树类似高度可以控制在logN那么增删查改的效率也可以控制在O(logN)相比二叉搜索树有了本质的提升。二. AVL树的实现2.1 AVL树的结构templateclass K,class V struct AVLTreeNode { // 需要parent指针后序更新平衡因子的时候就可以看到 pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; // balance factor平衡因子 //节点的构造 AVLTreeNode(const pairK,V kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) { } };2.2 树的插入2.2.1 插入的大概过程插入一个值按二叉搜索树规则进行插入。新增结点以后只会影响祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新从新增结点-根结点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了具体情况我们下面再详细分析。更新平衡因子过程中没有出现问题则插入结束更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后本质调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。2.2.2 更新平衡因子更新原则平衡因子 右子树高度 - 左子树高度只有子树高度变化才会影响当前结点平衡因子插入结点会增加高度所以新增结点在parent的右子树parent的平衡因子新增结点在parent的左子树parent平衡因子--parent所在子树的高度是否变化决定了是否会继续往上更新。更新停止条件1、更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0或者1-0说明更新前parent子树一边高一边低新增的结点插入在低的那边插入后parent所在的子树高度不变不会影响parent的父亲结点的平衡因子更新结束。2、更新后parent的平衡因子等于1或-1更新前更新中parent的平衡因子变化为0-1或者0--1说明更新前parent子树两边一样高新增的插入结点后parent所在的子树一边高一边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲结点的平衡因子所以要继续向上更新。3、更新后parent的平衡因子等于2或-2更新前更新中parent的平衡因子变化为1~2或者-1~-2说明更新前parent子树一边高一边低新增的插入结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个——示例更新到10结点平衡因子为210所在的子树已经不平衡需要旋转处理——更新到中间结点3为根的子树高度不变不会影响上一层更新结束——最坏更新到根停止——bool Insert(const pairK,V kv) { if (_root nullptr) { _root new Node(ky); 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; } } Node* newnode new Node(kv); if (parent-_kv.first kv.first) { parent-_right newnode; } else { parent-_left newnode; } cur-_parent parent; //更新平衡因子 while (parent) { if (cur parent-_left) { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0) { break; } else if (parent-_kv 1 || parent-_kv -1) { cur parent; parent cur-_parent; } else if (parent-_kv 2 || parent-_kv -2) { //旋转 break; } else { assert(false); } } return true; }2.3 旋转2.3.1 旋转的原则1.保持树的搜索规则2.让旋转的树从不满足变平衡其次降低旋转树的高度旋转分为四种左单旋/右单旋/左右双旋/右左双旋2.3.2 右单旋如下图10为根的树有a / b / c抽象为三棵高度为h的子树(h 0)a / b / c均符合AVL树的要求。10可能是整棵树的根也可能是一个整棵树中局部的子树的根。这里a / b / c是高度为h的子树是一种概括抽象表示他代表了所有右单旋的场景实际右单旋形态有很多种具体图2 / 图3 / 图4 / 图5进行了详细描述。在a子树中插入一个新结点导致a子树的高度从h变成h 1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要往右边旋转控制两棵树的平衡。旋转核心步骤因为5 b子树的值 10将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h 2符合旋转原则。如果插入之前10整棵树的一个局部子树旋转后不会再影响上一层插入结束了。下面的四种情况演示只是作为参考 比较抽象具象图画不完的但是抽象图可以很好地代表具象图具象图也是这个逻辑大家作为参考就好了—2.3.2.1情况1插入前a / b / c高度h 02.3.2.2 情况2插入前a / b / c高度h 12.3.2.3 情况3插入前a / b / c高度h 22.3.2.4 情况4插入前a / b / c高度h 3void RotateR(Node* parent) { Node* SubL parent-_left; Node* SubLR SubL-_right; parent-_left SubLR; //1.别忘记跟新父节点 //2.SubLR 可能是空节点 if(SubLR!nullptr) SubLR-_parent parent; Node* pParent parent-_parent; SubL-_right parent; parent-_parent SubL; //这里的 parent 不一定就是根节点与它有关联的节点也要更新 if (parent _root) { _root SubL; SubL-_parent nullptr; } else { if (pParent-_left parent) { pParent-_left SubL; } else { pParent-_right SubL; } SubL-_parent pParent; } //更新平衡因子 SubL-_bf 0; parent-_bf 0; }2.3.3 左单旋如下图所展示的是10为根的树有a / b / c抽象为三棵高度为h的子树(h 0a / b / c均符合AVL树的要求。10可能是整棵树的根也可能是一个整棵树中局部的子树的根。这里a / b / c是高度为h的子树是一种概括抽象表示他代表了所有右单旋的场景实际右单旋形态有很多种具体跟上面左旋类似。在a子树中插入一个新结点导致a子树的高度从h变成h 1不断向上更新平衡因子导致10的平衡因子从1变成210为根的树左右高度差超过1违反平衡规则。10为根的树右边太高了需要往左边旋转控制两棵树的平衡。旋转核心步骤因为10 b子树的值 15将b变成10的右子树10变成15的左子树15变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h 2符合旋转原则。如果插入之前10整棵树的一个局部子树旋转后不会再影响上一层插入结束了。void RotateL(Node* parent) { Node* SubR parent-_right; Node* SubRL SubR-_left; Node* pParent parent-_parent; parent-_right SubRL; SubR-_left parent; if (SubRL) SubRL-_parent parent; parent-_parent SubR; if (parent _root) { SubR-_parent nullptr; _root SubR; } else { if (pParent-_left parent) { pParent-_left SubR; } else { pParent-_right SubR; } SubR-_parent pParent; } SubR-_bf 0; parent-_bf 0; }2.3.4 左右双旋void RotateLR(Node* parent) { Node* SubL parent-_left; Node* SubLR SubL-_right; int bf SubLR-_bf; RotateL(parent-_left); RotateR(parent); if (bf -1) { SubLR-_kv 0; parent-_kv 1; SubL-_kv 0; } else if (bf 1) { SubLR-_kv 0; parent-_kv 0; SubL-_kv -1; } else if (bf 0) { SubLR-_kv 0; parent-_kv 0; SubL-_kv 0; } else { assert(false); } }2.3.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) { SubRL-_kv 0; parent-_kv 0; SubR-_kv 1; } else if (bf 1) { SubRL-_kv 0; parent-_kv -1; SubL-_kv 0; } else if (bf 0) { SubRL-_kv 0; parent-_kv 0; SubR-_kv 0; } else { assert(false); } }三. AVL树的查找3.1 代码示例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; } else { return cur; } } return nullptr; }四. AVL树的平衡性检查为确保 AVL 树实现无误需验证两个核心条件二叉搜索树特性 高度平衡特性。4.1 代码示例public: bool _IsBalanceTree() { return IsBalanceTree(_root); } private: bool IsBalanceTree(Node* root) { if (root nullptr) { return true; } int leftheight Height(root-_left); int rightheight Height(root-_right); int diff rightheight - leftheight; if (abs(diff) 2) { cout root-_kv.first 高度差异常endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } return IsBalanceTree(root-_left) IsBalanceTree(root-_right); } int Height(Node* root) { if (root nullptr) { return 0; } int leftheight Height(root-_left); int rightheight Height(root-_right); return leftheight rightheight ? leftheight 1 : rightheight 1; }#includeAVLTree.h void TestAVLTree1() { AVLTreeint, int t; // 常规的测试例 //int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 特殊的带有双旋场景的测试用例 int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { /*if (e 14) { int i 0; }*/ t.Insert({ e,e }); //cout e - t.IsBalanceTree() endl; } t.Inorder(); cout t._IsBalanceTree() endl; } int main() { TestAVLTree1(); return 0; }