AVL（平衡二叉搜索）树学习笔记

AVL=BBST

一. 平衡因子

     平衡因子 = 节点的左子树高度 - 右子树高度

如图：节点2的平衡因子为1-0=1

          节点11的平衡因子为2-1=1

          其他同理

总结：所谓AVL树就是其中所有节点的平衡因子不超过1也不小于-1。

二. AVL=适度平衡

1.一棵规模为n的AVL树，高度不超过O(logn)

     

 

2. 补充知识点：

斐波那契数列：Fibonacci Sequence

0,1,1,2,3,5,8,13,21,34,55,......

fib(n) = fib(n-1)+fib(n-2)   前一项+前两项（n>2）

fib(3) = fib(2)+fib(1)=1+0=1

3. 高度为h的AVL树，至少包含S(h)=fib(h+3)-1个节点。

三. 插入：

1. 单旋

• 同时可有多个失衡节点，最低者g不低于x祖父
• g经单旋调整后复横，子树高度复原；更高祖父也必平衡，全树复横。

栗子：............................................................................................................................

栗子：............................................................................................................................

往T2或T2下插入一个节点，使得g的平衡因子由-1变成-2。从g出发，找到它的孩子节点p，孙子节点v。

                              

（1）引入一个临时的引用rc，指向节点p

（2）p的左子树T1成为g的右子树

（3）g成为p的左孩子

（4）p替换g成为局部子树的根

 

做了一次zag旋转，这种旋转只涉及到局部的常数个节点，所对应的时间消耗为O(1)。

2. 双旋

• 同时可有多个失衡节点，最低者g不低于x祖父
• g经单旋调整后复横，子树高度复原；更高祖父也必平衡，全树复横

                 

栗子：............................................................................................................................

插入单词：cup ，cop， copy， hit， hi， his 和 hia 后得到的 AVL 树

   

       

   

四. 删除

1. 单旋

• 同时至多一个失衡节点g，首个可能就是x的父亲
• g经单旋调整后复衡，子树高度未必复原；更高祖先仍可能失衡
• 因有失衡传播现象，可能需要做O（logn）次调整

     

删除一个节点后，g处于失衡状态。进行一次顺时针的zig（g）

2. 双旋

删除一个节点后，g处于失衡状态。进行一次逆时针的zag(p),在进行一次顺时针的zig(p)。

栗子：............................................................................................................................

五.（3+4）重构

无论插入还是删除，无论是单旋还是双旋，最终效果应该都是这样一种形式。