5、5_2_平衡二叉树.pdf

《5、5_2_平衡二叉树.pdf》由会员分享，可在线阅读，更多相关《5、5_2_平衡二叉树.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/3/13王道考研/1本节内容平衡二叉树(AVL)王道考研/CSKAOYAN.COM1王道考研/CSKAOYAN.COM知识总览知识总览22020/3/13王道考研/2王道考研/CSKAOYAN.COM平衡二叉树的定义平衡二叉树的定义平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）树上任一结点的左子树和右子树的高度之差不超过1。结点的平衡因子=左子树高-右子树高。50262166706030682621305060666870只要有任一结点的平衡因子绝对值大于1，就不是平衡二叉树G. M. Adelson-Velsky和E. M. Landis000-10

2、10-1平衡二叉树结点的平衡因子的值只可能是1、0或1。00-1-2-3-4-5-53王道考研/CSKAOYAN.COM平衡二叉树的插入平衡二叉树的插入在二叉排序树中插入新结点后，如何保持平衡？5026216670603068000-1010-15026216670603068000-2021-2670插入67查找路径上的所有结点都有可能受到影响从插入点往回找到第一个不平衡结点，调整以该结点为根的子树每次调整的对象都是“最小不平衡子树”42020/3/13王道考研/3王道考研/CSKAOYAN.COM5026216670603068000-2021-2670每次调整的对象都是“最小不平衡子树”

3、5026216670603068000-1000-1670平衡二叉树的插入平衡二叉树的插入在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡5王道考研/CSKAOYAN.COM调整最小不平衡子树调整最小不平衡子树62020/3/13王道考研/4王道考研/CSKAOYAN.COM调整最小不平衡子树（调整最小不平衡子树（LL）1）LL平衡旋转（右单旋转）。由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右

4、子树则作为A结点的左子树。ABARBLBRHHHABARBLBRH+1HHABARBLBRH+1HH0112二叉排序树的特性：左子树结点值 根结点值 右子树结点值BLBBRAAR00LL插入右旋B目标：1.恢复平衡；2.保持二叉排序树特性思考：为什么要假定所有子树的高度都是H？最小不平衡子树7王道考研/CSKAOYAN.COM调整最小不平衡子树（调整最小不平衡子树（RR）ABALBLBRHHH0-1二叉排序树的特性：左子树结点值 根结点值 右子树结点值ALABLBlchild/rchildp实现 f 向右下旋转， p 向右上旋转：其中 f是爹，p为左孩子，gf为f他爹 f-lchild = p

5、-rchild; p-rchild = f; gf-lchild/rchild = p;f实现 f 向左下旋转， p 向左上旋转：其中 f是爹，p为右孩子，gf为f他爹 f-rchild = p-lchild; p-lchild = f; gf-lchild/rchild = p;左旋ABALBLBRBBLBRAALpf左旋、右旋操作后可以保持二叉排序树的特性BLBBRAARALABLBBR9王道考研/CSKAOYAN.COM调整最小不平衡子树（调整最小不平衡子树（LR）ABARBLBRHHHABARBLBRH+1HH01-12LR插入ABARBLCRHHH12CCLH-1-1也有可能是插入到

6、C的左子树3）LR平衡旋转（先左后右双旋转）。由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置102020/3/13王道考研/6王道考研/CSKAOYAN.COM调整最小不平衡子树（调整最小不平衡子树（LR）ABARBLCRHHH-12CCLH-1AARCRHH2CCLH-1BBLH1左旋C右旋CCRHCCLH-1BBLH1AARH01-10BLBCLC CRAAR11王道考研/CSKAOY

7、AN.COM调整最小不平衡子树（调整最小不平衡子树（LR）ABARBLCRHHH-12CCLH-1左旋C+右旋CCRHCCLH-1BBLH0AARH-110ABARBLCRHHH-12CCLH-1-1左旋C+右旋CCRHCCLH-1BBLH1AARH00122020/3/13王道考研/7王道考研/CSKAOYAN.COM调整最小不平衡子树（调整最小不平衡子树（RL）ABALBLBRHHH0-1RL插入ABALBLBRHH+1H1-2BCRH1CCLH-11AAL-2ALACLCCRBBRHBRH4）RL平衡旋转（先右后左双旋转）。由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由

8、-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置也有可能是插入到C的右子树13王道考研/CSKAOYAN.COM调整最小不平衡子树（调整最小不平衡子树（RL）BCRH1CCLH-11AAL-2ALACLCCRBlchild = p-rchild; p-rchild = f; gf-lchild/rchild = p;实现 f 向左下旋转， p 向左上旋转：其中 f是爹，p为右孩子，gf为f他爹 f-rchild = p-lchild; p-lchil

9、d = f; gf-lchild/rchild = p;只有右孩子才能左上旋162020/3/13王道考研/9王道考研/CSKAOYAN.COM5026216670603068000-2021-2670每次调整的对象都是“最小不平衡子树”LL型，左孩子右旋5026216670603068000-1000-1670填个坑填个坑在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡17王道考研/CSKAOYAN.COM填个坑填个坑ABARBLBRHHHABARBLBRH+1HHABARBLBRH+1HH011200LL型右旋BABALBLBRHHH0-1RR型左旋BABALBLBR

10、HH+1H-1-2BBLBRHH+10AALH0树高H+2树高H+3树高H+2182020/3/13王道考研/10王道考研/CSKAOYAN.COM填个坑填个坑ABALBLBRHHH0-1RL型ABALBLBRHH+1H1-2右旋C+左旋CCRCH-10B-1BRHCLAAL0HHABARBLBRHHHABARBLBRH+1HH01-12LR型左旋C+右旋CCRHCCLH-1BBLH1AARH00树高H+2树高H+3树高H+219王道考研/CSKAOYAN.COM填个坑填个坑插入操作导致“最小不平衡子树”高度+1，经过调整后高度恢复最小不平衡子树父L平衡因子恢复在插入操作中，只要将最小不平衡子

11、树调整平衡，则其他祖先结点都会恢复平衡202020/3/13王道考研/11王道考研/CSKAOYAN.COM5026216670603068000-1000-1670练习练习5026216670603068-2-1-167900插入 90RR型21王道考研/CSKAOYAN.COM练习练习5026216670603068-2-1-167900右孩子左旋RR型注意检查：是否符合 左根右5026217030680-1679006660000-1000222020/3/13王道考研/12王道考研/CSKAOYAN.COM练习练习5026217030680-1679006660插入 63RL型000-

12、100050262170306867906660-2-11630123王道考研/CSKAOYAN.COM练习练习右旋+左旋 66RL型5026217030681-1679006660000-2-1016306660637068906750262130242020/3/13王道考研/13王道考研/CSKAOYAN.COM练习练习注意检查：是否符合 左根lchild = p-rchild; p-rchild = f; gf-lchild/rchild = p;实现 f 向左下旋转， p 向左上旋转： f-rchild = p-lchild; p-lchild = f; gf-lchild/rchild = p;30