AVL树的插入与删除（详解）
AVL树的插入与删除（详解）
平衡二叉树的定义就不在这里赘述了，平衡二叉树的插入与删除都是基于平衡二叉树的查找进行的。平衡二叉树的查找和二叉树的查找又是一样的。
插入的话，我们从平衡二叉树的根结点出发查找我们需要插入的元素，如果查找到了表明该元素已经存在树中，因此就不用插入了，若没有查找到该元素就要创建这个元素结点，将结点插入我们所访问的那个查找失败的结点位置（查找失败结点是我们虚构的一个结点）。
删除的话，我们也是从根结点出发，找到我们需要删除元素的结点。若找到就将该结点删除。
前面的道理很简单，难就难在插入元素结点之后，我们的树可能会失去平衡。要学懂平衡二叉树，重点就在掌握插入和删除结点之后对树的平衡维护。树的平衡维护是通过平衡旋转来实现的。插入和删除结点导致的不平衡具体的旋转方法是不一样的。书上把结点的插入讲的很详细，但是结点的删除。。。我找了很多书，书上都没讲，刚开始我以为删除和插入的旋转是一样的打了好几大篇的草稿，各种蛇皮旋转，最终发现它和删除是不一样的（博主我已接近脑死亡）。最后又在网上找别人写的博客看，能把删除讲明白的很少，能用代码实现的反正是我没找到，好多都有问题（C语言实现的我不清楚，因为我C学的不太好）。但这至少个过程还是有收获的，有了一些思路，解决了一些我刚开始遇到的某些删除旋转问题。不懈努力之后，最终将删除的所有情况自己总结了出来，后面我会一一详细的讲解，希望对不懂的同学能有所帮助，也顺便纪念一下我死去的脑细胞。
一、AVL树的插入
首先我们得对结点的结构进行定义，参考书上讲的和我遇到的问题，最终我决定将结点定义如下（因为我感觉这样定义的结点比较容易实现平衡二叉树的插入和删除）：
应该很清晰明了就不一一解释结点了的结构了，代码：
public class BSTNode implements BalanceFactor {
private int data;
private int bf;
private BSTNode lchild, rchild, parent;
public BSTNode(int data) {// 构造一个结点
this.data = data;
this.bf = EH;//插入的结点平衡因子为0（EH）
this.lchild = null;
this.rchild = null;
this.parent = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getBf() {
return bf;
}
public void setBf(int bf) {
this.bf = bf;
}
public BSTNode getLchild() {
return lchild;
}
public void setLchild(BSTNode lchild) {
this.lchild = lchild;
}
public BSTNode getRchild() {
return rchild;
}
public void setRchild(BSTNode rchild) {
this.rchild = rchild;
}
public BSTNode getParent() {
return parent;
}
public void setParent(BSTNode parent) {
this.parent = parent;
}
}
书上看到的也是讲平衡因子写在结点里面，我看有些同学是用左子树高度减右子树高度什么的，没仔细看。平衡二叉树的平衡因子只能为1、0或-1，所以我将平衡因子类定义成了一个接口类。树的不同类型旋转也是根据平衡因子来判断的。
public interface BalanceFactor {
public static final int LH = 1;// 左高
public static final int EH = 0;// 等高
public static final int RH = -1;// 右高
}
首先得搞清楚什么时候才需要旋转？一定要记清楚这个。
当前这个结点A的子树的高度发生变化就可能需要旋转具体看这个结点A的平衡因子。插入的话树会变高，删除的话树就会变矮，我说的这个“树”不是整个平衡二叉树，而是相对于以某个结点来说的。比如某个叶子结点，你给它插入一个结点那么它的高度就会发生变化，但是相对于其他的某个结点来说，以这个“某个结点”为根的树高度可能并不会发生变化。删除也是一样的道理。
例如：A的平衡因子为-1，它的左子树变高了，A的平衡因子变为0，原本左子树比右子树矮，现在左子树变高，但A的高度没变，这时就不需要旋转。
通过递归的旋转，直到这个棵树的高度变为原来未插入时的高度，整棵树也就调整好了。下面我具体讲一下几种需要旋转的情况。
1.单右旋
若初始A的平衡因子为1，左子树的平衡因子为0，此时插入若导致A左子树的左子树变高，此时就需要单右旋，通过单右旋会使这棵树重新平衡，平衡后的树高度会恢复为原来的高度。单右旋的代码实现也很简单，单右旋的时候若H=0，需要注意，此时B.getRchild().setParent(A)会出错，因为得到的B点的右孩子为null。还有就是若A是根节点，A.getParent().setRchild()时也会报错。反正就是需要注意一下边界的情况。
public void R_Rotate(BSTNode p) {// 以结点p右旋处理
BSTNode lc = p.getLchild();
lc.setParent(p.getParent());
if (p.getParent() != null) {
if (p.getParent().getLchild() == p) {// p是父结点的左孩子
p.getParent().setLchild(lc);
} else {// p是父结点的右孩子
p.getParent().setRchild(lc);
}
}
p.setLchild(lc.getRchild());
if (lc.getRchild() != null) {
lc.getRchild().setParent(p);
}
lc.setRchild(p);
p.setParent(lc);
if (lc.getParent() == null) {
root = lc;
}
}
我在这里还没有改变结点的BF值，在后面的时候会改。
2.先左后右旋转
若初始A的平衡因子为1，左子树的平衡因子为0，此时插入若导致A左子树的右子树变高，此时就需要先左后右双旋转，通过双旋转会使这棵树重新平衡，平衡后的树高度会恢复为原来的高度。无论先左后右还是先右后左旋转，都是由两个单旋转合成的，就是先对B左单旋，再对A右单旋就可以了，很简单的。
3.单左旋
若初始A的平衡因子为-1，A的右子树平衡因子为0，若此时插入导致A的右子树的右子树高度增加，此时就需要单左旋。旋转之后A的高度恢复为原来的高度。
public void L_Rotate(BSTNode p) {// 以结点p左旋处理
BSTNode lc = p.getRchild();
lc.setParent(p.getParent());
if (p.getParent() != null) {
if (p.getParent().getLchild() == p) {
p.getParent().setLchild(lc);
} else {
p.getParent().setRchild(lc);
}
}
p.setRchild(lc.getLchild());
if (lc.getLchild() != null) {
lc.getLchild().setParent(p);
}
lc.setLchild(p);
p.setParent(lc);
if (lc.getParent() == null) {// 如果旋转之后lc是根节点
root = lc;
}
}
4.先右后左双旋转
若初始A的平衡因子为-1，A的右子树平衡因子为0，若此时插入导致A的右子树的左子树高度增加，此时就需要做先右后左旋转。旋转之后A的高度恢复为原来的高度。插入的话需要旋转的就这四种情况。可能会有疑惑，为什么A平衡因子为0，B的平衡因子为±1的情况没有列出来?可以尝试自己画一下，这种情况的话是不需要旋转的，只是当前的树可能会变高。若这颗树变高了（假设当前变高的子树根节点为A），那么相对于这棵树的父节点来说，又会是属于上面的四种情况之一。
观察四种旋转可以发现，插入的话通过单或双旋转后树的高度都会恢复原来的高度，就是经过一次平衡处理就可以实现平衡。但删除并不会这样，删除可能需要执行多级的平衡旋转。
5.左右平衡处理
左右平衡处理其实就是将上面四种旋转分成两类，这样代码会更清晰明了。将A结点左侧树变高需要进行的旋转和结点平衡因子的改变写在一个方法中：
public void InLeftBalance(BSTNode T) {// 对以T为根节点的二叉树做左平衡处理(先改变结点的bf,再旋转)
BSTNode lc = T.getLchild();
switch (lc.getBf()) {
case LH:// 单右旋的
T.setBf(EH);
lc.setBf(EH);
R_Rotate(T);
break;
case RH:// 先左旋，再右旋的
BSTNode rd = lc.getRchild();
switch (rd.getBf()) {
case LH:
T.setBf(RH);
lc.setBf(EH);
break;
case EH:
T.setBf(EH);
lc.setBf(EH);
break;
case RH:
T.setBf(EH);
lc.setBf(LH);
break;
}
rd.setBf(EH);
L_Rotate(lc);//双旋转
R_Rotate(T);
}
}
右侧平衡处理和左侧平衡处理是镜像的：只要会左侧的下面的代码这块可以忽略不用看。
public void InRightBalance(BSTNode T) {
BSTNode lc = T.getRchild();
switch (lc.getBf()) {
case RH:// 单左旋的
T.setBf(EH);
lc.setBf(EH);
L_Rotate(T);
break;
case LH:// 先右旋，再左旋的
BSTNode rd = lc.getLchild();
switch (rd.getBf()) {
case LH:
T.setBf(EH);
lc.setBf(RH);
break;
case EH:
T.setBf(EH);
lc.setBf(EH);
break;
case RH:
T.setBf(LH);
lc.setBf(EH);
break;
}
rd.setBf(EH);
R_Rotate(lc);
L_Rotate(T);
}
}
6.结点插入的实现
结点的插入是通过递归实现的，代码如下，可以参考一下最好搞懂，因为删除的递归实现和这个很类似。
首先我定义一个静态变量taller,记录当前的树是否长高，当taller=false时树的平衡就调整好了。
private static boolean taller;
public boolean insertAVL(BSTNode T, int x) {// 以T为根节点的平衡二叉树中插入元素x，成功返回true,失败返回false,taller反应树是否长高
if (T == null) {// 只有刚开始插入树为空才会执行这一步
root = new BSTNode(x);
return true;
}
if (x == T.getData()) {// ①
taller = false;
return false;
} else if (x < T.getData()) {// ②
if (T.getLchild() == null) {// 检查左子树
BSTNode q = new BSTNode(x);
T.setLchild(q);// 直接插入
q.setParent(T);
switch (T.getBf()) {
case EH:
T.setBf(LH);
taller = true;
break;
case RH:
T.setBf(EH);
taller = false;
break;
}
return true;
}
if (!insertAVL(T.getLchild(), x)) {
return false;
}
if (taller) {
switch (T.getBf()) {// 检查结点的平衡因子
case LH:// 原本结点的左子树比右子树高，且在左子树中插入了，需要做左平衡处理,处理之后树的高度不变
InLeftBalance(T);
taller = false;
break;
case EH:// 左右子树同样高，在左子树中插入，只是树变高了、平衡因子变为1，但当前不用做平衡处理
T.setBf(LH);
taller = true;
break;
case RH:// 右子树比左子树高，在左子树中插入，树的高度不变，当前结点的平衡因子变为0
T.setBf(EH);
taller = false;
break;
}
}
} else {// ③
if (T.getRchild() == null) {// 检查右子树
BSTNode q = new BSTNode(x);
T.setRchild(q);
q.setParent(T);
switch (T.getBf()) {
case EH:
T.setBf(RH);
taller = true;
break;
case LH:
T.setBf(EH);
taller = false;
break;
}
return true;
}
if (!insertAVL(T.getRchild(), x)) {
return false;
}
if (taller) {
switch (T.getBf()) {
case LH:
T.setBf(EH);
taller = false;
break;
case EH:
T.setBf(RH);
taller = true;
break;
case RH:
InRightBalance(T);
taller = false;
break;
}
}
}
return true;
}
二、AVL树的删除
1.删除节点的分类
由于在书上和其他博主那里都没有找到关于删除的详细讲解，所以我在这里会详细讲一下关于结点的删除。结点的删除我先定义了一个方法deleteAVL(BSTNode T，int x)——在以T为根结的树中删除结点元素值为x的结点。
结点的删除该开始可以分为四种情况，但最后我会将它归结为一种情况。
1.所删除的结点为叶子结点，可以将其直接删除，然后再依次向上调整使整棵树平衡。
2.删除的结点只有左子树且只有左子树一个节点（左右子树的高度差不超过1）。将待删除的结点与它的左子树结点值交换，删除叶子结点。这就转换成了第一种情况。
例如下面这段代码，T就是我们要删除的结点：
deleteAVL(T,x){
******
int value=T.getLchild().getDate();
deleteAVL(T,value);
T.setData(value);
******
}
这样就转换成了第一种情况了,代码只是形式，掌握思想就可以了。
3.删除的结点只有右子树且只有右子树一个节点，这样的情况以及转化方法和情况2几 乎是一样的，同理可以转化成情况1。
4.删除的节点左右子树都不空，这种情况和2.3的思想也是一样的。我们可以找到删除结点的前驱或者后继（中序遍历），前驱的位置是从该结点左转然后一直向右走到尽头（后继是从该节点右转然后向左走到尽头）。通过和2中类似的方法交换，将删除的结点与前驱结点元素值交换，再删除前驱结点。这里要删除的前驱位置结点可能会有左子树结点，那就再交换一次。情况四最多只需要两次交换。然后都能转化成情况1。这里可能看的有点迷糊，不过很正常，到时候看一下代码跟着代码走一次就全都明白了。
2.平衡旋转
（1）
若根节点A的平衡因子为0，无论删除结点导致A的左子树或右子树高度改变，此时A的平衡因子会变为-1或者1，但A还是平衡的并且以A为根结点的树高度没有发生变化。这种情不用做任何旋转。
（2）
若A的平衡因子为1，删除导致左子树的高度减小。此时A的平衡因子变为0，以A为根结点的的树高度减小，当前不用平衡调整。
（3）
若A的平衡因子为1，删除导致右子树的高度减小。此时A的平衡因子变为2，这样就需要平衡旋转了。这种情况下的平衡旋转还要依据A的左孩子结点B的平衡因子分为3种：
- B.getBf()=1，删除后经过旋转树的高度会减小。
- B.getBf()=0，删除后经过旋转树的高度恢复为原来的高度。
- B.getBf()=-1，删除后经过旋转树的高度会减小。
（4）
若A的平衡因子为-1，删除导致A的左子树高度减少。此时A的平衡因子变为-2，这样就需要平衡旋转了。这种情况下的平衡旋转和（3）是镜像的，要依据A的右孩子结点B的平衡因子分为3种：
- B.getBf()=1，删除后经过旋转树的高度会减小。
- B.getBf()=0，删除后经过旋转树的高度恢复为原来的。
- B.getBf()=-1，删除后经过旋转树的高度会减小。
（5）
若A的平衡因子为-1，删除导致A的右子树高度减少。此时A的平衡因子变为0，当前不用进行平和衡旋转，但树的高度减小了。
3.左右平衡处理
类似于删除，我们也将删除分为左右两种平衡处理。由于删除后的平衡处理会导致树的高度可能发生变化，前面提到过，所以在删除的左右平衡处理中会多一个对shorter(标记当前树是否变矮)的修改。
public static boolean shorter;// 记录树是否变矮的标志，若shorter=true要进行相应的调整
public void DeLeftBalance(BSTNode T) {
// 删除结点导致以T的左孩子为根节点的树高度改变，T结点失衡，做左平衡处理
BSTNode p = T.getRchild();
switch (p.getBf()) {
case LH:
// 先改结点的BF值
BSTNode q = p.getLchild();
switch (q.getBf()) {
case LH:
T.setBf(EH);
p.setBf(RH);
break;
case EH:
T.setBf(EH);
p.setBf(EH);
break;
case RH:
T.setBf(LH);
p.setBf(EH);
break;
}
q.setBf(EH);
// 再先右-左旋
R_Rotate(p);
L_Rotate(T);
shorter = true;
break;
case EH:// 左旋
p.setBf(LH);
T.setBf(RH);
L_Rotate(T);
shorter = false;
break;
case RH:// 左旋
p.setBf(EH);
T.setBf(EH);
L_Rotate(T);
shorter = true;
break;
}
}
public void DeRightBalance(BSTNode T) {
// 删除结点导致以T的右侧孩子为根节点的树高度改变，T结点失衡，做右平衡处理
BSTNode p = T.getLchild();
switch (p.getBf()) {
case LH:
T.setBf(EH);
p.setBf(EH);
R_Rotate(T);
shorter = true;
break;
case EH:
T.setBf(LH);
p.setBf(RH);
R_Rotate(T);
shorter = false;
break;
case RH:
BSTNode q = p.getRchild();
switch (q.getBf()) {
case LH:
T.setBf(RH);
p.setBf(EH);
break;
case EH:
T.setBf(EH);
p.setBf(EH);
break;
case RH:
T.setBf(EH);
p.setBf(LH);
break;
}
q.setBf(EH);
L_Rotate(p);
R_Rotate(T);
shorter = true;
break;
}
}
4.删除的实现
删除的实现和插入的实现很相似，删除也是通过地归来实现的，通过递归比较容易实现从下到上平衡的调整。稍微复杂一点的地方就是找到删除的结点但该结点左右子树都不空，这时候需要用我之前说的交换思想继续调用deleteAVL()方法，而且最多只用交换两次。如果还不明白的话可以参照下面给出的代码手动模拟一下交换的过程应该就会明白了。
public boolean deleteAVL(BSTNode T, int x) {// 删除成功返回true,返回失败返回false
if (T == null) {
System.out.println("树中不存在该结点,删除失败！");
shorter = false;
return false;
}
if (T.getData() == x) {
if (T.getLchild() != null && T.getRchild() != null) {// 需要删除的结点左右子树都不为空
BSTNode p = T.getLchild();
while (p.getRchild() != null) {
p = p.getRchild();
}
int value = p.getData();
deleteAVL(T, value);// ★★
T.setData(value);
if (shorter) {// 调整(结点的左子树高度减少1)
switch (T.getBf()) {
case LH://
T.setBf(EH);
shorter = true;
break;
case EH:
T.setBf(RH);
shorter = false;
break;
case RH:
DeLeftBalance(T);// shorter在DeLeftBalance(T)函数里面改变
break;
}
}
} else if (T.getBf() == LH) {// T只有一个左孩子结点
int value = T.getLchild().getData();
deleteAVL(T, value);// ★★
T.setData(value);
// 调整
T.setBf(EH);
shorter = true;
} else if (T.getBf() == RH) {// 只有右孩子结点
int value = T.getRchild().getData();
deleteAVL(T, value);// ★★
T.setData(value);
// 调整
T.setBf(EH);
shorter = true;
} else {// 左右子树都为空
if (T.getParent() == null) {// 删除的是根节点且只树有一个结点的情况
root = null;
} else {
delectNode(T);
shorter = true;// 删除结点，树变矮了
// return true;可以省略，函数的最后一行会返回true
}
}
} else if (x < T.getData()) {
if (!deleteAVL(T.getLchild(), x)) {// ★★
return false;
}
if (shorter) {// 调整(左子树中删除)
switch (T.getBf()) {
case LH:
T.setBf(EH);
shorter = true;
break;
case EH:
T.setBf(RH);
shorter = false;
break;
case RH:
DeLeftBalance(T);
break;
}
}
} else {
if (!deleteAVL(T.getRchild(), x)) {// ★★
return false;
}
if (shorter) {// 调整（右子树中删除）
switch (T.getBf()) {
case LH:
DeRightBalance(T);
break;
case EH:
T.setBf(LH);
shorter = false;
break;
case RH:
T.setBf(EH);
shorter = true;
break;
}
}
}
return true;
}
public void delectNode(BSTNode p) {// 删除一个叶子结点(存在父结点)的方法
if (p.getParent().getLchild() == p) {
p.getParent().setLchild(null);
} else {
p.getParent().setRchild(null);
}
}