目录1. AVLTree的定义2. 平衡因子3. AVLTree的基础接口插入旋转左单旋右单旋双旋4. AVLTree的测试5. 小结1. AVLTree的定义二叉搜索树BST虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。2. 平衡因子平衡因子不是必须的只是选择实现AVLTree的一种方式。平衡因子的优势是可以直接观察但是需要付出维护的代价。在每一个节点中都加入其平衡因子的数值一般习惯用右子树高度-左子树高度templatetypename k,typename v struct AVLTreeNode { typedef AVLTreeNodek, v Node; Node* _left; Node* _right; Node* _parent; int _bf;//balance factor pairk, v _kv; AVLTreeNode( const pairk,v kv make_pair(k(),v()) ) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };以下树为例进行分析。将平衡因子当作一个风向标。标出每一个节点现在的平衡因子新插入的节点会影响从根到该节点路径上所有节点的平衡因子每插入一个平衡因子就需要调整其祖先的平衡因子这也是为什么每个节点的成员需要设计一个parent。对于叶子结点每插入一个节点对于其双亲原来的叶子的变化插入在parent右边, 平衡因子插入在parent左边平衡因子--下面来讨论在普遍情况下插入节点后平衡因子的变化。首先任意树的平衡因子只会是-1 0 1(否则不满足AVL树的条件)1. 如果在插入节点之后parent的平衡因子是0就像上图的节点8说明原本是-1或者1然后新节点加入到了矮的那一边。2. 如果插入后parentr的平衡因子是1或-1说明原本parent的平衡因子本来是0在右或左插入一个。那此时parent的子树的高度就变化了需要继续向上更新。3. 如果插入后parent的平衡因子是2或者-2说明原本parent的平衡因子本来是-1或者1然后新节点加入到了长的那一边。此时parent的子树的高度也变化了需要继续向上更新。并且已经违反了AVL树的规则需要进行旋转。3. AVLTree的基础接口基本结构都和二叉搜索树类似。先实现结点templatetypename k,typename v struct AVLTreeNode { typedef AVLTreeNodek, v Node; Node* _left; Node* _right; Node* _parent; int _bf;//balance factor pairk, v _kv; AVLTreeNode(const pairk,v kv make_pair(k(),v()) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };再写树构造我们现在只强调一下拷贝构造。不能直接将根_root拷贝过来这样是两颗重复的树我们需要自己实现深拷贝。而树的拷贝需要递归构造函数里直接递归当然不合适所以需要再封装一层。插入插入的大逻辑如下bool insert(const pairk, v kv) { Node* parent nullptr; Node* cur _root; if (cur nullptr) { _root new Node(kv); return true; } 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; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) parent-_left cur; if (parent-_kv.first kv.first) parent-_right cur; cur-_parent parent; //开始调整parent的balance factor,因为是三叉链所以可以通过parent一路遍历向上 while (parent) { //先计算平衡因子 if (parent-_left cur) { parent-_bf--; } else if (parent-_right cur) { parent-_bf; } //再决定是否向上调整 if (parent-_bf 0) { break; } else if (parent-_bf 1 || parent-_bf -1) { //adjust up cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2) { //旋转 } else { //如果还有其他情况说明原节点的bf有问题不满足avl树的规范直接断掉 assert(0); } } return true; }在搜索二叉树的基础上插入变的更加复杂。首先比较的都是pair中的first也就是key值并且依然需要使用双指针否则不好接入最后就是需要插入完成之后调整_bf旋转如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。直接通过上文中的例子来进入“旋转”的主题左单旋新节点插入较高右子树的右侧开始向上遍历调整平衡因子调整到8的时候发现平衡因子是2需要旋转然后就将8这个节点传进我们的调节函数RotateL旋转方法9的左子树变成8的右子树8变成9的左子树这样旋转之后高度和加入节点之前没有变化。抽象图所有的分析中都要注意节点之间的高度差距不能超过1假设30为传入函数的需要调整的节点命名为parent60命名为subR a/b/c是三个等高的树如果a/b/c不等高就不能构成我们想调整的情况。总结一下就是左单旋需要将subRL连接到parent的右边因为60的左子树一定是大于30的然后将30连接到60的左边。可以先通过列举h0 h1 h2 h3等情况观察h0时最简单。也是上文引例中的情况。h1时的情况h2时情况的种类就很多了。a/b可能是xyz中的任意一种情况。c只能是x否则直接在该子树中就可以调节了。注意为什么是3*3*4因为左单旋对应的模型是在60的右树C下进行增加节点所以只有4个可以选择的位置。h3时先分析高度为3的子树的情况可能为x全满或者y非全满其中y共有14种情况。所以不讨论加节点的C树a/b树就已经有(141)*(141)种可能性因此解决这个问题还需要从抽象图入手将a、b、c当作高度为h的抽象树。代码实现旋转点平衡因子出现问题的点。左单旋其实只需要改变subR suRL parent三者的链接关系。parent可以是整棵树的根也可以是任意一个子树的根依然有逻辑bugsubRL和parent的_parent都还要修改。先只修改subRL的_parentparent是需要调整的节点的变量名_parent是节点内的成员变量subRL可能是空h0的时候就是空。但是parent和subR是一定存在的否则怎么会出现一个_bf是2一个_bf是1呢那如果这棵树本来自身只是一颗子树呢所以在改动parent-_parent的值之前要记录一下原来的parent-_parent对于parent-_parent的分析如果是空表明30原来的parent本来就是整棵树的根现在整棵树的根调整了我们需要调整下_root如果不是空就像之前的insert一样得从parentParent再去找我们左旋的这棵树是在左边还是右边。但是不用调整_root至此单旋的大逻辑就已经完成。节点链接好了但是我们现在还没有处理平衡因子。经过观察不难发现parent和subR的平衡因子都变成0了再加一句parent-_bf subR-_bf 0;void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) { subRL-_parent parent; } Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parentParent) { if (parentParent-_left parent) { parentParent-_left subR; } else { parentParent-_right subR; } } else { subR-_parent nullptr; this-_root subR; } subR-_parent parentParent; //调整平衡因子 parent-_bf subR-_bf 0; }为了便于记忆取名字的三个节点呈现一个“”形状要将凹陷的部分拉出来所以出现这种形状叫左旋。右单旋逻辑几乎和左旋是一样的只是交换了right和left读者可以自行尝试先写一写这个代码。void RotateR(Node* parent) { assert(parent); Node* subL parent-_left; Node* subLR subL-right; parent-_left subLR; if (subLR) { subLR-_parent parent; } //解决subL和parent的父节点问题 Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; if (parentParent nullptr) { _root subL; } else { if (parentParent-_left parent) { parentParent-_left subL; } else { parentParent-_right subL; } } subL-_parent parentParent; //调整平衡因子 parent-_bf subL-_bf 0; }实现好了左单旋和右单旋的代码回到原来的插入代码进行联系左旋的时候parent的bf2 cur的bf 1右旋的时候parent的bf-2 cur 的bf-1根据上述的两个条件要讨论哪些旋转方案也逐渐明朗cur-_bf1 parent-bf2左单旋cur-_bf-1 parent-bf-2(右单旋)cur-_bf-1 parent-bf2cur-_bf1 parent-bf-2来看后面两种情况双旋上面为单旋能解决的情况parent和subR的bf符号相同下面为符号相反h0按照之前的旋转思路此时进行左单旋能保证搜索树的特征但是没有完成旋转的初衷使高度差消失。这样旋只是让原来的右边高变成现在的左边高(h1)如果此时再右旋又会旋回去。也就是说左右旋面对这种情况只会原地打转。解决方法双旋先看h1或h0再看抽象图左双旋分为右单旋左单旋右双旋分为左单旋右单旋需要左双旋时第一次右单旋就将本来需要左双旋的变成上文最基本的模型因为此时涉及到对subR进行一次单旋需要使用到subRL的右子树所以需要单独再拆开一层树来分析。单旋的时候subRL不一定存在但这次都是在subRL的位置上加的数据所以subRL一定不为空还可以直接观察双旋结果直接看起始和终点状态将subRL这个节点变成根parent在左、subR在右然后subRL的左右子树分别分配给parent的右和subR的左总结subRL或者subLR会成为新的根他左边的子树分配给在两个节点中更左边的节点的右边他右边的子树分配给在两个节点中更右边的节点subR或subL / parent中的任意一个的左边双旋的代码实现的大逻辑当然是不正确的虽然每一次单旋都能保证父节点和子节点的转接但是没有考虑平衡因子的维护。问题整理双旋并不像单旋单纯的全部将平衡因子全部更新为0并且新节点加到b和c最后的结果还不一样。h为0的时候还是一种单独的情况更新完之后是全0以左双旋为例如果subRL的平衡因子是1 就是在C插入如果subRL的平衡因子是-1 就是在B插入如果是0则subRL本身是新加入的节点也就是上文所说的h是0的时候的特殊情况。RotateRL的意思就是先右单旋再左单旋左双旋和右双旋实现void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf;//采用直接观察法记录最初的subRL的_bf RotateR(subR); RotateR(parent); if (bf 0) { //说明subRL就是新加入的元素 subRL-_bf 0; parent-_bf 0; subR-_bf 0; } else if (bf -1) { parent-_bf 0; subRL-_bf 0; subR 1; } else if (bf 1) { parent-_bf 1; subR-_bf 0; subRL-_bf 0; } else { assert(0); } } void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf; RotateL(subL); Rotate(parent); if (bf 0) { parent-_bf 0; subL-_bf 0; subLR-_bf 0; } else if (bf 1) { parent-_bf 0; subL-_bf -1; subLR-_bf 0; } else if (bf -1) { parent-_bf 1; subL-_bf 0; subLR-_bf 0; } else { assert(0); } }这个时候就能根据parent和cur的_bf值判断怎么旋了。旋完之后可以直接break跳出平衡因子的调节。4. AVLTree的测试完成了以上代码后使用{16, 3, 7, 11, 9, 26, 18, 14, 15} {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}两组测试用例来测试代码。先实现中序走一遍。但是中序只能保证是一个二叉搜索树。还要判断其是不是平衡搜索树。再实现一个找高度的函数或者均可但是切忌写成递归里套了递归时间复杂度会大很多。这一点在之前的博客中有过详细讲解。利用_Height函数实现IsBalanceTree函数bool _IsBalanceTree(Node* root) { if (root nullptr) return true;//空树也算AVLTree //计算节点高度差 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; if (abs(diff) 2) { cout 结构错误有高度差大于1的节点 endl; return false; } if (diff ! root-_bf) { cout 平衡因子调节错误 endl; return false; } //并且保证所有的子树都满足这个条件。 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }调试技巧如果发现有错用编译器cout来找报出错打断点不一定要用编译器的条件断点可以自己直接写。第一组通过了。第二组利用上述调试技巧打断点。发现是6的平衡因子有问题那么就在插入6时打下断点开始观察是如何出错的。空语句不能打断点所以我们定义一个变量语句来方便打断点然后顺利找到是RotateRL时调节平衡因子的问题。bf1时parent的值应该是-1AVLTree test2:由于C语言库函数的设计只能有32468个随机数。所以希望产生N个随机数时最好加一个其他数字。5. 小结AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。比如插入时最多旋转两次双旋但是erase时可能需要旋转很多次。
)
