二叉树查询性能分析： 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索在二叉搜索树树平均查找长度是结点的深度的函数，即结点越深，则比较次数越多 如图：
下面就是对二叉搜索树的改进AVL树
目录：
一.AVL树的概念 二.AVL树的实现 三.AVL树的验证 四.AVL树的删除（了解） 五.AVL树的性能分析
一. AVL树的概念:
1. 二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺 序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种 解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点旋转)，即可降低树的高度，从而减少平均搜索长 2. 这个我们要定义一个平衡因子，平衡因子 = 右树高度 - 左树高度。 3. 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 搜索时间复杂 度(Log2^N)。
二 AVL树的实现：
1. 为了AVL树实现简单，AVL树节点在定义时维护一个平衡因子，具体节点定义如下：
代码语言：javascript复制public class AVLTree {
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;2.AVL树的插入：
2.1. 按照二叉搜索树的方式插入新节点 2.2. 调整节点的平衡因子 根据平衡因子可以分为几种情况： 情况一：Parent的平衡因子为 0，已经平衡无需调整； 情况二：Parent的平衡因子为 1,-1，继续向上调整； 情况三：Parent的平衡因子为 2，cur的平衡因子为1 ,左单旋（同号） 情况四：Parent的平衡因子为 2，cur的平衡因子为-1 ，右左双旋（异号） 情况五：Parent的平衡因子为 -2，cur的平衡因子为-1 , 右单旋（同号） 情况六：Parent的平衡因子为 -2，cur的平衡因子为 1 , 左右双旋（异号）
代码：
代码语言：javascript复制 //插入：
public boolean insert(int val) {
TreeNode node = new TreeNode(val);
if(root == null){
root = node;
return true;
}
TreeNode cur = root;
TreeNode parent = null;
while (cur != null){
if(cur.val < val){
parent = cur;
cur = cur.right;
}else if(cur.val > val){
parent = cur;
cur = cur.left;
}else {
return false;
}
}
if(parent.val < val){
parent.right = node;
}else{
parent.left = node;
}
node.parent = parent;
cur = node;//指向新插入的节点
//修改平衡因子
while (parent != null) {
//先看cur在parent的左边还是右边
if (cur == parent.right) {
//如果在右边就
parent.bf ;
} else {
//如果在左边就--
parent.bf--;
}
//检查当前的平衡因子是不是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 {
//cur.bf == -1
//右左双旋：
rotateRL(parent);
}
}else {
//parent.bf == -2//左树高-》降低左树高度
if(cur.bf == -1){
//右单旋
rotateRight(parent);
}else {
//cur.bf == 1
//左右双旋：
rotateLR(parent);
}
}
//已经平衡
break;
}
}
return true;
}3.AVL树的旋转：
3.1. 新节点插入较高左子树的左侧---右单旋 ： Parent的平衡因子为 -2，cur的平衡因子为-1 , 右单旋（同号） 图解：
代码：
代码语言：javascript复制 /**
* 右单旋
* @param parent
*/
private void rotateRight(TreeNode parent){
TreeNode subL = parent.left;
TreeNode subRL = subL.right;
parent.left = subRL;
subL.right = parent;
//如果旋转的整棵树也是一个子树，记录下原来该树的父亲，后续修改
TreeNode pParent = parent.parent;
if (subRL != null) {
subRL.parent = parent;
}
parent.parent = subL;
//看看整棵树是否也是一个子树
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;
}3.2. 新节点插入较高右子树的右侧---左单旋： Parent的平衡因子为 2，cur的平衡因子为1 ,左单旋（同号） 图解：
代码：
代码语言：javascript复制/**
* 左单旋
* @param parent
*/
private void rotateLeft(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
parent.right = subRL;
subR.left = parent;
TreeNode pParent = parent.parent;
if(subRL != null){
subRL.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;
parent.bf = 0;
subR.bf = 0;
}3.3. Parent的平衡因子为 -2，cur的平衡因子为 1 , 左右双旋（异号）： 图解：subLR的平衡因子区分情况 情况一：subLR平衡因子等于-1
情况二：subLR平衡因子等于1
代码：
代码语言：javascript复制 /**
*左右双旋：
* @param parent
*/
private void rotateLR(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
int bf = subLR.bf;
rotateLeft(parent.left);
rotateRight(parent);
//双旋时subLR的值-1,1，会有2种插入方式
if(bf == -1){
subL.bf = 0;
subLR.bf = 0;
parent.bf = 1;
}else if(bf == 1){
subL.bf = -1;
subLR.bf = 0;
parent.bf = 0;
}
}4. Parent的平衡因子为 2，cur的平衡因子为-1 ，右左双旋（异号）： 图解： 情况一：subRL平衡因子等于1
情况二：subRL平衡因子等于-1
代码：
代码语言：javascript复制 /**
*右左双旋：
* @param parent
*/
private void rotateRL(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
int bf = subRL.bf;
rotateRight(parent.right);
rotateLeft(parent);
//双旋时subRL的值-1,1，会有2种插入方式
if(bf == 1){
parent.bf = -1;
subRL.bf = 0;
subR.bf = 0;
}else if(bf == -1){
parent.bf = 0;
subRL.bf = 0;
subR.bf = 1;
}
}三.AVL树的验证:
分两步:
1. 验证其为二叉搜索树:
代码：
代码语言：javascript复制//中序遍历：
public void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left);
System.out.println(root.val);
inorder(root.right);
}
//求高度
private int height(TreeNode root){
if(root == null){
return 0;
}
int leftH = height(root.left);
int rightH = height(root.right);
return Math.max(leftH,rightH) 1;
}2. 验证其为平衡树:
代码语言：javascript复制 //判断树是否为平衡二叉树
public boolean isBalanced(TreeNode root){
if (root == null) return true;
int leftH = height(root.left);
int rightH = height(root.right);
/**检查这棵树平衡因子是否本身就出错
* 因为要验证的这棵树的平衡因子，是我们自己定义的，防止出错。
*/
if(rightH-leftH != root.bf){
System.out.println("这个节点" root.val "平衡因子异常");
return false;
}
return Math.abs(leftH-rightH) < 2
&& isBalanced(root.left)
&& isBalanced(root.right);
}四.AVL树的删除（了解）:
1、找到需要删除的节点 2、按照搜索树的删除规则删除节点--参考Map和Set及哈希--的奥秘（详解）-CSDN博客中二叉搜索树的删除 3、更新平衡因子，如果出现了不平衡，进行旋转。--单旋，双旋
五.AVL树性能分析:
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询 时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要 维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要 一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修 改，就不太适合
