💪 今日博客励志语录：
路在脚下延伸时，不必追问终点何在。你迈出的每一步，都在重新定义世界的边界
★★★ 本文前置知识：
二叉搜索树
引入
那么在之前的学习中，我们接触了二叉搜索树，我们知道二叉搜索树这个结构不仅能够存储数据，其最大的作用是能够高效的查找数据，那么查找的次数就取决于二叉搜索树的高度，但是一旦遇到极端情况，比如该二叉搜索树中存储的是一个单调递增或者递减的序列，那么此时二叉搜索树会退化成类似于链表的形态，时间复杂度就会达到o(N)这个级别
所以我们在维护一个二叉搜索树的时候，我们不能单单仅仅满足二叉搜索树的左小右大的性质，因为该二叉搜索树中存储的数据虽然不一定像刚才举的那个例子那样的极端，但是如果我们只是单单维护二叉搜索树的左小右大的性质，那么随着我们往二叉搜索树中不断插入新的节点，二叉搜索树的深度会逐渐增大，意味着查找的次数会增加，导致付出一定的时间代价，所以我们现在期望的就是，在满足二叉搜索树的左小右大的前提下，能够尽可能的调整或者压缩二叉搜索树的高度，从而维持二叉搜索树的一个高效的查找效率，而今天我要讲的AVL树，那么就是在二叉树的基础上，对其结构进行了优化与调整，在满足了二叉搜索树的前提下，尽可能的压缩了二叉搜索树的高度
AVL树
那么AVL树又称平衡二叉树，之所以给平衡二叉树取名叫AVL树，其实是为了纪念研究出这个较为复杂的数据结构的两个俄国的数学家，分别取了各自名字的首字母得到了AVL，而AVL树之所以复杂，就在于上文说的AVL树在普通的二叉搜索树身上做的改进：也就是压缩二叉搜索树高度的算法，那么这里我会在后文详细讲述
那么既然叫做平衡二叉树，在具体谈这里AVL树中所谓的平衡的概念之前，我们先来谈一下现实生活中的平衡，那么一提到现实生活中的平衡，那么天平这个例子可以作为代表，那么我们知道天平的左右两侧可以用来放物品或者砝码，那么天平如果要平衡，意味着天平左右两侧的放的物品的重量要相等，如果左侧或者右侧的重量更大，此时这个天平就会不平衡
天平其实类似于这里的二叉搜索树，天平的左右两侧其实代表着二叉搜索树的左右子树，天平的平衡意味着天平的左右两侧的重量相等，而二叉搜索树的平衡则意味着根节点的左右两侧的子树的高度相等
但是事实上，这里AVL树对平衡的要求做了一定的宽松，这里我就引出AVL树的性质：根节点的左右子树的高度不超过1，并且其左右子树也递归满足该条件
而这里AVL树要求的平衡，并不是完美的平衡，也就是左右子树的高度一样，那么要达到这种所谓的完美的平衡，也就是左右子树的高度一样，并且对于左子树和右子树来说，其也得递归满足其左右子树的高度一样，
要到这种完美的平衡，其实就只有一种情况，那么就是满二叉树，在满二叉树的所有节点中，其节点分为两类，第一类则是节点都有左右孩子，第二类则是位于最后一层没有左右孩子的叶子节点
而如果该树不是满二叉树，那么意味着一定有一层的节点不满，那么有一层的节点不满，那么意味着左子树和右子树一定有高度差，所以我们能够知道，如果二叉搜索树不是严格的满二叉树，那么其是无法做到该二叉搜索树每一个局部都是满足完美的平衡
而我们插入最终得到的二叉搜索树，那么其为满二叉搜索树的概率很低，所以这就是为什么AVL树的设计者选择将平衡的条件放宽，也就是根节点的左右子树高度差不超过1，并且其左右子树也递归的满足，事实上，只要一个二叉搜索树满足了这个性质，那么左右子树的高度不超过1，我们可以想象到这里的二叉搜索树整个的形态以及分布已经很均匀了，其形态其实趋近于一颗完全二叉树，所以AVL树的高度近似为logN，不管你插入的情况有多么极端，那么AVL树都能将高度维持到logN，从而优化了时间复杂度
而看到这里，那么有的读者可能会有一个疑惑，那么既然这里AVL树将平衡的条件放宽，也就是左右子树高度差为1，也可以算作平衡，那么为什么不把条件宽松到左右子树高度差为2或者为3等等也视作平衡了，那么要回答这个问题，那么就得和后面调整AVL树的操作，也就是旋转有关，因为只要左右子树的高度超过了1，也就是左右子树的高度差达到了2，那么我们就会立马旋转，那么一旦旋转完成之后，那么整个局部的二叉搜索树就达到平衡，所以有了旋转这个操作，我们左右子树的高度根本不会超过2，所以这里就没必要将平衡的条件在进行进一步的宽松，那么接下来的内容，我会着重介绍AVL树的插入以及背后涉及到的旋转，那么先讲原理，后面会根据原理来写代码模拟实现AVL树
原理
平衡因子
那么我们知道在插入一个新节点之前，那么该二叉树已经是一棵平衡二叉树，那么意味着其根节点的左右子树的高度差不超过1，并且左右子树也递归的满足该性质，
但是我们插入一个新的节点可能会破坏平衡二叉树的性质，也就是让左右子树之间的高度差超过1，那么现在就有一个问题，那么就是我们如何知道新插入的节点是否会破坏该该平衡二叉树的性质，难道我们插入完成后，要深度优先遍历来计算出根节点的左右子树的高度，看其高度差是否超过1，而二叉树是一个递归的结构，那么其左右子树也可以视作由根节点和左子树和右子树三部分构成，那么接下来意味着我们要计算出每一个局部的二叉搜索树的左右子树的高度差，如果每一个局部的二叉搜索树的左右子树的高度差不超过1，那么意味着该新插入的节点不会破坏性质
但是我们肯定不会这么做，那么这种方式太暴力，依次不断重新往下遍历二叉搜索树，来计算左右子树的高度差，所以这里AVL树引入了一个平衡因子，那么AVL树中的每一个节点都具有一个平衡因子
所谓的平衡因子其实就是一个标记，那么每一个节点的平衡因子的值就是其右子树的高度减去左子树的高度，而根据平衡二叉树的性质，也就是左右子树的高度不超过1，那么我们知道平衡二叉树中的每一个节点的平衡因子的值只有3种，分别是0，1，-1
那么如果平衡因子是0，那么平衡因子的计算公式是右子树高度减去左子树高度，那么如果其为0，意味着左子树和右子树高度相等，如果其为1，那么意味着右子树比左子树高1，如果为-1，那么意味着左子树比右子树高1
所以当我们插入一个新的节点的时候，那么该新插入的节点是属于某个局部的平衡二叉树中的左子树或者右子树，那么一旦插入，那么一定会让该局部的平衡二叉树中的一侧的子树高度加一，那么如果它插入在左子树中，那么让左子树的高度加一，那么此时导致其根节点的平衡因子的值会减一，而如果插入到右子树中，那么会导致右子树的高度加一，那么会让根节点的平衡因子的值加一
那么一旦平衡因子的绝对值为2，也就是平衡因子的值为-2或者2，那么意味着左右两侧的子树的高度差超过了1，那么意味着该局部的二叉搜索树此时不平衡，那么不平衡就需要调整，那么调整的方式就是旋转
而我们知道二叉树是一个递归的结构，那么其是由根节点和左右子树三部分构成，那么我们知道如果当前根节点的平衡因子如果为2或者-2，那么意味着当前根节点及其左右子树所组成的局部的二叉搜索树是不平衡的，但其他局部都是平衡的，满足左右子树的高度差是不超过1，那么如果我们能够让该根节点以及其左右子树所组成的二叉搜索达到平衡，那么意味着整个二叉搜索树就能够达到平衡，二叉树中不平衡的局部二叉树就好比肿瘤，那么这个不平衡的局部的二叉树就是寄生在这整棵二叉树的一个肿瘤，那么我们就得做手术将其清理，在这里就是将其调整至平衡，那么调整的方式就是旋转
旋转
左单旋
那么我们知道不平衡意味着根节点的左右两侧的子树超过了1，也就意味要么左子树的高度比右子树的高度高2或者右子树的高度比左子树的高度高2
如果左子树的高度比右子树的高度高2，那么就得右旋，那么右子树的高度比左子树的高度高2，那么就得左旋，那么在讲解左旋和右旋的具体原理之前，那么我们还是引入一个生活场景来理解，还是上文讲的天平的例子
那么这里的局部的二叉搜索树不平衡，可能是由于左子树过高，或者右子树过高导致的，那么就如同天平的左侧或者右侧过重，那么这里假设这里的天平的左侧过重，那么这时候我们如何调节使得天平达到平衡呢？那么我们可以取走天平左侧的一个砝码，让天平左侧减重，或者往天平右侧增加一个砝码，让天平右侧增重，从而让天平达到平衡
那么这里的旋转的道理其实类似于刚才调节天平的平衡，那么如果右子树的高度大于左子树，也就是高度差超过了1，类似于天平的右侧更重，那么这里我们就可以左旋
那么这里理解旋转的关键一定得借助图像去理解，那么这里假设有一个局部的二叉搜索树，其根节点A，那么其右孩子节点为B，而右孩子B的左子树为C，右孩子B的右子树为D，然后根节点的左子树为E，那么这里我建了一个抽象的模型，那么这个抽象的模型就能涵盖这一类的所有情况
那么在插入之前，那么该局部的二叉搜索树一定是平衡的，那么这里插入的新节点使得该局部的二叉树不平衡，假设这里的局部的二叉树的右子树整体的高度比左子树整体的高度高1，并且插入之前A的左子树的整体的高度为h，A的右子树的整体的高度为h+1
那么既然这里右子树整体的高度为h+1，那么这里对于右孩子B的左右子树来说，那么其高度都为h，那么B作为根节点的整体子树的高度才能为h+1，那么这里插入在B的右子树D中，那么这里使得B的右子树D的高度加一，此时原本B的左子树E高为h，那么此时插入新的节点之后，使得B的右子树的高度为h+1，那么此时我们可以来计算B和其左右子树组成的新的子树的整体高度
那么计算整体的子树的高度H的公式则是：H=1+max（H(左子树)+H(右子树)），所以这里B和其左右子树组成的新的左子树的高度H为：1+max（h+1，h）=h+2
那么此时新的子树的高度为h+2，那么左子树的高度为h，那么此时右侧比左侧的子树高2，导致不平衡
那么此时我们发现右侧比左侧高的高度为2，就好比天平右侧的重量比左侧的重量多重2克，那么此时如何达到平衡呢，那么我们通过旋转：
让此时根节点的右孩子，也就是B作为新的根节点，而原本的根节点A以及其左子树作为B的右子树，然后将B原本的高度为h的左子树给了A，作为了A的左子树，由于一个分支只能指向一个节点，所以这里就将B的右子树交给A
那么我们在仔细看这个过程，证明其是否正确，那么在证明是否平衡之前，我们得先证明其调整过后是否还是一棵二叉搜索树，那么如果其调整过后连二叉搜索树都不是，那么证明其平衡也没有意义，那么我们知道在调整之前，那么该局部的这棵树是一颗二叉搜索树，其满足左小右大，那么此时由于B位与根节点的右分支，那么意味着包括b在内以及其左右子树的所有节点，都大于根节点以及根节点的左子树中的所有的节点
那么如果我们将根节点和其右子树中的节点作为B的左子树，那么我们此时观察发现，此时还是满足左小右大的一个性质，因为B作为了新的根节点，那么B的右子树没变，那么肯定是大于节点B的，而此时根节点和其左子树作为了B的左子树一部分，那么其一定小于根节点B，而这里我们将B的左子树交给了A，作为其右子树，那么由于B的左子树原本属于A的右侧，那么其一定也大于根节点，那么这里放到A，作为其右子树，此时由A和其左右子树组成的局部的二叉树也满足二叉搜索树
所以这里我们能够证明调整过后的树是确实是一个二叉搜索树，那么这里我们再来证明调整过后的二叉搜索树是否平衡，那么这里我们就得计算新调整后的左右子树的高度
那么先来计算新的右子树的高度，那么新的右子树就为h+1，而左子树的高度则是1+max(h,h)=h+1，那么此时左右子树的高度都为h+1,那么整个二叉树是平衡的，并且A节点和其左右子树组成的局部的二叉搜索树，那么其左子树的高度为h，右子树的高度为h，其也平衡，并且都是完美的平衡，所以这里能够证明平衡性
那么刚才说的这个过程，我们之所以叫起左旋，那么其过程就非常像将右孩子B为支点然后来旋转根节点和其左子树到其左侧，作为其左子树
而这里我们可以来理解左旋的设计思想与巧妙之处，那么之前我们计算插入之前的左右子树的高度,那么左子树的高度为h，而右子树的高度为1+max(h,h+1)=h+2,而这公式里加的第一个1对应的就是根节点的右孩子B，而这里加的第二个1对应的就是新插入的节点，而这里我们将根节点的右孩子作为新的二叉搜索树的根节点，相当于减少了右子树的高度，相等于减去了一个1：1+max(h+1,h)-1=h+1,而又让根节点作为了左子树的一部分，那么相当于给左子树增加了一个单位的高度，然后把B的右子树给了A，作为其左子树，那么原本的左子树的高度为：h，此时新的左子树的高度为：1+max(h,h)=h+1
那么这里旋转背后的涉及的核心思想就可以借助天平理解，那么这里是天平右侧比左侧多重两克，那么右侧重h+2，左侧重h，那么每一个节点就如同这里的砝码，质量为一克，那么这里就是左旋就是在右侧拿走一个一克的砝码，那么这个砝码就是右孩子B，然后再给左侧加一克砝码，那么这个砝码就是根节点A，然后双方的重量都为h+1
右单旋
那么这里右单旋的场景，我们还是可以用刚才的那个模型来描述右单旋中的所有的情况，那么这里还是有一个局部的平衡的二叉搜索树，那么其根节点为A，左孩子为B，那么左孩子B的左子树为C，左孩子的右子树为D，A节点的右子树为E，那么在插入之前，那么该局部的二叉树的右子树的高度为h，左子树整体的高度为h+1，那么其中B的左子树c和右子树D的高度为h，那么这里假设我们往B的左子树C中新插入一个节点
那么此时新插入节点之后，那么左子树的高度H：1+max(h,h+1)=h+2，而右子树为h，那么此时二叉搜索树不平衡，那么这里的场景和刚才左单旋的场景其实是一个镜像对称的场景
那么处理的方式和思想就是和之前类似了，那么这里相当于天平的左侧重h+2，右侧重h，那么这里我们就得拿走左侧的重一克的砝码，也就是根节点的左孩子B，让其去成为新的根节点，然后再从右侧添加一克的砝码，也就是让原本的根节点作为新的右子树的一部分，从而达到平衡
所以这里右单旋的过程，就是将左孩子B作为新的根节点，然后左孩子B的左子树C交给原本的根节点A，然后根节点A作为B的右孩子，从而调整达到平衡
那么这里证明其为二叉搜索树以及其平衡性的过程，那么这里就不再过多赘述了，和上文证明左单旋的过程几乎是一样的，那么经过右单旋之后，那么这里整体的局部二叉搜索树也是达到了完美的平衡，也就是左右子树的高度都是相等的，并且其左右子树也是完美的平衡
右左双旋
那么在前面介绍了左单旋和右单旋的例子后，那么这里我们知道了如果一个局部二叉搜索树不平衡且如果左子树偏高，那么就右旋，那么右子树高，那么就左旋
那么这里是不是只要左子树高，那么就一律的右旋，那么右子树高，那么就一律的左旋呢？
所以接下来我要再来引入一个模型，那么还是一个局部的二叉搜索树，其根节点为A，那么其右孩子为B，那么右孩子B的右子树为C，那么这里我们将模型更细化了一点，方便理解之后的插入以及旋转，那么这里B的左孩子为D，那么D的左右子树分别为E和F，那么根节点A的左子树为K
那么之前的插入是在B的右子树中，也就是C中插入一个新的节点，但这一次我们新插入的节点不在B的右子树中，而是在B的左子树中，也就是D的左子树E或者D的右子树F中插入一个节点，那么此时假设根节点a的左子树整体的高度为h，而右子树整体的高度为h+1，那么b的右子树的高度为就为h，并且D的左右子树的高度都是h-1
那么这里假设我们插入到D为根节点的左子树E中，那么此时也满足插入在B的左子树中，那么我们来计算d为根节点的子树的整体的高度H1：
H1=1+max(h-1+1,h-1)=h+1
接着我们再来计算b为根节点的整体子树的高度H2：
H2=1+max(H1,h)=1+max(h+1,h)=h+2
而a的左子树的整体的高度是h，那么这里我们知道当新插入的节点在右孩子b的左子树中，那么也会造成右侧比左侧高2，和之前插入到右孩子b的右子树是一个效果，那么这里我们能否再仅仅左单旋，来达到平衡呢？
那么这里我们可以尝试一下，看看左单旋是一个什么效果，那么这里左单旋就是将右孩子b作为根节点，然后原本的根节点a作为b的左孩子，然后将b的左子树交给了a，作为a的右子树，那么此时我们来计算这里新的局部二叉搜索树的左右子树的高度
那么此时旋转过后的右子树的高度就是b原本的右子树的高度，因为b的高位h+1的左子树交给了原本的根节点a，作为其右子树，所以这里左旋后的右子树的高度为h
而此时我们再来计算左子树的高度：H=1+max(h,h+1)=h+2
那么这里此时左树的高度变为了h+2,那么我们发现这里仅仅左单旋，结果反而颠倒了，也就是左侧的高度比右侧高2，没有成功达到平衡，那么我们也可以尝试分析一下导致这种情况出现的原因，那么我们知道右子树就像天平的右侧，初始的时候已经比左侧重了一克，但是还可以接受，而此时新插入的节点就相当于给天平的右侧在放入了一克的砝码
而此时进行左单旋，就好给左侧加了一克的砝码，也就是根节点a，那么还从右侧拿走了一克的砝码也就是新插入的节点，给了左侧，也就是从右侧本身就拿走了两克的砝码，而给左侧又添加了2个砝码，所以会导致左侧此时反而比右侧高2
所以这里导致高度反转的核心原因就是这个新插入的节点会给左侧的子树，所以这里就得在左旋之前，先对b所构成的局部的二叉搜索树右旋，降低其左子树的高度
那么右旋会让此时由b作为的根节点的局部的二叉搜索树的左树高度降低，右侧高度增加，这里左旋之后，那么原本给a的右子树的会多给一个新插入的节点，而右旋让b的左子树高度降低了一个单位的高度，相当于就抵消新增的节点
右旋之后，此时再对a整体左旋即可，从而让左侧只会增加旋转下来的根节点a
那么我们也可以来证明这种方式的平衡性，那么右左双旋得到的新的二叉搜索树的左子树的高度则是H1=1+max(h,h)=h+1
而右子树的高度为H2=1+max(h-1,h)=h+1，那么此时完美平衡
但是我们再来验证下一层的局部的二叉搜索树的平衡性，首先则是a作为根节点的局部的二叉搜索树，那么我们可以计算器左右子树的高度，那么其左子树的高度为H1=h,右子树的高度为h-1+1=h，那么此时a为根节点的局部的二叉搜索树是完美的平衡的，那么我们再来看右边以b为根节点的局部二叉搜索树，那么其左子树的高度为H1=h-1，右子树的高度为h，那么这里对于b为根节点的局部二叉树来说，那么b的平衡因子是1，右子树比左子树高1
而这里之所以将这里的模型给细化，也就是将根节点a的左孩子b的左子树细化为由根节点d和左子树e和右子树f组成，那么就是因为这里新插入的节点可能位于e，也可能位于f，那么位于e或者f会影响下一层的局部的二叉搜索树的平衡因子，那么刚才插入的位置是d的左子树e中，那么导致右左旋转后的b作为根节点的局部二叉搜索树的平衡因子是1，而之前仅仅左单旋的时候，每一个局部都是完美平衡，也就是每一个节点的平衡因子都是0，但是在该场景下则不是每一节点的平衡因子都是0
而这里如果我们插入到d的右子树也就是f，那么同样还是先右旋转，那么对于b作为根节点的局部二叉树来说，会让d成为根节点，然后b作为d的右孩子，并且接收d的右子树f，然后对a作为根节点的整个局部二叉搜索树整体左旋，此时d作为根节点，那么a作为其左孩子，接收d的左子树，那么此时对于这种情况，我们还是先计算右左双旋之后，新的局部二叉树的左子树整体的高度和右子树的整体的高度
那么d的左子树整体的高度则为：H1=1+max(h,h-1)=h+1
而右子树整体的高度则为：H2=1+max(h-1+1,h)=h+1
那么此时右左双旋后的整体左右子树的高度仍然是相等，那么这里我们再来看下一层的局部的二叉搜索树的平衡性，那么先看a作为根节点的局部二叉搜索树的平衡性，那么其左子树的高度H1=h，右子树的H2=h-1,而b作为根节点的局部二叉搜索树的平衡性，那么其左子树为H1=h-1+1=h，右子树H2=h，那么b的平衡因子是0，那么这里插入在d的右子树f中，那么下一层的局部二叉树的平衡性和之前插入在d的左子树的平衡性是不同的
但是此时还有第三种情况，那么就是这里插入之前，b的左子树为空，那么意味着新插入的节点就是b的左孩子，那么我们知道在插入之前，那么该二叉搜索树一定是平衡二叉树，那么这里b没有左子树，并且插入了新节点之后，要让此时a的右子树的整体的高度要比左侧的整体的高度高2，那么此时就只有一种情况，那么就是这里的根节点a的左子树为空以及根节点的左孩子b的左右子树都为空才能满足，然后此时在b的左子树插入了一个节点，还是一样进行右左双旋，如果仅仅左单旋，那么旋完之后的结果还是左边比右边高2，那么读者这里可以自己直接画图来证明，那么知道了右左双旋之后，我们这里着重观察，右左双旋后的每一个节点的平衡因子，那么我们可以发现在这个情况下，那么每一个节点的平衡因子都是0
所以这里右左双旋，有两个难点，第一就是理解右左双旋的意义以及右左双旋为什么正确，其次就是确定右左双旋后的新的二叉搜索树的平衡因子
那么这里其实我们核心就是确认三个节点的平衡因子，分别是根节点a，以及根节点a的右孩子b以及b的左孩子d，这三个节点的平衡因子
因为我们右左双旋会改变这三个节点的左右子树，那么其他子树内部没有旋转，那么我们就不用关心其他局部的节点的平衡因子，因为其他局部的左右子树没有变，那么其局部的根节点的平衡因子也不会改变
并且这里旋转后的局部二叉搜索树的根节点，也就是d，不论是这三种情况中的哪一种，其平衡因子都是0
所以这里右左双旋就可以分为三种情况，分别是插入在d的左子树e以及d的右子树f和b的左右子树都为空，插入在b的左子树中
那么这三种情况下，就要注意a和b和d的平衡因子
左右双旋
那么知道了左单旋，那么我们就能够理解右单旋，那么知道了右左双旋，那么同样我们就能够理解左右双旋，那么左右双旋的场景和右左双旋一样，是镜像对称的，只不过这里的模型变成了：根节点a，根节点的左孩子为b，那么左孩子的左子树为c，左孩子的右孩子为d，那么d的左右子树分别为e和f，根节点的右子树k
那么假设这里根节点左子树的整体高度为h+1，那么右子树高度为h，那么此时d的左右子树的高度为h-1，那么如果此时插入新节点到b的右子树中，那么此时会让左侧的高度比右侧高2，但是这里不能仅仅采取右单旋，那么采取右单旋，上文讲解右左双旋的时候，我已经证明过仅仅采取左单旋的效果，这里的证明方式同样，这里就不写证明过程，那么如果只采取右单旋，结果还是会颠倒，也就是旋完之后，右边比左边高2
所以这里就得采取左右双旋，那么先对b作为根节点的二叉搜索树整体左旋，旋完之后，在对a作为根节点的二叉搜索树整体右旋，那么这里旋转的原理和最终平衡性的证明和上文一样，这里同样得分为三类情况：
分别是插入在d的左子树e以及插入在d的右子树f和b的左右子树为空，插入在b的右子树中，那么这三类情况下，只需要关注根节点a和以及其左孩子b和b的右孩子d这三个节点的平衡因子，那么我们可以画图加计算得到这三个节点在这三种情况下的平衡因子，那么计算过程就省略了，按照上文的方式计算即可，那么这里我直接给出结果
那么第一种情况也就是插入在d的右子树f中，那么最终左右双旋之后，那么此时新的根节点d的平衡因子为0，那么a的平衡因子为0，b的平衡因子为-1
第二种情况插入在d的左子树e中，那么左右双旋之后，新的根节点d的平衡因子为0，a的平衡因子为1，b的平衡因子为0
第三种情况，那么d和a和b的平衡因子都为0
并且这里我们也可以确认：左右双旋后的局部二叉搜索树的根节点，也就是d，不论是这三种情况中的哪一种，其平衡因子都是0
总结
那么知道了这几个旋转的原理之后，那么读者可能现在唯一的疑惑就是如何判断什么时候用左单旋，什么时候用右单旋，以及左右双旋，那么这里如果新插入的节点如果是在根节点的左孩子的左子树中，也就是LL型，那么就是右单旋，而如果是插入在根节点的左孩子的右子树中，那么就是LR型，就是左右双旋
同理如果插入在根节点的右孩子的右子树中，此时是RR型，那么就是左单旋，那么如果插入在右孩子的左子树中，此时是RL型，就是右左双旋
其实我认为，只要读者理解了上文所讲的原理，其实我们没必要刻意去记什么形态对应什么旋转，理解了原理之后，其实我们脑子中就能想象出一副动态的抽象图出来，那么我们立刻就可以知道此时应该采取什么旋转才是正确的
模拟实现
那么上文我们已经知道了AVL树最为重要的操作，也就是旋转，那么接下来我们就可以尝试自己模拟实现AVL树，那么首先我们得准备一个AVL树中的节点，也就是AVLTreeNode模板类，那么注意这里的成员变量以及构造函数都得用public来修饰，因为我们会在后面的AVLTree模版类中定义一个指向根节点的指针，并且其成员函数中会涉及到直接修改节点的指针，所以为了能在类外访问，这里我们要将AVLTreeNode中的成员变量都设置为public，而我们只需要在AVLTree模板类中，将AVLTreeNode的typedef的别名以及指向根节点的指针的成员变量私有即可
那么这里AVLTreeNode首先准备一个pair元组，那么因为我们的AVL树是一个key val模型，所以这里的数据域就得采取的元组来实现，并且模版参数得有两个，然后还得定义指向左孩子以及右孩子的两个指针，分别为left和right，以及一个指向父节点的指针parent，而这个parent指针的作用会在后面的insert函数讲解，最后则是一个int类型的平衡因子，那么由于每次新插入的节点，其没有左右孩子，所以这里的AVLTreeNode的构造函数就是将平衡因子初始化为0，然后指针初始化为nullptr
而这里AVLtreeNode也支持了接收pair类型的参数的构造函数来初始化里面的元组
template<typename key, typename val>
class AVLTreeNode
{
public:
std::pair<key, val> _pair;
AVLTreeNode<key, val>* left;
AVLTreeNode<key, val>* right;
AVLTreeNode<key, val>* parent;
int _bf;
AVLTreeNode()
:_pair(std::make_pair(key(), val()))
, left(nullptr)
, right(nullptr)
, parent(nullptr)
, _bf(0)
{
}
AVLTreeNode(const std::pair<key, val>& p)
:_pair(p)
, left(nullptr)
, right(nullptr)
, parent(nullptr)
, _bf(0)
{
}
};
template<typename key, typename val>
class AVLTree
{
private:
typedef AVLTreeNode<key,val> Node;
Node* root;
...........
};
构造函数
那么接下里就是AVLTree的构造函数了，那么这里的构造函数有无参的以及带参的，那么无参的就是构建一颗空树，那么根节点为nullptr，而带参的就是给根节点进行初始化，那么会接收一个pair类型的参数
AVLTree()
:root(nullptr)
{
}
AVLTree(const std::pair<key, val>& p)
:root(new Node(p))
{
}
insert函数
那么接下来就是insert函数的实现，那么insert函数的实现思路其实可以分为两个大的步骤，那么第一步就是我们借助二叉搜索树的左小右大的性质，然后找到新插入节点的位置以及其父节点,然后创建节点，并且与父节点连接，这步和实现二叉搜索树的查找几乎是一样的
void Insert(const std::pair<key, val>& p)
{
if (root == nullptr)
{
root = new Node(p);
return;
}
Node* cur = root;
Node* parent = nullptr;
while (cur)
{
if (p.first < cur->_pair.first)
{
parent = cur;
cur = cur->left;
}
else if (p.first > cur->_pair.first)
{
parent = cur;
cur = cur->right;
}
else
{
return;
}
}
cur = new Node(p);
if (cur->_pair.first < parent->_pair.first)
{
parent->left = cur;
cur->parent = parent;
}
else
{
parent->right = cur;
cur->parent = parent;
}
.................
}
创建完节点后，我们就得检查新插入的节点是否会破坏二叉搜索树的性质，那么这里就得访问父节点的平衡因子，那么如果新插入的节点是在父节点的右子树中，导致父节点的右子树增高，那么我们会让父节点的平衡因子加加，而如果新插入的节点是在父节点的左子树中，那么相等于左子树高度增加，那么父节点的平衡因子就得减减，修改完父节点的平衡因子，接下来就是判断父节点的平衡因子，那么如果父节点的平衡因子为0，那么意味着此时父节点以及其左右子树构成的局部的二叉搜索树已经达到完美的平衡，那么由于插入之前，其他各个局部都是平衡，而当前局部也满足平衡，就没必要再往上检查了
但是如果父节点的平衡因子是1或者-1，那么意味着父节点的左子树或者右子树增高，那么根据子树的计算公式：H=1+max(H(左子树)+H(右子树))，那么这里H(左子树)或者H(右子树)会增加一个单位的高度，会导致此时父节点为根节点的局部的子树也整体增加一个单位的高度，那么就要判断父节点的父节点，也就是祖先节点是否平衡，因为祖先节点的左侧或者右侧子树的高度增加，如果原本这个增高的子树的高度就比另一个子树的高一个单位，而此时高的子树再增加一个单位的高度，此就会导致这里的局部的二叉搜索树不平衡，那么这里我们可以用一个循环，定义一个cur和parent指针，分别指向当前节点和其父节点，那么如果父节点的平衡因子是1或者-1，那么将parent给cur，由于AVL树中的节点是一个三叉链，有指向父节点的指针，所以parent可以移动到其父节点的父节点，也就是祖先节点，然后继续根据cur在parent的哪个分支，来加加parent或者减减parent的平衡因子，然后重复这个过程，那么会沿途检查祖先节点直到达到根节点，所以这里的while循环的结束条件当parent等于nullptr就结束，因为根节点的parent指针是nullptr
而如果平衡因子是2或者-2，那么意味着此时parent指向的节点，其作为根节点的局部的二叉搜索树是不平衡的，那么就要旋转，那么经过上文的讲解，那么这里我们要对旋转进行判断，如果是LL型就右单旋，如果是LR型就左右双旋，那么这里判断就是借助cur以及parent的平衡因子来共同判断采取哪种旋转方式
那么经过上文的讲解，不论你是采取单旋还是双旋，那么整个局部二叉树都会被调整至完美的平衡，那么该局部已经达到平衡，而其他局部也是平衡的，那么就必要再往上遍历判断了，直接break退出即可
while (parent)
{
if (cur == parent->left)
{
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)
{
if (parent->_bf == -2)
{
if (cur->_bf == 1)
{
RotationLR(parent);
}
else
{
RotationR(parent);
}
}
else
{
if (cur->_bf == -1)
{
RotationRL(parent);
}
else
{
RotationL(parent);
}
}
break;
}
else
{
assert(false);
}
}
}
那么这里注意这里的AVL树中的平衡因子的绝对值只能是0或者1或者2，不可能大于2，因为这里的平衡因子只能从0依次递增到2，那么一旦某个节点的平衡因子的绝对值达到了2，那么我们就会立马旋转调整使其平衡，让调整后的整体的局部二叉树的根节点的平衡因子变为0，所以这里如果AVL树出现了绝对值大于2的平衡因子的节点比如3，那么该节点的出现那么意味着前面一定还有有平衡因子的绝对值为的2节点，但是一旦出现绝对值为2，我们立马会调整，所以这里不可能出现平衡因子为3的节点，但是这里读者可以看到这里我while循环的最后一个条件语句的分支，写了一个断言，那么进入到这个条件语句分支，以为则出现了平衡因子的绝对值大于2的节点，那么程序肯就会被assert终止
但是理论上如果我们的代码逻辑是正确的，那么是不可能执行这个断言语句的，所以一旦执行了这个断言，那么说明我们的旋转或者插入的代码的逻辑肯定有错
void Insert(const std::pair<key, val>& p)
{
if (root == nullptr)
{
root = new Node(p);
return;
}
Node* cur = root;
Node* parent = nullptr;
while (cur)
{
if (p.first < cur->_pair.first)
{
parent = cur;
cur = cur->left;
}
else if (p.first > cur->_pair.first)
{
parent = cur;
cur = cur->right;
}
else
{
return;
}
}
cur = new Node(p);
if (cur->_pair.first < parent->_pair.first)
{
parent->left = cur;
cur->parent = parent;
}
else
{
parent->right = cur;
cur->parent = parent;
}
while (parent)
{
if (cur == parent->left)
{
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)
{
if (parent->_bf == -2)
{
if (cur->_bf == 1)
{
RotationLR(parent);
}
else
{
RotationR(parent);
}
}
else
{
if (cur->_bf == -1)
{
RotationRL(parent);
}
else
{
RotationL(parent);
}
}
break;
}
else
{
assert(false);
}
}
那么接下来，知道了insert函数的实现之后，我们再来看旋转的函数代码如何实现
左单旋RotationL函数
那么左单旋针对的就是RR类型的场景，也就是新插入的节点在根节点的右孩子的右子树当中，而该函数会接收一个指向不平衡的局部二叉树的根节点的指针，而上文说了左单旋的过程，就是将根节点作为其右孩子的左孩子，那么根节点的右孩子假设为cur，那么将根节点作为右孩子的左孩子的代码就是：
cur->left=parent;
那么这里左孩子成为了根节点的父亲，那么这里还要修改parent的指向的父节点指针，那么在指向之前，那么我们还得保存parent的父节点指针，因为此时cur作为新的根节点，那么会连接原本的parent的父节点
Node* pparent=parent->parent;
parent->parent=parent;
这里还要将cur的左子树交给parent,作为其右子树：
Node* curleft=curleft;
parent->right=curleft;
那么这里还要修改左子树指向的根节点，但是这里左子树有可能为空，所以就需要判断一下
if (curleft)
curleft->parent = parent;
那么这里要注意的就是这里的parent可能是整棵树的根节点，那么如果parent是整棵树的根节点，那么此时cur经过旋转之后，就成为了整棵树的根节点，那么这里我们还得修改root成员变量让其指向cur，那么如果pparent为空，那么说明parent就是整棵树的根节点
curleft->parent = parent;
if (pparent)
{
if (pparent->left == parent)
{
pparent->left = cur;
}
else
{
pparent->right = cur;
}
}
else
{
root = cur;
}
parent->_bf = cur->_bf = 0;
}
最后就是修改平衡因子了，那么这里我们修改的节点只包括parent和cur这两个节点，因为这两个节点的子树有变动，而其余的节点的子树没有修改，而上文我们就证明过左单旋过后，那么此时parent和cur的平衡因子一定是0，所以这里直接修改
即可
void RotationL(Node* parent)
{
Node* cur = parent->right;
Node* curleft = cur->left;
Node* pparent = parent->parent;
parent->parent = cur;
parent->right = curleft;
cur->parent = pparent;
cur->left = parent;
if (curleft)
curleft->parent = parent;
if (pparent)
{
if (pparent->left == parent)
{
pparent->left = cur;
}
else
{
pparent->right = cur;
}
}
else
{
root = cur;
}
parent->_bf = cur->_bf = 0;
}
右单旋RotationR函数
那么这个右单旋函数其实和左单旋就是一个对称的情况，那么原理和实现思路和左单旋一模一样，所以这里我直接给出代码即可，不在过多叙述
void RotationR(Node* parent)
{
Node* cur = parent->left;
Node* curright = cur->right;
Node* pparent = parent->parent;
parent->parent = cur;
parent->left = curright;
cur->right = parent;
if (curright)
curright->parent = parent;
cur->parent = pparent;
if (pparent)
{
if (pparent->left == parent)
{
pparent->left = cur;
}
else
{
pparent->right = cur;
}
}
else
{
root = cur;
}
parent->_bf = cur->_bf = 0;
}
左右双旋函数RotationLR函数
那么这里左右双旋函数会接收一个指向不平衡的整体的局部二叉搜索树的根节点的指针，那么这里左右双旋其实可以看成两个过程，那么首先就是对parent的左孩子节点为根节点的局部二叉搜索树整体右旋，然后再对parent为根节点的整个局部的二叉搜索树左旋，那么前面已经实现好了RotationL和RotationR函数，那么这里我们直接复用写好的函数
Node* cur = parent->left;
RotationL(cur);
RotationR(parent);
那么旋转玩后，下一步就是更新平衡因子，而这里cur是根节点的左孩子，那么上文我们就说过这里有三种情况，分别是插入在cur的右孩子的左子树中以及cur的右孩子的右子树中，以及cur的右子树为空，然后插入新的节点
那么这三种情况其实可以利用cur的右孩子的平衡因子来判断，如果cur的右孩子的平衡因子为-1，说明插入到了cur的右孩子的左子树，反之为1，说明插入到了cur右孩子的右子树中，而如果其平衡因子为0，说明就是第三种情况，那么这三种情况下，最终parent以及cur和cur的右孩子的平衡因子的值是什么，上文也是说的很明白了，这里直接根据情况，修改对应的平衡因子即可
void RotationLR(Node* parent)
{
Node* cur = parent->left;
Node* curright = cur->right;
int bf = curright->_bf;
RotationL(cur);
RotationR(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = curright->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
}
右左双旋函数RotationRL函数
那么右左双旋就是左右双旋的对称，那么原理和实现思路和左右双旋一模一样，这里不在过多叙述，直接给出代码
void RotationRL(Node* parent)
{
Node* cur = parent->right;
Node* curleft = cur->left;
int bf = curleft->_bf;
RotationR(cur);
RotationL(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = curleft->_bf = 0;
}
else if (bf == -1)
{
curleft->_bf = 0;
cur->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
curleft->_bf = 0;
parent->_bf = -1;
cur->_bf = 0;
}
}
拷贝构造函数
那么这里拷贝构造函数，那么采取的就是前序遍历来拷贝，那么这里我额外定义了一个copy函数来实现这里的拷贝逻辑，那么这里对于AVL树来说，由于每一个节点是一个三叉链，那么最难办的就是指向父节点的指针，所以这里我们可以将copy函数的参数设置为指针的引用，那么引用就是指针的别名，那么其接收当前要拷贝的AVL树的根节点指针parent1和被拷贝的AVL树的指针parent2，那么如果当前parent2不为空，那么就给parent1开辟节点，那么由于parent1是父节点的左指针或者右指针的别名，那么这里直接开辟节点，相当于直接让父节点的左指针或者右指针指向新开辟的节点，所以不需要额外添加连接的逻辑，那么这就是引用的巧妙之处
void copy(Node* & parent1, Node* const& parent2)
{
if (parent2 == nullptr)
{
parent1 = nullptr;
return;
}
parent1 = new Node(parent2->_pair);
......................
}
那么接下来我们就在递归调用copy，先拷贝完其左子树在拷贝完其右子树，然后再回到当前函数，那么意味着左右子树都已拷贝成功，那么我们让parent的左指针指向的节点以及右指针指向的节点的parent指针指向自己，但是有可能左右子树为空，所以这里需要特判一下
AVLTree(const AVLTree<key,val>& p)
{
copy(root,p.root);
}
void copy(Node* & parent1, Node* const& parent2)
{
if (parent2 == nullptr)
{
parent1 = nullptr;
return;
}
parent1 = new Node(parent2->_pair);
copy(parent1->left, parent2->left);
copy(parent1->right, parent2->right);
if (parent1->left)
parent1->left->parent = parent1;
if (parent1->right)
parent1->right->parent = parent1;
}
检查当前二叉树是否平衡的Isbalanced函数
那么当我们创建并且插入完节点，得到了一个AVL树，那么我们得想办法验证得到的该AVL树是否真的平衡，这里验证我不可能打印AVL树的节点或者自己画图，那么万一节点很多，那么这个时间成本就太大了，所以这里我们可以定义一个函数来检查该AVL树是否平衡，那么检查AVL树是否平衡的核心思路就是检查其每一个局部是否满足性质，也就是左右子树的高度差不超过1，那么有的读者认为：那这简单，我直接深度优先遍历，检查所有节点的平衡因子的绝对值是否为0或者1，一旦不是0或者1，那么这里的AVL树是不平衡的，一旦所有节点的平衡因子结对之是0或者1，那么该AVL树就是正确的
但是这里我想说的是，这里可以检查平衡因子，但是它的说服力不高，就好比小时候，你爸妈检查你每个月怎么花的钱，那么你给你爸妈看你在自己的笔记本上记录的每个月的账单，但是你的爸妈肯定是不会相信你每个月的花费就是按照你账单记录的那样，所以爸妈采取的方式就是直接打开你微信的账单以及付款记录，这个才有说服力
那么如果我们的平衡因子的更新逻辑是错的，那么导致平衡因子错误，那么此时就无法以平衡因子作为依据，那么最有依据的，就是直接计算每一个局部的二叉树的左右子树的高度，然后得到高度差，如果当前局部的二叉搜索树的高度差不等于平衡因子，那么此时这个AVL树一定是不正确的，或者高度差大于了1，那么这里也是不正确的，那么我们再依次递归检查每一个局部的子树
int Hight(Node* parent)
{
if (parent == nullptr)
{
return 0;
}
return 1 + std::max(Hight(parent->left), Hight(parent->right));
}
bool isBalanced(Node* parent)
{
if (parent == nullptr)
{
return true;
}
int lefthight = Hight(parent->left);
int righthight = Hight(parent->right);
int hightdiff = righthight - lefthight;
if (hightdiff != parent->_bf)
{
return false;
}
if (abs(hightdiff) >= 2)
{
return false;
}
return isBalanced(parent->left) && isBalanced(parent->right);
}
析构函数
那么由于AVL树每一个节点都是动态开辟的，所以这里我们需要编写析构函数来释放资源，那么析构函数释放每一个节点的顺序采取的就是后序遍历，先释放左子树，在释放右子树，最后释放根节点
~AVLTree()
{
destroyTree(root);
}
void destroyTree(Node* parent)
{
if (parent == nullptr)
{
return;
}
destroyTree(parent->left);
destroyTree(parent->right);
delete parent;
}
源码
AVLTree.h:
#include<algorithm>
#include<iostream>
#include<cstdbool>
#include<cstdlib>
using std::cout;
using std::endl;
namespace wz
{
template<typename key, typename val>
class AVLTreeNode
{
public:
std::pair<key, val> _pair;
AVLTreeNode<key, val>* left;
AVLTreeNode<key, val>* right;
AVLTreeNode<key, val>* parent;
int _bf;
AVLTreeNode()
:_pair(std::make_pair(key(), val()))
, left(nullptr)
, right(nullptr)
, parent(nullptr)
, _bf(0)
{
}
AVLTreeNode(const std::pair<key, val>& p)
:_pair(p)
, left(nullptr)
, right(nullptr)
, parent(nullptr)
, _bf(0)
{
}
};
template<typename key, typename val>
class AVLTree
{
private:
typedef AVLTreeNode<key, val> Node;
Node* root;
void copy(Node* & parent1, Node* const& parent2)
{
if (parent2 == nullptr)
{
parent1 = nullptr;
return;
}
parent1 = new Node(parent2->_pair);
copy(parent1->left, parent2->left);
copy(parent1->right, parent2->right);
if (parent1->left)
parent1->left->parent = parent1;
if (parent1->right)
parent1->right->parent = parent1;
}
void Inorder(Node* _root)
{
if (_root == nullptr)
{
return;
}
Inorder(_root->left);
cout << "key: " << _root->_pair.first << " val:" << _root->_pair.second << " ";
Inorder(_root->right);
}
void destroyTree(Node* parent)
{
if (parent == nullptr)
{
return;
}
destroyTree(parent->left);
destroyTree(parent->right);
delete parent;
}
void RotationL(Node* parent)
{
Node* cur = parent->right;
Node* curleft = cur->left;
Node* pparent = parent->parent;
parent->parent = cur;
parent->right = curleft;
cur->parent = pparent;
cur->left = parent;
if (curleft)
curleft->parent = parent;
if (pparent)
{
if (pparent->left == parent)
{
pparent->left = cur;
}
else
{
pparent->right = cur;
}
}
else
{
root = cur;
}
parent->_bf = cur->_bf = 0;
}
void RotationR(Node* parent)
{
Node* cur = parent->left;
Node* curright = cur->right;
Node* pparent = parent->parent;
parent->parent = cur;
parent->left = curright;
cur->right = parent;
if (curright)
curright->parent = parent;
cur->parent = pparent;
if (pparent)
{
if (pparent->left == parent)
{
pparent->left = cur;
}
else
{
pparent->right = cur;
}
}
else
{
root = cur;
}
parent->_bf = cur->_bf = 0;
}
void RotationLR(Node* parent)
{
Node* cur = parent->left;
Node* curright = cur->right;
int bf = curright->_bf;
RotationL(cur);
RotationR(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = curright->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
}
void RotationRL(Node* parent)
{
Node* cur = parent->right;
Node* curleft = cur->left;
int bf = curleft->_bf;
RotationR(cur);
RotationL(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = curleft->_bf = 0;
}
else if (bf == -1)
{
curleft->_bf = 0;
cur->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
curleft->_bf = 0;
parent->_bf = -1;
cur->_bf = 0;
}
}
int Hight(Node* parent)
{
if (parent == nullptr)
{
return 0;
}
return 1 + std::max(Hight(parent->left), Hight(parent->right));
}
bool isBalanced(Node* parent)
{
if (parent == nullptr)
{
return true;
}
int lefthight = Hight(parent->left);
int righthight = Hight(parent->right);
int hightdiff = righthight - lefthight;
if (hightdiff != parent->_bf)
{
return false;
}
if (abs(hightdiff) >= 2)
{
return false;
}
return isBalanced(parent->left) && isBalanced(parent->right);
}
public:
AVLTree()
:root(nullptr)
{
}
AVLTree(const std::pair<key, val>& p)
:root(new Node(p))
{
}
AVLTree(const AVLTree<key, val>& p)
{
copy(root, p.root);
}
~AVLTree()
{
destroyTree(root);
}
void Insert(const std::pair<key, val>& p)
{
if (root == nullptr)
{
root = new Node(p);
return;
}
Node* cur = root;
Node* parent = nullptr;
while (cur)
{
if (p.first < cur->_pair.first)
{
parent = cur;
cur = cur->left;
}
else if (p.first > cur->_pair.first)
{
parent = cur;
cur = cur->right;
}
else
{
return;
}
}
cur = new Node(p);
if (cur->_pair.first < parent->_pair.first)
{
parent->left = cur;
cur->parent = parent;
}
else
{
parent->right = cur;
cur->parent = parent;
}
while (parent)
{
if (cur == parent->left)
{
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)
{
if (parent->_bf == -2)
{
if (cur->_bf == 1)
{
RotationLR(parent);
}
else
{
RotationR(parent);
}
}
else
{
if (cur->_bf == -1)
{
RotationRL(parent);
}
else
{
RotationL(parent);
}
}
break;
}
else
{
assert(false);
}
}
}
bool Isbalanced()
{
return isBalanced(root);
}
void inorder()
{
Inorder(root);
}
};
}
main.cpp:
#include<cassert>
#include <vector>
#include <queue>
#include"AVLTree.h"
using namespace std;
using namespace wz;
int main() {
// 测试1：左单旋（RR情况）
{
cout << "test1: RR - insert 10,20,30" << endl;
AVLTree<int, int> tree;
tree.Insert({ 10, 0 });
tree.Insert({ 20, 0 });
tree.Insert({ 30, 0 });
// 验证树结构
// 预期结构：
// 20
// / \\
// 10 30
assert(tree.Isbalanced());
cout << "test1 pass!" << endl;
}
// 测试2：右单旋（LL情况）
{
cout << "test2: LL - insert 30,20,10" << endl;
AVLTree<int, int> tree;
tree.Insert({ 30, 0 });
tree.Insert({ 20, 0 });
tree.Insert({ 10, 0 });
// 预期结构：
// 20
// / \\
// 10 30
assert(tree.Isbalanced());
cout << "test2 pass!" << endl;
}
// 测试3：左右双旋（LR情况）
{
cout << "test3: LR - insert 30,10,20" << endl;
AVLTree<int, int> tree;
tree.Insert({ 30, 0 });
tree.Insert({ 10, 0 });
tree.Insert({ 20, 0 });
// 预期结构：
// 20
// / \\
// 10 30
assert(tree.Isbalanced());
cout << "test3 pass!" << endl;
}
// 测试4：右左双旋（RL情况）
{
cout << "test4: RL - insert 10,30,20" << endl;
AVLTree<int, int> tree;
tree.Insert({ 10, 0 });
tree.Insert({ 30, 0 });
tree.Insert({ 20, 0 });
// 预期结构：
// 20
// / \\
// 10 30
assert(tree.Isbalanced());
cout << "test4 pass!" << endl;
}
// 测试5：复杂测试（包含所有旋转）
{
cout << "test5: - insert{50,30,70,20,40,60,80,35}" << endl;
AVLTree<int, int> tree;
vector<int> nums = { 50, 30, 70, 20, 40, 60, 80, 35 };
for (int num : nums) {
tree.Insert({ num, 0 });
}
// 预期结构：
// 50
// / \\
// 30 70
// / \\ / \\
// 20 40 60 80
// /
// 35
assert(tree.Isbalanced());
cout << "test5 pass!" << endl;
}
// 测试6：随机插入测试
{
cout << "test6: random - insert 100 random number" << endl;
AVLTree<int, int> tree;
srand(time(0));
for (int i = 0; i < 100; i++) {
int num = rand() % 1000;
tree.Insert({ num, 0 });
}
assert(tree.Isbalanced());
cout << "test6 pass!" << endl;
}
// 测试7：连续插入相同值
{
cout << "test7: insert same val in a row - 10,10,10" << endl;
AVLTree<int, int> tree;
tree.Insert({ 10, 0 });
tree.Insert({ 10, 0 });
tree.Insert({ 10, 0 });
// 预期结构：只有一个节点10
assert(tree.Isbalanced());
cout << "test7 pass!" << endl;
}
// 测试8：插入已排序序列
{
cout << "test8: - insert 1 to 100" << endl;
AVLTree<int, int> tree;
for (int i = 1; i <= 100; i++) {
tree.Insert({ i, 0 });
}
assert(tree.Isbalanced());
cout << "test8 pass!" << endl;
}
// 测试9：插入逆序序列
{
cout << "test9: - insert 100 to 1" << endl;
AVLTree<int, int> tree;
for (int i = 100; i >= 1; i--) {
tree.Insert({ i, 0 });
}
assert(tree.Isbalanced());
cout << "test9 pass!" << endl;
}
// 测试10：混合插入测试
{
cout << "test10: - insert{50,25,75,12,37,63,87,6,18,31,43,57,69,81,93}" << endl;
AVLTree<int, int> tree;
vector<int> nums = { 50,25,75,12,37,63,87,6,18,31,43,57,69,81,93 };
for (int num : nums) {
tree.Insert({ num, 0 });
}
assert(tree.Isbalanced());
cout << "test10 pass!" << endl;
}
//测试11：拷贝构造函数测试
{
cout << "test10: - insert{50,25,75,12,37,63,87,6,18,31,43,57,69,81,93}" << endl;
AVLTree<int, int> tree;
vector<int> nums = { 50,25,75,12,37,63,87,6,18,31,43,57,69,81,93 };
for (int num : nums) {
tree.Insert({ num, 0 });
}
AVLTree<int, int> T(tree);
assert(T.Isbalanced());
cout << "test11 pass!" << endl;
}
cout << "========== ALL Tests pass! ==========" << endl;
return 0;
}
运行截图：
评价
那么文章的最后就来评价一下AVL树的性能，那么AVL树由于左右子树的高度差不超过1，那么这会让AVL树的形态趋近于完全二叉树，那么AVL树查找的时间复杂度是logN量级，而对于插入来说，那么首先要利用二叉搜索树左小右大的性质，来确定新插入的节点的位置，那么这部分的时间复杂度是O(logN),然后接着会往上遍历沿途的祖先节点，检查器平衡因子，那么往上遍历的时间复杂度也是O(logN),如果根基的平衡因子为2或者-2，那么此时会旋转调整平衡,而旋转的时间复杂度则是常数级别O(1)，所以AVL插入的时间复杂度是2logN，也是在logN这个量级
结语
那么这就是本文关于AVL树全部的讲解，带你从多个维度认识AVL树，那么我之后还会学一个也是在二叉搜索树基础上调整其为平衡的树，那么该树便是是红黑树，那么其性能要比AVL树更高效一点，所以一般红黑树的应用场景要多一些，而AVL树反而有一点冷门，那么下一期我会更新红黑树，那么我会持续更新，希望你能够多多关照，如果本文对你有帮组的话，还请三连加关注，你的支持就是我创作的最大动力！
