赞
踩
——本节内容为Bilibili王道考研《数据结构》P52视频内容笔记。
目录
1.平衡二叉树,简称平衡树(AVL树),树上任一结点的左子树和右子树的高度之差不超过1;
2.结点的平衡因子=左子树高-右子树高;
3.平衡二叉树结点的平衡因子的值只可能是-1、0、1;
4.只要有任一结点的平衡因子绝对值大于1,就不是平衡二叉树。
1.key为数据域;
2.balance为平衡因子。
- typedef struct AVLNode {
- int key;
- int balance;
- struct AVLNode* lchild, * rchild;
- }AVLNode,*AVLTree;
在二叉树中插入新结点后,如何保持平衡?
1.从插入点往回找到第一个不平衡结点,调整以该结点为根的子树(即每次调整的对象都是“最小不平衡子树”);
2.在插入操作中,只要将最小不平衡子树调整平衡,则其他祖先结点都会恢复平衡;
3.要满足:(1)恢复平衡;(2)保持二叉排序树的特性(左子树结点值<根结点值<右子树结点值),分为以下四种情况:
①LL:在A的左孩子的左子树插入导致不平衡:
LL平衡右旋(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树。
- //f.lchild = p.rchild;
- //p.rchild = f;
- //gf.lchild / rchild = p;
②RR:在A的右孩子的右子树插入导致不平衡:
RR平衡左旋(左单旋转)。由于在根结点A的右孩子(R)的右子树(R)上插入了新结点,A的平衡因子由-1减至-2.导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原左子树则作为A结点的右子树。(操作同LL类似,省略图示)
- //f.rchild = p.lchild;
- //p.lchild = f;
- //gf.lchild / rchild = p;
③RL:在A的右孩子的左子树插入导致不平衡:
RL平衡旋转(先右后左双旋转)。由于在A的右孩子(R)的左子树(L)上插入新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置,然后再把该C结点向左上旋转提升到A结点的位置。
④LR:在A的左孩子的右子树插入导致不平衡:
LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树(R)上插入新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置, 然后再把该C结点向右上旋转提升到A结点的位置。
4.一步到位操作
RL 和 LR 两种操作可以由两步合并为一步,总结:先写C结点作为根结点,其左孩子为左旋操作所替代的结点,右孩子为右旋操作所替代的结点,将C结点的左子树放到左旋替代的结点的右子树的位置,将C结点的右子树放到右旋替代的结点的左子树的位置,其他都不变。
5.只有左孩子才有可能进行右旋操作,只有右孩子才有可能进行左旋操作;
6.在插入操作中,只要将最小不平衡子树调整平衡,则其他祖先结点都会恢复平衡;因为插入操作导致“最小不平衡子树”高度+1,经过调整后高度恢复,而平不平衡就是树高h决定的。
1.若树高为h,则最坏情况下,查找一个关键字最多需要对比h次,即查找操作的时间复杂度不可能超过O(h);
2.假设以 表示深度为 h 的平衡树中含有的最少结点数,则有:
3.基于上述公式可以证明:含有n个结点的平衡二叉树的最大深度为 ,平衡二叉树的平均查找长度(查找操作的时间复杂度)为 。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。