平衡二叉树
2019-05-13 14:20:39 0 举报平衡二叉树的介绍
作者其他创作
大纲/内容
3
9
10
14
8
解决方法：以N2为中心右旋，再以N1为中心左旋
解决方法：和LL类似，以N1为中心右旋
13
以N2为中心左旋
平衡因子：左子树的高度减去右子树的高度（或者右子树的高度减去左子树的高度），由平衡二叉树的定义可知，平衡因子只能为0，1，-1
7
6
情形1：LL（第一个字母L表示最小失衡子树的左子树较高，第二个字母L表示最小失衡子树较高子树的左子树较高，其他情况类似）
15
20
5
插入节点时，只需要根据插入节点往上查找第一个不平衡子树，修复即可；
先介绍两个概念：
此时N1为节点5
接下来介绍平衡二叉树的查找，插入，删除：
用N1表示最小失衡子树的根节点，N2表示最小失衡子树较高子树的根节点
以N2为中心右旋
2.删除的节点只有左儿子
第一个字母表示最小失衡子树的平衡因子
4.删除的节点既有左儿子，又有右儿子
此时N1为节点5，N2为节点9
①直接删除该叶子节点
删除节点16后，二叉树失衡
情形5：RL
LE（可以当做LL处理）：
AVL树的删除和二叉查找树一样，分为四种情况：
以N1为中心左旋
此时会造成更大的不平衡子树
插入节点8后，二叉树失衡
①假设被删除的节点为D，找到D的前驱节点（左子树的最右节点）或后驱节点（右子树的最左节点），假设为C，用C替代D，然后删除C；
16
平衡二叉树：也叫AVL树，二叉查找树的一种
情形6：RE（这种情况不可能存在，可自行推导）
18
解决方法：和RR类似，以N1为中心左旋
字母取值：L表示左子树较高，R表示右子树较高，E表示左右子树等高
此时N1为节点10，N2为节点7
再以N1为中心右旋
解决方法：以N1为中心右旋
插入节点3后，二叉树失衡
11
②删除C后将导致C的父节点平衡因子发生变化，因此要从C的父节点开始向上检索失衡子树，然后按LL（包括LE），LR，RR（包括RE），RL四种情况处理，处理完继续向上检索直到根节点。
性质：任何一个节点的左子树和右子树的高度之差的绝对值不超过1
最小失衡子树：在新插入的节点往上寻找，第一个平衡因子的绝对值超过1的节点为根的子树就是最小失衡子树（删除类似）
3.删除的节点只有右儿子
RE（可以当做RR处理）：
1.删除叶子节点
第二个字母表示最小失衡子树较高子树的根节点的平衡因子
删除节点3后，二叉树失衡
3.删除的节点只有右儿子，和第2种情况类似
4.删除的节点既有左儿子，又有右儿子
此时N1为节点12
①假设删除的节点为D，用D的左儿子替换掉D
12
另外删除有可能出现LE，RE两种情况
情形4：RR
以N1为中心右旋
插入：
注意：
解决方法：以N1为中心左旋
情形2：LR
插入节点13后，二叉树失衡
②删除叶子节点将导致父节点平衡因子的变化，所以要从父节点开始向上检找出其中的失衡子树，然后按照LL（包括LE），LR，RR（包括RE），RL四种情况进行处理，处理完继续向上检索直到根节点
情形3：LE（这种情况不可能存在，可自行推导）
此时N1为节点10
这里用两个字母表示各种情况：
2.删除的节点只有左儿子
删除节点时，可能存在由于调整最小不平衡树而导致了更大的不平衡树，所以要继续往上查找不平衡子树直到根节点。
删除：
②从D的父节点开始查找失衡子树，然后按LL（包括LE），LR，RR（包括RE），RL四种情况处理，处理完继续向上检索直到根节点
删除节点9后，二叉树失衡
解决方法：以N2为中心左旋，再以N1为中心右旋
调整后如右图所示
查找：和二叉查找树一样，具体看二叉查找树
0 条评论
下一页
