大家好。
数据结构与算法这一讲我们学习第十二章高级数据结构中的平衡二叉搜索树。
那我们今天主要是学习AVL树的概念和插入的操作。
在我们内存中呢一般都是用二叉搜索树来作索引。
那这个二叉搜索树的建立过程跟我们数据的输入呢是相关的。
那如果我按照一个比较随机的顺序来给数据，就会得到一个比较平衡的二叉搜索树， 能够得到logn的一个高度
但如果我给一个有序的顺序， 那就可能会得到一个规划成为单向链的这么一个BST
因此呢Adelson的三个科学家他们就联合提出了一种叫做AVL树的平衡二叉搜索树。
这种树它能够保持一个log n的高度，
在介绍AVL树之前我们 再来回顾一下那对于BST来说，
我们最关心的只是在一个中序遍历的情况下它是有序的就行，
并不关心它具体的结构是什么样的。
那它们的索引的这么一个效果都是等价的。
因此这两个树型呢
我们可以看作把这个左边的这个呢进行右旋或者是把右边这个进行左旋，
那它们所得到的这样的BST都是在索引的意义上是等价的。
另外呢我们可以再给它拉开一点来看一看，
可以看到它底下的这个结构，它们在旋转以后呢都能得到这么一个支架型的结构
我们都是中间的那个结点作为子根
那对于我们这样的一个L再R或者是R然后再L
这么两种类型的结构呢我们也是通过旋转操作能够得到这么一个支架型的这么一个平衡的结构，
那因此我们可以来定义这么一个AVL树。
首先它可以是空，
那如果不空的情况下我们限制AVL树它左右子树的高度差呢不能够超过1。
这个性质在整棵AVL树里面任何一个结点都必须满足。
那有了这个性质的保证我们可以保证整个这个AVL树呢它的高度会是在log n的量级。
那我们这里给的例子是一些处于边界情况的AVL树.
在这些树中我们任意删除其中的一个结点,
那都会导致这个树高会缩短1.
那我们再来定义AVL树的平衡因子。
也就是它的右子树的高度再减掉左子树的高度.
那我们可以知道呢平衡因子取值就是负1、0、正1这三种情况。
那我们来看一下AVL树的插入操作。
在这个AVL树里面进行插入首先我们需要考虑它的BST的性质。
因此呢我们还是按照二叉搜索树的这么一个插入操作。
首先我就是在整个这个BST里面检索待插入的结点它应该在什么位置。
那如果是检索成功，那我是不允许插入重复关键码的。
那如果检索失败，那一定是在它失败的那个位置上
我拉出的是一个空指针的这么一个位置，那在这个位置上就可以插入这个结点。
那插入了以后呢我们要考虑
AVL树它是不是一个平衡的.
它本来呢就是一边重，我接着新插入的节点, 还在它那个重的那一边继续插入,
那这就是发生了危机的情况，我们可能需要调整。
那这个调整呢我们希望它是比较局部的不要扩散到整个AVL树。
那我们来看这么一个例子。
在左边这个树里面呢我们是17是新插入的结点，
它插入以后呢就导致了12这个结点呢它的平衡因子会变成了2。
那我们就需要在这个局部进行调整。
那这里我们给的这个调整方案呢调整完了以后，
这个新的子树高度跟插入17之前的这个子树高度是一样的，就是高度为2。
那因此我们这个调整就在这个局部进行。
那我们再来考虑一下，我新插入一个结点S，
然后在插入了以后我整个树里面是哪一些结点需要调整呢？
那我们可以看一下在这个S插入了以后
从S往根的方向上头那些结点跟它最近的那一个它原来这个平衡因子呢就不是等于0的那个结点
那我们假设这个结点叫做a，
那主要就是要考虑这个a结点它的平衡因子到底是一个什么样的。
当然我们刚才想象的是它的平衡因子原来应该是不等于0
因此呢可能是有等于正1或者是负1的情况。
那为什么还有等于0的情况呢？那这个是一个特殊的考虑，
也就是说如果我们整个从S到根都没有这个祖先呢，它的平衡因子是不等于0的。
那也就是说这个时候我们让这个a呢就等于那个根节点，
而且这个根节点它的平衡因子也是0，
那对这个情况呢a子树的它的树高发生了改变，
而且从a到s这么一个路径上头这些祖先呢它们的树高呢也都是平衡因子是发生了一些调整
那如果是S插到它的左边，那我们就变成负1.插到右边呢变成正1，有这么一串的调整。
那如果a的平衡因子原来是等于负1，
那假设我们把s插到它的右边的话呢，那我们这个a的平衡因子就变成了0，
它的子树高度呢不发生变化，也就是说不会影响整个树里面其他的节点
那我们其实就不需要调整了。
那如果a的平衡因子是正1，那s又插到它的右边
那它就会变成了正2，这个时候是需要调整的。
那怎么调整呢？我们分为四类情况进行调整。
那其实呢又分为两个大类，
那也就是说如果是a的平衡因子它原来是等于负1的，也就是说它是左重的
那这个时候我们新插入的节点s
它如果是插入到a的这个左孩子
那个b结点呢它的左边还是右边，
如果是还插到它的左子结点的左边，那就是LL型的。
那如果是插到它的子结点的右边，那就是LR型的
那我们后面呢有相应的调整策略。
那如果是a的平衡因子原来是正1的，也就是说它原来是右重的
那因为你现在新插入结点又插到它的这个右边，那使得它变成了正2这样的情况，
那我们就会有如两个跟刚才对称的这个情况发生
也就是RR型的，或者是RL型的。
那我们先来看这样的LL型和RR型。
因为它们其实主要的涉及到两个结点的调整，所以我们把它称为单旋转
在这两种情况下呢我们都是把a的子结点b呢作为新的子树根
然后a呢作为这个b结点的一个孩子，
那就完成了这么一个调整
那我们来看一下LL型的单旋转。
那这个时候呢需要进行一个单旋，我把b调整为这个新的子根，然后a呢作为它的右孩子。
调整完了以后我们可以看到a和b他们的平衡因子都变成了0
而且这个子树高度呢跟我们在插入这个新结点s之前a子树的高度是一样，都是h+2
因此，调整在这个局部发生就可以了。不会影响啊AVL树里面其他的结点。
那我们来看一下，嗯，它的调整运算的这么一个实质。
我们在插入之后呢，它变成了这么一个结构。
那我们把它调整之后，我是把这个b结点作为a结点的父结点，
那，嗯，调整了之后呢，嗯，它的这么一个结构呢.跟调整之前都是保持了中序下面的一个有序性质，
也就是原来是T0aT1cT2bT3
那调整完了以后的一个新结构仍然是这么一个有序的性质。
那这里，我们注意呢，我的a、b、c它并不表示在中序下头遍历的一个性质
在整个这个讲义里面，我们是把a作为一个失衡的、 需要调整的那么一个子根结点。
b结点呢，作为它的直接的，一个需要调整的这个局部结点。
而c结点呢，是辅助来。考察这个，子树的情况的一个，孙一级的结点。
那我们再来看这么一个双旋转的过程
对于RL或者是LR型呢，我们其实是要涉及到三个结点来进行调整。
那这里呢，我们主要是调整RL这个情况，对于LR呢它是类似的。
那我们来看RL的这么一个旋转。
在插入之前，我们a子树的树高呢，它是h+2的。
那插入之后，那因为我们这是一个RL型的插入，
我们把这个，c，它的左子树或者是右子树之一把它变高了一层。
那也就是说原来他们都是h-1的高度，现在呢，某一个子树呢变成了h。
我们调整的时候呢，是分两步进行的。首先就是c旋转，为b的这么一个根。
接着呢，我们再围绕着这个a来旋转，把c呢又旋转为一个新的根。
那a呢做为它的一个左子结点。
旋转完了以后，可以看到c子树它的平衡因子一定是0的。
那这个a和b呢，它的平衡因子是多少?
主要是看刚才我们插入的这个新的结点是在T1 子树还是在T2子树里面。
而且呢，我们可以发现我们旋转调整完了以后
这个以c为根的新子树它的高度呢一定是h+2的,跟刚才没有插入之前的这个a子树的高度是一样。
因此，我们的调整在这儿就可以完成了。
从这个c结点开始往根的方向上头，其他的这些结点呢，就都不需要进行任何的调整。
当然我们在整个这个插入的过程中，在插入到这个T1子树或者是T2子树的那个叶的位置，
那个新结点s，然后s到a的一个方向上头的这些祖先呢，因为他们原来的平衡因子都是0，
那我们要把它变成+1或者-1那主要是看你这个先插入的结点s是在左子树里面插入呢，还是在右子树里面插入。
那我们来看这么一个例子。
那我连续的插入7个字符串，首先得到一个LR型的这么一个结构
那我进行一个双旋转，然后呢，就得到了这么一个支架形的结构。
那接着呢，我再插入hit还有hi
那这个局部结构就是以cop为根的这么一个子树呢,它是需要进行调整的。这是一个RL型的调整。
那我们双旋转以后呢，在这个新的子树的结构它就是保持跟原来的，插入之前的树高是一样的。
那这个调整就完成了。
那接着，我们再继续，插入his。
插入这个以后呢，我们可以发现在，copy这个根结点它是失衡了。
因此呢，需要进行一个RL型的一个单旋转。
然后把hi 旋转回一个子树根，然后呢，这个调整就完成了。
再接着我们插入hia
那这个局部呢，我们可以看到以hit为根的这个子树它是一个LL型的这么一个失衡
那因此我们发生一个单旋转， 然后呢就就调整到位了。
那最后给大家几个思考题，一个是我们是不是能够修改AVL树的平衡因子定义？
原本我们限定的是高度差为1，现在我们能不能改成高度差为2呢？
第二个思考呢就是，我们对关键码1、2、3、这样一直到2的k次方减1来顺序输入
然后呢我们也按照AVL树的这么一个调整方案来进行调整,结果我们可以得到一棵高度为k的完全的满二叉树。
例如：我们顺序输入1234567，
那可以地得到这个一个平衡的、完全的满二叉树。那这个证明呢其实是一个归纳法的证明。
也就是说我们可以对高度，k来进行归纳。在k等于1的时候成立。然后呢，如果是在k的时候成立，那我们考察k+1的时候是怎么样的。
谢谢大家。