1.二叉搜索树回顾以及性能分析
1.1二叉搜索数的概念
二叉搜索树又被称为二叉排序树，它是一棵空树，或者是具有一下性质的二叉树
-
若它的左子树不为空，则左子树上所有的节点的值都小于根节点的值。
-
若它的右子树不为空，则右子树上所有的节点的值都大于根节点的值。
-
它的左右子树也分别为二叉搜索树。
图例：
从上述概念以及图中可以看出，二叉搜索树具有以下的特性：
- 二叉搜索树中最左侧的节点是树中最小的节点，最右侧的节点一定是数中最大的节点
- 如果采用中序遍历的方式遍历二叉搜索树，可以遍历出一个有序的序列。
1.2 二叉搜索树的查找
既然将其称为二叉搜索树，因此这颗树主要是用来进行查找元素，而且查询的原理特别简单。具体如下：
题目在一棵二叉搜索树中，查找某个值，如果在树中存在这个元素，那么就返回true,否则返回false
图例：
插入和删除操作，都是建立在查找的基础上的。
1.3二叉树查询性能分析
插入和删除操作都必须先要查找，查找效率代表了二叉搜索树中各个操作的性能
对于n个节点的二叉搜索树，若每个元素查找的概率相等。则二叉搜索树的平均查找长度是节点在二叉搜索树的深度的函数，即节点越深，则比较次数越多。
但是对于相同的关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。
图例：
最优条件下，二叉搜索树为完全二叉树，其平均比较次数为:log2N
最差条件下，二叉搜索树退化为单支树，其平均比较次数为:N/2
但是在图中我们也可以看到，当二叉搜索树退化成单支树的时候，二叉搜索树的性能就是去了。那么怎样才能改进，无论按照怎样的插入关键字码的顺序，都可以让二叉搜索树的性能最佳？
那么就要介绍今天的重头戏了，AVL树，当我们搜索二叉树中插入节点的时候，让加入节点之后的搜索二叉树是一颗平衡二叉树。那么这样就极大的提高了二叉搜索树的查找性能。
2.AVL树
2.1AVL树的概念
二叉搜索树虽然可以缩短查找的效率，但是如果插入这可二叉树是一组有序的序列，那么在最后形成的二叉树就是一棵单支数，我们在查找元素的时候就类似于在顺序表中查找元素，效率低下。因此我们的前辈们就发明出了一种解决上述问题的方法：当二叉搜索树中插入新节点之后，如果能保证每个节点的左右子树之差的绝对值不超过1(需要对书中的节点进行调整)，即可以降低树的高度，从而减少平均查找长度。
简单的说一棵AVL树，要么是一颗空树，要么就是满足一下性质的二叉搜索树
- 它的左右子树都是AVL树
- 左右子树盖度之差(简称平衡因子)的绝对中不超过1
如果一棵二叉搜索树是高度平衡的，它就是AVL树，如果它有n个节点，其高度可保持在O(log2N),搜索时间复杂度就是O(log2N).
2.2AVL树节点的定义
为了实现二叉搜索树简单，AVL树节点在定义得时候维护一个平衡椅子，具体节点定义如下：
static class TreeNode {
public int val; //每个节点中的值
public int bf; //每个节点的平衡因子
//当前节点的平衡因子，我们默认等于 右树的高度 - 左树的高度
public TreeNode parent; //指向父亲节点
public TreeNode left; //指向左孩子
public TreeNode right; //指向右孩子
public TreeNode(int val) {
this.val = val;
}
}
2.3AVL树的插入
AVL树就是在二叉搜索树的基础上引进了平衡因子，因此AVL树也可以看做数一棵二叉搜索树，那么AVL数的插入就可以分为两个步骤：
- 按照在搜索二叉树中的插入节点的方法进行插入节点
- 调整节点的平衡因子
-
插入节点的算法流程：
当在一棵二叉树中插入节点的时候，如果这颗树还是空的，那么当前传进来的node节点赋为根节点即root = node。如果此时这颗树不为空，我们要到添加新节点的位置。因为这颗二叉树是二叉搜索树，在根节点的右边都是比根节点的值大的节点，在根节点的左边都是比根节点小的节点。此
创建出一个cur节点，用于遍历这颗二叉树，创建出一个parent指向的节点用于跟踪cur节点. parent指针指向的节点时cur的父亲节点，创建初始的时候让cur = root.我们及当前传进来的节点为node.遍历节点的时候，如果node.val < cur.val 那么就在这颗树的左子树进行查找，如果node.val > cur.val 那么就在这颗树的右子树进行查找.否则在二叉树中就存在这个节点，就返回false.当cur == null的时候那就证明此时已经遍历完了二叉树的一支路径，此时要添加节点。而此时的parent指针指向的节点就是二叉树遍历一支路径之后的最后一个节点。此时让node.val 和 parent.val进行比较，如果parent.val > node.val那么parent.left = node,否则就是parent.right = node.因为我们的存储方式是，孩子父亲表示法，所以node/parent = parent.此时的cur = node。图例：
public boolean insert(int val){ TreeNode node = new TreeNode(val); //如果此时的跟节点为空，那么就是这棵二叉树还是空的 if(root == null){ root = node; return true; } TreeNode parent = null; TreeNode cur = root; while(cur != null){ if(node.val > cur.val){ //进入右子树 parent = cur; cur = cur.right; }else if(node.val == cur.val){ return false; }else{ //进入左子树 parent = cur; cur = cur.left; } } //此时cur == null，parent指向的是叶子节点 if(node.val > parent.val){ parent.right = node; }else{ parent.left = node; } node.parent = parent; cur = node; }
先按照二叉搜索树的规则将节点插入到AVL数中，但是新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要跟心平衡因子，并检测是否破坏了AVL数的平衡性
所以说当前的主要任务就是，我们要知道在这颗二叉搜索树中，那一个分支，子树不是平衡的，知道不平衡的树，把它改成平衡的树。
当在二叉搜索树中插入一个节点之后，我们就要更新它的平衡因子，在默认的情况下，每个节点对应的平衡因子是0，在插入一个节点之后，我们记新插入的这个节点为cur,cur 的父亲节点为parent,parent节点的父亲节点为Pparent.
图例：
-
我们可以分析一下，当插入的这个节点也就是cur,如果在插入节点指向parent节点没有左右孩子，那么就要根据cur.val和parent.val的大小，来判断parent节点的平衡因子在新添节点之后，会变成什么，如果cur节点时parent节点的左孩子，因为我们默认平衡因子 = 右子树的高度 - 左子树的高度。所以说此时的parent.bf就为1，如果cur节点是parent节点的右孩子，所以说此时parent.bf就为-1.
-
让我们分析一下，造成二叉搜索树不平衡的时候的平衡因子是多少？
我们可以总结一下：
- 如果parent节点的平衡因子为0，说明在插入node节点之后，把paren节点左后子树的节点的高度持平，所以现在满足AVL树的性质，插入成功。
- 如果parent节点的平衡因子为±1，说明在插入node节点之前parent的平衡因子一定为0，在插入node 节点之后，以parent为根节点的二叉树的高度就增加了，需要继续继续向上更新。
- 如果此时parent的平衡因子为±2，那么就违背了AVL树的性质，所以现在要进行旋转处理，让二叉树的高度降下来。
while(parent != null){
//如果cur 是父亲的右孩子，父亲的平衡因子++
if(cur == parent.right){
parent.bf++;
}else if(cur == parent.left){
parent.bf--;
}
//如果平衡因子的值等于0，那么就证明这棵树是平衡的，直接退出
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{
rotateRightLeft(parent);
}
}else if(parent.bf == -2){
if(cur.bf == -1){
//进行右旋
rotateRight(parent);
}else{
rotateLeftRight(parent);
}
}
}
2.4AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新的节点，可能造成不平衡，此时必须调整数的结构。使二叉搜索树平衡话。根据节点插入位置的不同，AVL树的旋转分为4种.
2.4.1右单旋
新节点插入较高左子树的左侧-右单旋
这种情况是当parent节点没有父亲节点的前提之下：
还有一种情况，就是其实在上述的图中subLR其实这个节点可以没有。还有我们的上述的图中的二叉搜索树仅仅是一棵子树，parent节点还会有自己的父亲节点
还是上图举例：
贴代码：
public void rotateRight(TreeNode parent){
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
//当前的这个parent节点，不一定使用棵树的跟节点，可能是一棵树的跟节点，也可能是一棵树的子树
//进行旋转
parent.left = subLR;
if(subL.right != null){
subLR.parent = parent;
}
subL.right = parent;
TreeNode Pparent = parent.parent;
parent.parent = subL;
//如果此时Pparent == null 那么就证明此时这个parent节点就是一棵树的根节点
if(parent == root){
root = subL;
root.parent = null;
}else{
if(Pparent.left == parent){
Pparent.left = subL;
}else{
Pparent.right = subL;
}
subL.parent = Pparent;
}
//修改平衡因子
subL.bf = 0;
parent.bf = 0;
}
2.4.2 左单旋
新节点插入较高右子树–左单旋
贴代码：
//左旋
public void rotateLeft(TreeNode parent){
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
parent.right = subRL;
subR.left = parent;
if(subRL != null){
subRL.parent = parent;
}
TreeNode Pparent = parent.parent;
parent.parent = subR;
if (parent == root) {
root = subR;
root.parent = null;
}else{
if(Pparent.left == parent){
Pparent.left = subR;
}else{
Pparent.right = subR;
}
subR.parent = Pparent;
}
subR.bf = 0;
parent.bf = 0;
}
2.4.3 左右双旋
//左右双旋
public void rotateLeftRight(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;
parent.bf = 1;
subL.bf = 0;
}else if(bf == 1){
subL.bf = -1;
parent.bf = 0;
subLR.bf = 0;
}
}
2.4.4右左双旋 
贴代码：
//右左双旋
public void rotateRightLeft(TreeNode parent) {
//先进行简单右旋，在进行简单左旋
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
int bf = subRL.bf;
rotateRight(parent.right);
rotateLeft(parent);
if (bf == -1) {
parent.bf = 0;
subRL.bf = 0;
subR.bf = 1;
} else if(bf == 1){
parent.bf = -1;
subR.bf = 0;
subRL.bf = 0;
}
}
2.5AVL树的验证
- 因为AVL树同时也是一个二叉搜索树，我们知道二叉搜索树的中序遍历之后可以得到一个有序序列，所以通过这个验证我们创建出来的AVL树是不是一个二叉搜索树。
- 因为AVL树同时也是一个二叉平衡树，在二叉平衡数中，左树的高度-右树的高度的绝对值要小于等于1，其实这也是leetcode上面的移到算法题。
//使用中序遍历，判断AVL树是不是二叉搜索树
public void in_order(TreeNode root){
if(root == null){
return;
}
in_order(root.left);
System.out.println(root.val);
in_order(root.right);
}
//得到一棵树的最大深度
public int getMaxHeight(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = getMaxHeight(root.left);
int rightHeight = getMaxHeight(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//判断AVL树是否为二叉平衡树
public boolean isBalance(TreeNode root){
if(root == null){
return true;
}
int leftHeight = getMaxHeight(root.left);
int rightHeight = getMaxHeight(root.right);
//在这个地方一定要进行判断，因为在二叉树中每个节点的平衡因子是我们手动给予的，所以可能会产生错误，在这里用树的高度之差进行验证
if(rightHeight - leftHeight != root.bf){
System.out.println("avl树存在异常");
System.out.println("异常节点为 " + root.val);
}
return Math.abs(leftHeight - rightHeight) <= 1 && isBalance(root.left) && isBalance(root.right);
}
public static void main(String[] args) {
AvlTree avlTree = new AvlTree();
int []array = {
16, 3, 7, 11, 9, 26, 18, 14, 15};
for(int i = 0;i<array.length;i++){
avlTree.insert(array[i]);
}
avlTree.in_order(avlTree.root);
for(int i = 0;i<array.length;i++){
avlTree.insert(array[i]);
}
System.out.println(avlTree.isBalance(avlTree.root));
}
运行结果：
2.6AVL树的删除
因为AVL树也是二叉搜索树，可以按照二叉搜索树的方式将节点删除，然后在更新平衡因子，只不过于删除不同的是，删除节点后的平衡因子要被更新，最差情况下一直要调整到根节点的位置。
- 找到需要删除的节点
- 按照搜索树的删除规则删除节点
- 更新平衡因子，如果出现了不平衡，进行旋转
2.7AVL树的性能分析
AVL树是一颗绝对平衡的二叉搜索树，器要求每个节点的左右子树的高度差都不超过1，这样可以保证查询是高效的时间复杂度。即log2N,但是如果要对AVL树做一些结果修改的操作，性能非常低下，比如：插入时要维护其绝对品恒，旋转的次数比较多，更差的是删除的时候，有可能一直要让旋转持续到根节点的位置，因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变),可以考虑AVL树，但一个结构经常修稿，就不太适合。
转载：https://blog.csdn.net/qq_54883034/article/details/125691854