1 00:00:00,000 --> 00:00:03,300 大家好 2 00:00:03,300 --> 00:00:09,190 数据结构与算法这一讲,我们介绍第十二章高级数据结构中的平衡的二叉搜索树 3 00:00:09,190 --> 00:00:17,110 我们今天特别介绍AVL树的删除以及AVL树的效率。 4 00:00:17,110 --> 00:00:26,950 那我们AVL树呢,它是要求左右子树,高度差不超过1的这么一个BST。 5 00:00:26,950 --> 00:00:35,320 那AVL树里面的删除操作,其实可以看作是插入的一个逆操作。 6 00:00:35,320 --> 00:00:41,420 那它的删除,首先也是要遵循BST的这样的结点删除的规律。 7 00:00:41,420 --> 00:00:48,450 那也就是说,我们从左子树里找最小,或者是找右子树里的最大, 8 00:00:48,450 --> 00:00:51,910 然后替代被删的那一个结点。 9 00:00:51,910 --> 00:01:01,910 删完以后, 有可能会导致某一个局部的子树呢,它的左分支或者右分支被缩短 10 00:01:01,910 --> 00:01:06,500 那如果是说原来最短的那个,我缩的更短, 11 00:01:06,500 --> 00:01:13,860 那这种情况下,就可能失衡,需要调整,而这种调整也可能会一直向根的方向传递。 12 00:01:13,860 --> 00:01:21,240 那我们来看,这个删除以后的调整所需要考虑的情况。 13 00:01:21,240 --> 00:01:29,400 最主要的是,删完以后它肯定要修改一些相应的平衡因子, 14 00:01:29,400 --> 00:01:36,820 我在这个删除以后,当前结点,很多情况下是被删这个结点它的父结点。 15 00:01:36,820 --> 00:01:41,380 那它的平衡因子,原来是零 16 00:01:41,380 --> 00:01:47,520 那我们删完一个结点呢,可能会导致它要修改平衡因子, 17 00:01:47,520 --> 00:01:53,660 但是它的树高,其实因为有另外一半那个没被删的撑着,它可能并没有发改变。 18 00:01:53,660 --> 00:02:00,830 如果是,我们原来平衡因子不为0的这么一个当前结点, 19 00:02:00,830 --> 00:02:08,480 它矮的那一边被删除了以后,那导致另外一边更矮,那这个当前结点就失衡了。 20 00:02:08,480 --> 00:02:15,840 那我们就需要一个调整,而且调整完了以后,往往这个子树高有可能会有所修改。 21 00:02:15,840 --> 00:02:22,000 那这个高度变矮了以后了不得呢,它就会往上面传递,影响其他的这个结点。 22 00:02:22,000 --> 00:02:25,910 它的这么一个平衡的状态,那我们需要层层的检查。 23 00:02:25,910 --> 00:02:33,680 我们要设置一个叫modified这样的一个变量,记录被删除以后它的调整状态。 24 00:02:33,680 --> 00:02:44,280 特别是这个删完以后,我们进行了调整,调整以后的这么一个子树比调整之前的那个子树,它有没有高度的变化。 25 00:02:44,480 --> 00:02:50,110 那如果没有,就是modified=false,那我们就不需要继续调整。 26 00:02:50,110 --> 00:02:59,400 如果是发生高度变化,也就是变短了,我们就需要调整,往上面再继续检查。 27 00:02:59,400 --> 00:03:04,960 那第一种情况就是,当前结点a,它的平衡因子是0 28 00:03:04,960 --> 00:03:09,080 它的左右子树高度本来就是一样的。 29 00:03:09,290 --> 00:03:14,440 那你在某一分支里面,删除一个结点,使它变矮了一点。 30 00:03:14,440 --> 00:03:20,920 那只需要修改它的平衡因子,它整这个树高呢并没有发生变化。 31 00:03:20,920 --> 00:03:26,430 那例如我们看这两个子树,删除它的高度之前是h+1, 32 00:03:26,430 --> 00:03:32,510 删完以后它的高度呢,还是h+1,因为有那么一个分支它并没有变矮。 33 00:03:32,510 --> 00:03:43,430 那这样的话呢,我们的这个调整呢,就不需要往上面传递了。只需要在这一层就完成了。 34 00:03:43,430 --> 00:03:49,530 那第二种情况呢,就是原来的平衡因子不是0, 35 00:03:49,530 --> 00:03:54,940 但是呢,它较高的那个子树被缩短了。 36 00:03:54,940 --> 00:04:03,800 那这种情况呢,我们来看这个例子,就是原来这个子树它的高度是h+2 37 00:04:03,800 --> 00:04:10,840 删除了以后呢,它的左右两个分支呢,就是都一样高了。 38 00:04:10,840 --> 00:04:16,540 我们整个这个子树的高度呢,变成了h+1。 39 00:04:16,540 --> 00:04:26,680 那这种情况呢,我们除了调整这个根的平衡因子以外呢,我还需要把这个modified的这个参数,设置为true, 40 00:04:26,680 --> 00:04:36,680 然后再继续往上面传递,来检查这些分支有没有修改,是不是需要再做这种高度的平衡检查。 41 00:04:36,680 --> 00:04:40,950 那还有一类情况,是比较复杂的, 42 00:04:40,950 --> 00:04:44,660 也就是当前结点a,它的平衡因子不是0。 43 00:04:44,660 --> 00:04:48,990 而且我们删除的时候,是在它比较矮的那个分支, 44 00:04:48,990 --> 00:04:54,430 来删除了结点,那删完以后它矮的就更矮了。 45 00:04:54,430 --> 00:05:00,020 这个时候,a结点本身就发生了失衡,需要进行调整。 46 00:05:00,020 --> 00:05:10,420 那调整的情况呢,我们最主要的是看,它原来比较重的那边那个子根结点它的平衡因子,是一个什么情况。 47 00:05:10,420 --> 00:05:15,070 然后呢,我们再进行相应的调整,那我们下面来展开讨论。 48 00:05:15,070 --> 00:05:23,300 在情况1呢,就是a的平衡因子不为0, 49 00:05:23,300 --> 00:05:28,510 比如说我们现在都是当它是右重的这个情况。 50 00:05:28,510 --> 00:05:36,910 然后呢它较矮的这边是左子树,其实呢只删这个结点,但是删完这个结点导致它削矮了一层。 51 00:05:36,930 --> 00:05:43,550 那它的这个较重的b子树呢, 它的平衡因子原来是0。 52 00:05:43,550 --> 00:05:50,680 那这种情况,那我们来看一下,我们做一个简单的旋转调整。 53 00:05:50,680 --> 00:05:56,060 那删之前,a子树的这个高度呢,是h+2。 54 00:05:56,060 --> 00:06:04,780 那我们下面呢,把这个它重的那一边的这个子树根,就是b,我们选上来作为新的子树根。 55 00:06:04,780 --> 00:06:07,930 然后a呢放在它的左子树 56 00:06:07,930 --> 00:06:14,190 原来的这个子树的高度呢,是h+2。那这个新的那个子树呢,还是h+2。 57 00:06:14,190 --> 00:06:25,010 因此我们只需要相应地修改这个a,b结点它们的平衡因子, 58 00:06:25,010 --> 00:06:33,470 因为这个a的平衡因子,其实它在前面,是已经变成过正2,我们再把它拉回来,变成正1。 59 00:06:33,470 --> 00:06:41,240 那这个b呢,再调整完以后,是变成左重的,那它的平衡因子变成-1。 60 00:06:41,240 --> 00:06:44,900 然后我们这个修改呢,就可以完成, 61 00:06:44,900 --> 00:06:49,630 所以我们modified=false,就完成了这个删除的调整操作。 62 00:06:49,630 --> 00:06:53,900 那再来看,删除的情况3.2。 63 00:06:53,900 --> 00:06:59,640 那这个情况呢,就是删的是a的左边,然后a原来是右重, 64 00:06:59,640 --> 00:07:04,900 然后它的那个右子树的结点呢,还是一个右重的情况, 65 00:07:04,900 --> 00:07:08,760 这种情况下我们也是做一个单旋, 66 00:07:08,760 --> 00:07:15,970 然后把这个重的那一边的这个结点的根呢我们作为新的子树根。 67 00:07:15,970 --> 00:07:25,670 然后我们把a挂到它的左边,那我们再来观察一下这两棵子树在删除前,删除后的情况, 68 00:07:25,670 --> 00:07:31,590 在删除前,以a为根的这个子树,它的树高是h+2。 69 00:07:31,590 --> 00:07:40,290 而删完,我们调整了以后, 这个b子树它的子树高呢,是h+1。 70 00:07:40,290 --> 00:07:50,440 那这样的情况呢,就是说,我们删完以后,整个新的这个子树,它的高度,比以前缩短了1。 71 00:07:50,440 --> 00:07:56,520 那因此,它就会影响到原来这个a,它的祖先上的其它结点。 72 00:07:56,520 --> 00:08:05,710 那我们就要,把当前这个结点呢,变成a的父结点,然后再对它的父结点进行检查。 73 00:08:05,710 --> 00:08:08,340 因此我们设modified=true, 74 00:08:08,340 --> 00:08:11,410 然后往上面传递,继续进行检查 75 00:08:11,410 --> 00:08:21,830 那我们还有一种情况是,当前结点a,和它较重的那个一个子树根结点b 他们的平衡因子是一个反着的情况。 76 00:08:21,830 --> 00:08:29,120 那这个时候呢,我们要把b重的那边的子树根呢,也拿出来考虑。 77 00:08:29,120 --> 00:08:37,280 那我们是把这个新结点c,作为新的子树的,然后a,b分别挂在它的两边。 78 00:08:37,280 --> 00:08:41,460 也就是说我们是做了一个双旋转 79 00:08:41,460 --> 00:08:44,270 我们来看一下,这两个子树的高度 80 00:08:44,270 --> 00:08:51,590 那在删除之前,这个a子树是不是呢,它高度是h+2的, 81 00:08:51,590 --> 00:09:01,830 特别是我们来看一下这个c结点,它的两个分支呢,它们的高度,可以是h-1或者是h-2 82 00:09:01,830 --> 00:09:09,940 但是呢必须保证,其中有一个是h-1高,另外一个可以是h-1或者是h-2。 83 00:09:10,160 --> 00:09:15,430 因为我们必须要保证b,它是左重的。 84 00:09:15,430 --> 00:09:20,340 那删完以后,我们调整了之后呢 85 00:09:20,340 --> 00:09:32,520 以c为子根,这个c,因为它的左右的这个子树的高度都是h,那c子树整个的高度是h+1。 86 00:09:32,520 --> 00:09:38,100 那我们a和b它的子树高到底是多少? 87 00:09:38,100 --> 00:09:43,380 要看刚才这个c结点它的左右子树具体是什么高度。 88 00:09:43,380 --> 00:09:46,520 然后再进行标记。 89 00:09:46,520 --> 00:09:50,000 这种情况下,原来a子树的高度是h+2, 90 00:09:50,000 --> 00:09:55,900 删完我们再调整以后,新的子树高度是h+1,它就削矮了一层 91 00:09:55,900 --> 00:10:04,080 这种情况我们要把,这个调整呢这个操作呢,要传递到前面a结点的父结点 92 00:10:04,080 --> 00:10:07,950 然后再继续看,是不是需要进行相应的调整。 93 00:10:07,950 --> 00:10:12,540 所以我们这个modified=TRUE,然后往上继续来处理。 94 00:10:12,540 --> 00:10:19,390 删除以后的这样的一个连续调整过程呢,是一层层往上面传的 95 00:10:19,390 --> 00:10:28,960 也就是如果是我这个局部的这个子树它的高度被削减了1,那我们就需要再往上面传递一层继续来检查 96 00:10:28,960 --> 00:10:36,830 这样传递呢,可能一直调整到根,当然如果是说根这一层我们modified也等于TRUE, 97 00:10:36,830 --> 00:10:43,380 那没有关系,因为根再往上面这没得传的了。那我们就到这个地方可以截止。 98 00:10:43,380 --> 00:10:48,990 那这个操作过程其实是根我们整个子树的高度相关的。 99 00:10:48,990 --> 00:10:54,790 那我们AVL树,它其实是log n的这么一个高度量级。 100 00:10:54,790 --> 00:10:58,440 那因此呢,它的整体的这个操作呢,就是theta log n的。 101 00:10:58,440 --> 00:11:00,760 那我们来看一下AVL树删除的例子。 102 00:11:04,700 --> 00:11:09,440 那在我们这个左图里面,假设我们要删除结点m, 103 00:11:09,580 --> 00:11:16,200 那我要找到它的左子树里面的最大l,我来替换到这个m的位置 104 00:11:16,200 --> 00:11:19,930 然后我把这个l删除,就变成了右图的这个情况。 105 00:11:19,930 --> 00:11:26,820 在这个情况下,我们可以看到,因为原来删除了l之后,当前结点是k, 106 00:11:26,820 --> 00:11:29,960 k呢原来它的平衡因子是0 107 00:11:29,960 --> 00:11:36,450 那我们把它的某一个子树变矮了以后呢,它的平衡因子只需要修改一下 108 00:11:36,450 --> 00:11:47,320 但是这个k子树的树高并没有发生变化,因此这个修改呢就到这儿截止,不需要再往上面继续调整, 109 00:11:47,320 --> 00:11:51,840 那我们就适合于这个情况1的这个例子,然后我们就删除结束了。 110 00:11:51,840 --> 00:12:01,500 在这个树里面我继续来删除n,那删除n以后呢,当前结点呢就变成了l, 111 00:12:02,270 --> 00:12:08,230 这个l它原来是一个左边是纵的 112 00:12:08,230 --> 00:12:14,980 然后呢,它这个子结点k呢,也是一个左纵的同边顺的情况, 113 00:12:14,980 --> 00:12:20,530 因此呢,我们就需要应用情况3.2来进行调整。 114 00:12:20,530 --> 00:12:26,610 在删完以后,这个l变成了一个危机的结点,它已经不平衡了。 115 00:12:26,610 --> 00:12:34,790 那我们调整呢,就是一个右旋,就是k变成子树根,然后l作为它的右子树。 116 00:12:34,790 --> 00:12:36,990 然后j呢,还挂在那 117 00:12:36,990 --> 00:12:45,600 那我们删完以后呢,这个新的k子树,它比原来那个l这样的一个子树呢,它的高度是变矮了1, 118 00:12:45,600 --> 00:12:50,880 那我们就要把这个信息再往上面传递,也就是传到l的父结点i, 119 00:12:50,880 --> 00:12:56,380 那i呢,就需要再检查,看看需不需要调整。 120 00:12:56,380 --> 00:13:03,580 那因为i结点它的平衡因子原来就不是0,是-1,也就是说是左纵的情况。 121 00:13:03,580 --> 00:13:08,110 现在你删除了右边的,也就是说短的那个变得更短 122 00:13:08,110 --> 00:13:11,580 因此,它就需要进行一个旋转的平衡。 123 00:13:11,580 --> 00:13:23,000 那我们来看,它的左子孩子平衡因子为1,也就是跟i呢,是反着的这么一个平衡因子的,一个取值。 124 00:13:23,000 --> 00:13:32,040 那这样的话呢,我们就还要拿出d它的一个右结点g来参与这个调整。 125 00:13:32,040 --> 00:13:38,340 那我们把g呢,作为一个新的子树根,然后d和i呢,分别挂接上, 126 00:13:38,340 --> 00:13:48,400 那调完以后,我们可以看到,因为刚才这个i已经是到根结点了,因此我们这个调整就可以到此结束了。 127 00:13:48,400 --> 00:13:59,450 那我们再来看一下AVL树的高度。那AVL树的这个高度呢其实也跟深度相关的。 128 00:13:59,450 --> 00:14:09,800 那我们高度就是深度+1, 那我们猜想,它的这个深度是log n的量级,那到底是多少呢?我们假设它是K倍的log n 129 00:14:09,800 --> 00:14:15,170 那我们来看一下这个K到底是有多大。 130 00:14:15,170 --> 00:14:22,180 那我们来构造一系列最接近于不平衡的这样的AVL树,也就是说,是临界状态的AVL树。 131 00:14:22,180 --> 00:14:33,210 那我们来看这个T1呢,就是深度为1,那其实高度是2,的这么的一个临界的AVL树。 132 00:14:33,210 --> 00:14:39,150 那T2呢,它其实是左边是T1,然后右边呢,就是一个独根的结点。 133 00:14:39,150 --> 00:14:49,250 那我们这样的递归的往下面去定义,那就可以发现呢,最接近于不平衡状态的这个临界的AVL树呢, 134 00:14:49,250 --> 00:14:57,480 它的左边我们都是让它为Ti-1,然后右边呢是Ti-2 135 00:14:57,480 --> 00:15:04,940 然后我们就构成一个这样的深度为i的这么一个Ti子树。 136 00:15:04,940 --> 00:15:10,470 那这样的一个树呢,我们可以看到它有这样的关系, 137 00:15:10,470 --> 00:15:17,280 也就是说我们t(1)呢,是有2个结点,t(2)呢是4个结点, 138 00:15:17,280 --> 00:15:29,100 而我们整个这个t(i)树呢,它的这个结点的个数,是t(i-1)加上t(i-2),然后 再加上这个根结点1 139 00:15:29,100 --> 00:15:39,650 我们来观察这样的一个递推的关系。它很类似于Fibonacci数列,给它和Fibonacci数列来建立一个联系呢 140 00:15:39,650 --> 00:15:46,830 就可以看到是t(i)=F(i+3)-1这样的一个关系, 141 00:15:46,830 --> 00:15:55,670 那Fibonacci数列呢我们有一个渐近公式,那我们把这个关系呢,去套进到Fibonacci数列的渐近公式里面, 142 00:15:55,670 --> 00:16:11,710 就可以得到这个t(i)指数它的结点的个数呢, 就会是1/根号5,的i+3次方-1,这个Φ呢是二分之1加上根号5, 143 00:16:11,710 --> 00:16:21,070 那我们再来看深度i跟结点个数t(i)的关系,我们来用换底公式 00:16:21,070 --> 00:16:34,430 来带进去,而且呢,我们把这个t(i)呢,就用结点个数n来带进去,那就会得到i<2/3的log以2为底,括号n+1的对数再减掉1 145 那这是它的深度,它的高度呢,其实就是,嗯,再把这个i值呢,是再加1,也就是,3/2的log以2为底n+1的对数, http://en.wikipedia.org/wiki/Fibonacci_number 146 那AVL树它的检索, 插入和删除的效率都是跟它的树高有关的。 The efficiency of inserting and deleting depends on its height. 147 那我们前面说到它的树高和树的深度都是log以2为底n的一个对数, The height and depth is logn. 148 那因此呢,具有n个结点的AVL树,它的插入删除,和检索的一个效率呢都是log n的量级。 So efficiency of indexing is logn. 149 AVL树呢,它比较适合组织内存里面小规模的数据 AVL tree is very fit to the small scale data in memory。 150 对于大规模的数据呢,我们就把它导到外层用B树和B+树来组织, For large scale data, we can use B tree or B+ tree with external memory. 151 那如果是内存能够放下,而且这个数据规模呢,还是特别大,那一般情况下,我们也是在内存里面用B树来组织的。 For large data in memory, we usually use B tree. 152 另外呢,就是AVL树,啊,它的这个插入删除的维护代价还是比较大的, Beside the inserting and deleting of AVL tree takes a big price. 153 所以现在呢,已经不是特别常用,那我们很多情况下是用红黑树,或者splay tree来替代。 So in most circumstances, we use red-black tree of splay tree instead. 154 那最后给大家一些思考,就是我们对比一下红黑树,还有AVL树,大家看一下它们的这个树高有些什么样的差异 Let's think about this. What's the difference of the height of red-black tree and AVL tree. 155 另外呢就是在它的结点插入删除的操作上,我们有哪一些相似的地方,有哪些不同, And the similar of inserting and deleting between these two trees. 156 还有我们考虑下这个代码它们的易写性和可维护性,哪一个是更好一些 And the difficulty of writing codes. 157 特别是我们还要考虑一下,在统计意义上,也就是说,我们在实际运行过程中,到底是红黑树的效率更高,还是AVL树的效率更高。 Efficiency between these two trees. 158 谢谢大家。 Thank you.