二叉搜索树进阶——AVL树
ok，那么今天来分享下，一种高阶数据结构——AVL树
之前分享的数据结构中，已经介绍过了二叉搜索树。
这个二叉搜索树又称二叉排序树
其性质如下：
——如若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值
——如若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值
——它的左右子树也分别为二叉搜索树。
虽然二叉搜索树可以缩短查找的效率，最优情况下：O(log2n） 最坏情况下：O(n)
AVL树
那么把它给“进化”一下，使它向二叉搜索树中插入新节点后，还能保证插入的每个节点的左右子树高度之差的绝对值不超过1
那么它就是变成了AVL树。
其性质如下：
——它的左右子树都是AVL树
——左右子树高度差的绝对值不超过1，既可以1 / -1 /0
举个例子：
此时这就是一个AVL树
那么绿色标记的是左右子树的高度差——平衡因子
这里我规定为计算其高度差：右树高度 减 左树高度
当然也可以规定：左树高度减去右树高度
所以说，一颗二叉搜索树是高度平衡的，它就是AVL树，如果它有n个节点，其高度可保持在
O(log2n),这里是指log以2为底的n，搜索时间复杂度同样也为此。
那么接下来到实现环节
AVL树的节点是如何定义的呢？
static class TreeNode{
public int val;//节点的值
public int bf;//节点的平衡因子
public TreeNode left;//左孩子
public TreeNode right;//右孩子
public TreeNode parent;//双亲节点
public TreeNode(int val){
this.val=val;
}
}我们可以定义一个类来存储节点的信息
那么可以看到，和之前二叉搜索树定义是差不多的，多了个平衡因子和和双亲节点
平衡因子出现，是因为，高度平衡的原因。
那么为什么还要多个父亲节点呢？下文会说到，这里方便后续的旋转操作
接着，我们先来实现下插入操作
插入操作
首先这个插入一部分操作是和二叉搜索树是差不多的
因为AVL树实在二叉搜索树基础上改进的
public TreeNode root;
//插入操作
public boolean insert(int val){
if(root==null){
root=new TreeNode(val);
return true;
}
TreeNode parent=null;
TreeNode cur=root;
while (cur!=null){
if(cur.val<val){
parent=cur;
cur=cur.right;
} else if (cur.val==val) {
return false;
}else {
parent=cur;
cur=cur.left;
}
}
TreeNode newNode=new TreeNode(val);
if(parent.val<val){
parent.right=newNode;
}else {
parent.left=newNode;
}思路：如若当前节点是空的，那么插入节点成为新节点，
如若当前节点不为空，那么判断下当前的节点值和插入的节点值，当前的节点值大于插入的节点值，那么就往左边寻找，反之，就从右边寻找，如果等于，那就退出，不能插入相同的节点值
找到合适插入的叶子节点之后，那么判断当前的节点值与插入节点值大小，进行向左还是向右插入。
ok，此时完成了插入操作，那么问题就要来了，
如何进行平衡因子的调整
举个例子
这里往左插入一个，那么此时10这个节点的平衡因子-1，原本为0，减1，等于-1，因为之前规定平衡因子是右树-左树高度的
同理可得，那么此时10这个节点的平衡因子就调为+1，即 1
所以代码可以这样写
//此时插入完成后，要进行平衡因子的调节
//新节点的父亲节点为parent
newNode.parent=parent;
cur=newNode;
while (parent!=null){
if(parent.right==cur){
//如果插入节点等于父亲节点的右边，那么bf++，假设数的高度等于右树减左树
parent.bf++;
}else {
//如果插入节点等于父亲节点的左边，那么bf--，
parent.bf--;
}当然这里要找到我们的10这个节点，那么10这个节点是作为左右子树的父亲节点，那么意思是找父亲节点
那么此时我们插入值的时候，先让插入节点的父亲节点保存此时的父亲节点信息
举个例子：
假设我们要插入的是18这个节点，那么插入之后，就要让18的父亲节点保存此时的parent，此时的parent是15这个节点
把父亲节点保存之后，再让为空的cur保存下新节点（newNode）
接着呢，就要开始修改下平衡因子，插入在左边呢，就减1，插入在右边呢，就+1
那么你插入完成之后，还得要进行一个重要的事，就是判断下当前的平衡因子是否是符合范围的，如果不符合，那么就要进行相对应的操作
比如当平衡因子为0时：
那么此时意味着我们的AVL树是不需要进行任何操作的
当平衡因子等于1 / -1，以及平衡因子等于2时
此图中，当20的平衡因子等于1的时候，就证明整个树是平衡了吗？显然是不是的
可以看出15这个节点的平衡因子是2，大于1，所以也是不平衡的，由此可得
当然，换过来，-1的时候，不一定也是平衡的。
所以，我们得出，如若是-1 或者 1，那么要向上回溯，看看是否都平衡了
如若当前的节点的平衡因子不等于0 / 1 / -1 那么必须要进行相关操作了
那么上诉代码，可以这样写：
//此时判断下平衡因子
if(parent.bf==0){
//那么代表了插入的时候，此树已经平衡，
break;
}else if(parent.bf==-1||parent.bf==1){
//此时意味着，当前的树平衡，不代表上面的树平衡，所以得向上调整
cur=parent;
parent=cur.parent;
}else {
if(parent.bf==2){
//此时代表的是右树高，那么往左转，即左单旋
if(cur.bf==1){
rotateLeft(parent);
}else {
//此时走到，意味着parent.bf=2,cur.bf=-1,出现异号，此时需要右左双旋
rotateRL(parent);
}
}else {
//parent.bf==-2
//此时是左数高，需要往右转，即降低左数的高度，即右单旋
if(cur.bf==-1){
rotateRight(parent);
}else {
//此时到这里，意味着parent.bf=-2,cur.bf=1,是异号的，所以进行左右双旋
rotateLR(parent);
}
}
//此时完成旋转之后，就平衡了
break;
}
}
return true;
}那么此时，如若发现当前的节点的平衡因子等于2或者-2时，我们的操作是对树进行旋转。
那么旋转呢又分四种类型
右单旋、左单旋、左右单旋、右左单旋
那么接下来一一介绍，哪种情况，对应哪种旋转，
右单旋
举个例子：
此时当一棵树进行这样的插入，直到插入10这个节点，然后再往10这个节点的左边，再插入5，意思是往较高左子树的左侧插入一个节点
那么此时平衡因子是有问题的
30节点没问题，60节点的平衡因子有问题了，它等于-2
那么此时parent和cur在哪呢？
如图所示
为什么到这里？前面的代码有说过的
后面就不再叙说了
此时看着刚刚给到的树图片，很明显发现左边树高了，那么此时我们就要进行旋转，把左树高度降低，然后匀节点到右树那边
那么此时你看，右边是右单旋的结果，这棵树的平衡因子是都不超过2的，所以达到平衡。
那么是如何移动的呢？
思路：
首先让30的左边连接60这个节点
然后让60的左边连接30的右边，此时连接到这里，那么还是符合二叉搜索树的。
那么接着，要修改下它们的父亲节点是谁了
旋转后，60的父亲节点是30，40的父亲节点是60
此时，还得修改最重要的一个东西，平衡因子，可以发现，我们动了30、60、40这个几个节点，它们最终的平衡因子都是为0的
那么接下来，我们其实可以用几个临时节点来进行操作移动的，如上图所示
那么上代码：
private void rotateRight(TreeNode parent){
//首先定义两个节点
TreeNode subL=parent.left;
TreeNode subLR=subL.right;
parent.left=subLR;
subL.right=parent;
//有可能subL的左边节点为空，那么就要判断一下
if(subLR!=null){
subLR.parent=parent;
}
TreeNode pParent=parent.parent;
//修改parent.parent的节点之前要保存一下parent.parent,有可能当前的parent上面还有一个节点
parent.parent=subL;
//下面修改subL的指向
if(parent==root){
//parent就是头节点
root=subL;
root.parent=null;
}else {
if (pParent.left == parent) {
//如果parent的父亲节点左边等于parent，那么代表着parent左边要连接subL
pParent.left = subL;
} else {
pParent.right = subL;
}
//无论怎么样，subL的父亲节点永远都是pParent
subL.parent=pParent;
}
//修改完指向后，那么就要修改下此时平衡因子
subL.bf=parent.bf=0;
} if(subLR!=null){
subLR.parent=parent;
}
这里值得说下
如若我们的30节点下没有40这个节点，那么此时不去判断就去执行这个subLR.parent=parent;
就会报空指针异常
TreeNode pParent=parent.parent;
为什么要进行这一步呢，因为不能保证30的节点上是否还有父亲节点，所以也要进行判断修改下，
但是parent.parent=subL;这一步已经修改了这个parent 即30父亲节点的指向，所以要提前把parent的父亲节点保存下来。
ok，到这里，右单旋讲完了
接下来讲讲左单旋
左单旋
类比上上面的，当树出现不平衡，且左树较高时，那么就进行了右单旋
现在是这样的情况，同样是树出现了不平衡，这时候是右树较高了，那么我们就进行左单旋
比如上图，30这个节点的平衡因子就是2，40节点的平衡因子是1
很明显就要进行旋转，把一些节点进行左旋
类似于右单旋的操作，定义两个临时节点来进行旋转
思路：
40节点的左边连接30节点，30的左边连接35这个节点，
然后接着修改30、40、35这几个节点的父亲节点
然后接着修改下它们平衡因子，
思路和右单旋是差不多的
public void rotateLeft(TreeNode parent){
//首先定义两个节点
TreeNode subR=parent.right;
TreeNode subRL=subR.left;
parent.right=subRL;
subR.left=parent;
//subRL此时有可能为空，需要判断下
if(subRL!=null){
subRL.parent=parent;
}
//此时有可能parent的parent不为空，所以修改parent.parent指向之前，保存一下
TreeNode pParent=parent.parent;
parent.parent=subR;
//到这里要修改下parent的parent的指向了
if(root==parent){
root=subR;
root.parent=null;
}else {
if(pParent.left==parent){
pParent.left=subR;
}else {
pParent.right=subR;
}
subR.parent=pParent;
}
//到这里进行修改平衡因子
subR.bf=parent.bf=0;
}此时，我们也可以发现，左单旋和右单旋，代码是差不多，只不过修改的一些节点是不一样而已。
那么此时，我们可以发现这样一个现象
当parent的平衡因子=2，cur所在节点的平衡因子是1，那么此时是左单旋
如果是parent所在节点的平衡因子=-2，cur所在节点的平衡因子是-1，此时是右单旋
那么有没有出现，paren所在节点t为正，cur所在节点所在为负，或者parent所在节点为负，cur所在的节点为正呢？
接下来就讲讲左右单旋
左右单旋
这样情况，就是有着parent的平衡因子是 -2，cur的平衡因子是 1
那么此时如若我们进行单纯的左右单旋
比如进行右旋
很明显此时树还是不平衡的，
同理，单纯的左旋也是不行的。
那么如何做呢？
我们先要进行左旋，再进行右旋
编辑
为什么会有左右双旋，会有两个情况呢？
因为在25这个节点进行插入的时候，插入25左节点和右节点，其情况是不一样的，对应的就有两个图了
那么和左单旋、右单旋是有点点类似的，那么就是说旋转完后，也要进行平衡因子的修改
此时发现，我们图A定义的节点中，subR的平衡因子等于-1，parent的平衡因子等于0，subRL的平衡因子等于0
图B定义的节点中，subR的平衡因子是0，parent平衡因子是1，subRL平衡因子是0
那么如何进行区别呢？
可以看到导致这两个的情况发生，是当初插入23节点时，插入25的左边还是右边，才会发生的
所以我们判断下25那个的平衡因子即未插入前 subRL的平衡因子是1，还是-1就行
如若是-1，对应的是图B，如若是1，那么对应的是图A
那么代码如下
public void rotateLR(TreeNode parent){
//涉及到旋转，就要进行到平衡因子的修改，所以要记录一下
TreeNode subL=parent.left;
TreeNode subLR=subL.right;
int bf=subLR.bf;
//进行左右双旋
rotateLeft(parent.left);
rotateRight(parent);
//进行平衡因子的修改
if(bf==-1){
subLR.bf=0;
subL.bf=0;
parent.bf=1;
}else if(bf==1){
subLR.bf=0;
subL.bf=-1;
parent.bf=0;
}
}ok，左右单旋讲完了
那么同理讲讲右左单旋吧
右左单旋
右左单旋，意味是parent的平衡因子是2，cur对应节点的平衡因子是-1，是异号的
举个例子
此时同样的，单一进行右单旋，或者左单旋也是不行的
所以现在进行右左双旋
同样的因为插入18后面的节点，放在左右位置不同，导致会有两种情况，是和左右双旋差不多的
其他的平衡因子的修改是通过这个subRL的平衡因子是1，还是-1来进行两种不同情况的修改
public void rotateRL(TreeNode parent){
//涉及到旋转，就要进行到平衡因子的修改，所以要记录一下
TreeNode subR=parent.right;
TreeNode subRL=subR.left;
int bf=subRL.bf;
//进行右左双旋
rotateRight(parent.right);
rotateLeft(parent);
//进行平衡因子的修改
if(bf==-1){
parent.bf=-1;
subRL.bf=0;
subR.bf=0;
}else if(bf==1){
subR.bf=1;
subRL.bf=0;
parent.bf=0;
}
}那么到这里呢，四个旋转也讲完了
那么这个插入操作，就是这样子，
删除操作
那么删除操作呢？
这里不做实现了
不过有相对应的一些思路：
就像是和之前二叉搜索树，有点类似的，找到删除节点，然后找到另一个”替死鬼“（参照二叉搜索数的删除操作），然后进行更新平衡因子，然后不平衡，进行旋转
那么问题又来了？如何判定是不是平衡的呢？
判断是否平衡
是否平衡，那么平衡因子起到关键作用
而平衡因子呢，又是右树高度-左树高度得到的
此时，又涉及到树的高度，那么此时得先求树的高度
比如，求到了当前节点的树左右子树的高度，那么此时进行右子树高度减去左子树高度，看看绝对值是否小于1，
还有一个需要注意，我们的平衡因子是通过bf++/bf--计算得来，万一，本来就计算错了
所以不能单纯看右子树高度减去左子树高度，看看绝对值是否小于1，
还要看看此时的平衡因子和左右子树的高度差是否相等
但当前节点平衡，下面左右子树就一定平衡了？
显然是不一定，那么此时需要进行从当前节点开始判断下，左树是否平衡，右树是否平衡
代码如下
//求树的高度，这个是涉及到检查AVL树是否平衡的操作
private int height(TreeNode root){
if(root==null){
return 0;
}
int leftH=height(root.left);
int rightH=height(root.right);
return leftH > rightH ? leftH+1 : rightH+1;
}
public boolean isBalanced(TreeNode root){
if(root==null){
return true;
}
int left=height(root.left);
int right=height(root.right);
//存在一个可能，就是平衡因子本来就是计算错的，所以为了防止这个
if((right-left)!=root.bf){
System.out.println("当前节点平衡因子出现问题："+root.val);
return false;
}
//此时看它的平衡因子是否小于，以及左右树是否符合当前的条件
return Math.abs(left-right)<=1 && isBalanced(root.left) && isBalanced(root.right);
}树的高度，就使用了递归去求，找到左边的高度，和右边的高度，一比较，谁大，谁的高度再+1
+1是说明，是要包含此时根节点
到这里已全部讲完所学到的AVL树。
后面附上源码：
public class AVL {
//首先AVL树在二叉搜索树的基础上完成的，首先创建个二叉搜索树
static class TreeNode{
public int val;
public int bf;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
public TreeNode(int val){
this.val=val;
}
}
public TreeNode root;
//插入操作
public boolean insert(int val){
TreeNode newNode=new TreeNode(val);
if(root==null){
root=newNode;
return true;
}
TreeNode parent=null;
TreeNode cur=root;
while (cur!=null){
if(cur.val<val){
parent=cur;
cur=cur.right;
} else if (cur.val==val) {
return false;
}else {
parent=cur;
cur=cur.left;
}
}
if(parent.val<val){
parent.right=newNode;
}else {
parent.left=newNode;
}
//此时插入完成后，要进行平衡因子的调节
//新节点的父亲节点为parent
newNode.parent=parent;
cur=newNode;
while (parent!=null){
if(parent.right==cur){
//如果插入节点等于父亲节点的右边，那么bf++，假设数的高度等于右树减左树
parent.bf++;
}else {
//如果插入节点等于父亲节点的左边，那么bf--，
parent.bf--;
}
//此时判断下平衡因子
if(parent.bf==0){
//那么代表了插入的时候，此树已经平衡，
break;
}else if(parent.bf==-1||parent.bf==1){
//此时意味着，当前的树平衡，不代表上面的树平衡，所以得向上调整
cur=parent;
parent=cur.parent;
}else {
if(parent.bf==2){
//此时代表的是右树高，那么往左转，即左单旋
if(cur.bf==1){
rotateLeft(parent);
}else {
//此时走到，意味着parent.bf=2,cur.bf=-1,出现异号，此时需要右左双旋
rotateRL(parent);
}
}else {
//parent.bf==-2
//此时是左数高，需要往右转，即降低左数的高度，即右单旋
if(cur.bf==-1){
rotateRight(parent);
}else {
//此时到这里，意味着parent.bf=-2,cur.bf=1,是异号的，所以进行左右双旋
rotateLR(parent);
}
}
//此时完成旋转之后，就平衡了
break;
}
}
return true;
}
/**
* 右单旋
* @param parent
*/
private void rotateRight(TreeNode parent){
//首先定义两个节点
TreeNode subL=parent.left;
TreeNode subLR=subL.right;
parent.left=subLR;
subL.right=parent;
//有可能subL的左边节点为空，那么就要判断一下
if(subLR!=null){
subLR.parent=parent;
}
TreeNode pParent=parent.parent;
//修改parent.parent的节点之前要保存一下parent.parent,有可能当前的parent上面还有一个节点
parent.parent=subL;
//下面修改subL的指向
if(parent==root){
//parent就是头节点
root=subL;
root.parent=null;
}else {
if (pParent.left == parent) {
//如果parent的父亲节点左边等于parent，那么代表着parent左边要连接subL
pParent.left = subL;
} else {
pParent.right = subL;
}
//无论怎么样，subL的父亲节点永远都是pParent
subL.parent=pParent;
}
//修改完指向后，那么就要修改下此时平衡因子
subL.bf=parent.bf=0;
}
/**
* 左单旋
* @param parent
*/
public void rotateLeft(TreeNode parent){
//首先定义两个节点
TreeNode subR=parent.right;
TreeNode subRL=subR.left;
parent.right=subRL;
subR.left=parent;
//subRL此时有可能为空，需要判断下
if(subRL!=null){
subRL.parent=parent;
}
//此时有可能parent的parent不为空，所以修改parent.parent指向之前，保存一下
TreeNode pParent=parent.parent;
parent.parent=subR;
//到这里要修改下parent的parent的指向了
if(root==parent){
root=subR;
root.parent=null;
}else {
if(pParent.left==parent){
pParent.left=subR;
}else {
pParent.right=subR;
}
subR.parent=pParent;
}
//到这里进行修改平衡因子
subR.bf=parent.bf=0;
}
/**
* 左右双旋
* @param parent
*/
public void rotateLR(TreeNode parent){
//涉及到旋转，就要进行到平衡因子的修改，所以要记录一下
TreeNode subL=parent.left;
TreeNode subLR=subL.right;
int bf=subLR.bf;
//进行左右双旋
rotateLeft(parent.left);
rotateRight(parent);
//进行平衡因子的修改
if(bf==-1){
subLR.bf=0;
subL.bf=0;
parent.bf=1;
}else if(bf==1){
subLR.bf=0;
subL.bf=-1;
parent.bf=0;
}
}
/**
* 右左双旋
* @param parent
*/
public void rotateRL(TreeNode parent){
//涉及到旋转，就要进行到平衡因子的修改，所以要记录一下
TreeNode subR=parent.right;
TreeNode subRL=subR.left;
int bf=subRL.bf;
//进行右左双旋
rotateRight(parent.right);
rotateLeft(parent);
//进行平衡因子的修改
if(bf==-1){
parent.bf=-1;
subRL.bf=0;
subR.bf=0;
}else if(bf==1){
subR.bf=1;
subRL.bf=0;
parent.bf=0;
}
}
//中序遍历可以获得一个有序的数据
public void inorder(TreeNode root){
if(root==null){
return;
}
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}
//求树的高度，这个是涉及到检查AVL树是否平衡的操作
private int height(TreeNode root){
if(root==null){
return 0;
}
int leftH=height(root.left);
int rightH=height(root.right);
return leftH > rightH ? leftH+1 : rightH+1;
}
public boolean isBalanced(TreeNode root){
if(root==null){
return true;
}
int left=height(root.left);
int right=height(root.right);
//存在一个可能，就是平衡因子本来就是计算错的，所以为了防止这个
if((right-left)!=root.bf){
System.out.println("当前节点平衡因子出现问题："+root.val);
return false;
}
//此时看它的平衡因子是否小于，以及左右树是否符合当前的条件
return Math.abs(left-right)<=1 && isBalanced(root.left) && isBalanced(root.right);
}
