目录
- 00.BBST——平衡二叉搜索树
- 01.AVL树
- 02.AVL的插入
- 2.1单旋——zig 与 zag
- 2.2插入节点后的单旋实例
- 2.3手玩小样例
- 2.4双旋实例
- 2.5小结
- 03.AVL的删除
- 3.1单旋删除
- 3.2双旋删除
- 3.3小结
- 04.3+4重构
- 05.综合评价AVL
- 5.1优点
- 5.2缺点
00.BBST——平衡二叉搜索树
本文是介绍众多平衡二叉搜索树(BBST)的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树(BST)在极度退化的情况下,十分不平衡,不平衡到只朝一侧偏,成为一条链表,复杂度可达 O ( n ) O(n) O(n),所以我们要在“平衡”方面做一些约束,以防我们的树结构退化得那么严重。
具体来说,含 n n n个节点,高度为 h h h的BST,若满足 h = O ( l o g 2 n ) h=O(log_2 n) h=O(log2n),则称为称为平衡二叉搜索树。
01.AVL树
AVL树是一种BBST(稍后会证明)。它约束自己是否平衡,主要靠一个指标——平衡因子。定义:平衡因子=左子树高度-右子树高度。如果满足 − 2 < 全部平衡因子 < 2 -2<全部平衡因子<2 −2<全部平衡因子<2,则该AVL树处于平衡状态;否则,需要靠一系列措施,将其恢复平衡。
首先先证明AVL树满足BBST的要求,即 h = O ( l o g 2 n ) h=O(log_2 n) h=O(log2n)(下式)。我们可转而证明n=Ω(Φh)(即,AVL的节点数不会太少)
结论:高度为h的AVL Tree 至少有 fib((h+3)-1 个节点
证明:
02.AVL的插入
插入一个节点会导致一串祖先的失衡,删除一个节点至多导致一个祖先失衡。但是,通过后续代码就可发现,删除节点比插入节点复杂的多。原因是,插入节点只要调整好了一处,这条路径上的所有祖先都可平衡,复杂度是
O(1)
。而删除节点是,调整好了一处平衡,另一处就会不平衡,自下而上层层调整,复杂度是O(n)
。
2.1单旋——zig 与 zag
zig 与 zag 分别对应右单旋和左单旋。单旋
的操作改变的是两个
节点的相对位置。改变的是三条线:一上一下一子树。新树根上行指向原根,新树根原子树给到原根。如下图,V到Y那去,Y到C那去。
2.2插入节点后的单旋实例
在下图处添加一个节点,自上而下更新高度(或平衡因子),g会率先进入不平衡状态。观察g,p,v呈一条线,而非“之”字,所以用单旋调整(之字形对应双旋)。具体来说,对g左单旋。
2.3手玩小样例
例题:将1,2,3,4,5,6依次插入空的AVL Tree,最终AVL Tree长成什么样?
过程:
首先正常插入1,2;插入3时,1是第一个发现不平衡的节点,zag(1),即对1进行左单旋,成功解决;正常插入4
插入5时,3是第一个发现不平衡的节点,zag(3),即对3进行左单旋,成功解决
插入6时,2是第一个发现不平衡的节点,zag(2),即对2进行左单旋,成功解决
2.4双旋实例
双旋
的操作改变的是三个
节点的相对位置。分为两种情况——zig-zag与zag-zig。
在下图处添加一个节点,自上而下更新高度(或平衡因子),g会率先进入不平衡状态。观察g,p,v呈“之”字,所以用双旋。具体来说,先zig§,再zag(g).
2.5小结
AVL树中插入节点引发失衡,经旋转调整后重新平衡,此时包含节点g,p,v的子树高度是不变的,子树高度复原,更高祖先也必平衡,全树复衡。故在AVL树中修正插入节点引发的失衡不会出现失衡传播。
03.AVL的删除
删除一个节点至多导致一个祖先失衡。
3.1单旋删除
3.2双旋删除
3.3小结
AVL树中删除节点引发失衡,经旋转调整后重新平衡,此时包含节点g,p,v的子树高度有可能不变也有可能减小1,故在AVL树中修正删除节点引发的失衡有可能出现失衡传播。
04.3+4重构
通过观察以上插入和删除的结果示意图,发现结构是一样的——三个节点按顺序呈三角形,四个子树按原来的顺序分别挂在两个孩子节点的下边。(如下图)
那我们就不必关注具体的技巧了,而是将三个节点和四个子树拆开,像暴力组装魔方那样(先拆散)拼上。
05.综合评价AVL
5.1优点
- 查找、插入、删除,最坏时间复杂度为 O ( l o g n ) O(logn) O(logn)
- O ( n ) O(n) O(n)的存储空间
5.2缺点
- 需要额外维护高度或平衡因子这一指标(后续Splay Tree可改善这一问题)
- 删除操作后,最多需旋转 Ω ( l o g n ) \Omega(logn) Ω(logn)次
- 单次动态调整后,全树拓扑结构的变化量可能高达 Ω ( l o g n ) \Omega(logn) Ω(logn) (RedBlack Tree可缩到 O ( 1 ) O(1) O(1))
谢谢观看~