比如有这么一个数组：{1,2,3,4,5,6}，对应的二叉排序树存在一个问题。如下图

1. 左子树全部为空，从形式上看，更像是一个单链表
2. 插入速度没有影响
3. 查询速度明显降低（因为需要依次比较），不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
4. 解决方案就是平衡二叉树（AVL）

   简介

   平衡二叉树也叫平衡二叉排序搜索树，又被称为AVL树，可以保证查询效率较高。
   AVL树具有的特点：它是一颗空树或者它的左右两个子树的高度差值的绝对值不能超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用实现方法有红黑树，AVL，替罪羊树，Treap，伸展树等。

如下三棵树

插入节点失去平衡

上图中节点 66 的左子树高度为 1，右子树高度为 3，此时平衡因子为 -2，树失去平衡。
以节点 66 为父节点的那颗树就称为 最小失衡子树

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。
平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋 与 右旋 。
旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

平衡二叉树旋转

在插入完节点后，发现不再是一棵AVL树，这时候就要进行旋转

平衡二叉树左旋转

思路

1. 当右子树的高度-左子树的高度>1时就要进行左旋转
2. 创建一个新的节点，这个节点的值等于当前节点
3. 把新节点的左子树设置为当前节点的左子树
4. 把新节点的右子树设置为当前节点的右子树的左子树
5. 把当前节点的的值替换为右子节点的值
6. 把当前节点的右子树设置成右子树的右子树
7. 把当前节点的左子树设置为新的节点

   图解

平衡二叉树右旋转

思路

1. 当左子树的高度-右子树的高度>1时，就要进行右旋转
2. 创建一个新的节点，以当前节点的值
3. 把新节点的右子树设置为当前节点的右子树
4. 把新节点的左子树设置为当前节点的左子树的右子树
5. 把当前节点的值换为左子节点的值
6. 把当前节点的左子树设置为左子树的左子树
7. 把当前节点的右子树设置为新的节点

   图解

平衡二叉树双旋转

如图
图1右旋转后得到图2，还是不平衡。这种情况就要双旋转。

思路

1. 当符合右旋转的条件时
2. 如果它的左子树的右子树高度大于它的左子树的左子树高度
3. 先对当前这个节点的左子节点进行左旋转
4. 再对当前节点进行右旋转的操作
5. 当符合左旋转的条件时，和上面的2，3，4步骤相反，思路顺序是一样的

代码

平衡二叉树就是二叉排序树，升级版

using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApp1
{
    public class AVLTree
    {
        public Node root;
        //添加
        public void add (Node node)
        {
            if (root == null)
                root = node;
            else
                root.add(node);
        }
        //中序遍历
        public void infixOrder()
        {
            if (root == null)
            {
                Console.WriteLine("二叉树为空");
                return;
            }
            root.infixOrder();     
        }
        //查找要删除的节点
        public Node search(int val)
        {
            if (root == null)
                return null;
            else
                return root.search(val);
        }
        //查找要删除节点的父节点
        public Node searchParent(int val)
        {
            if (root == null)
                return null;
            else
                return root.searchParent(val);
        }
        //删除右边节点的最小的一个节点
        //返回以node为根节点的二叉排序树的最小节点的值，并且删除这个节点
        public int delRightTreeMin(Node node)
        {
            Node target = node;
            while (target.left != null)
            {
                target = target.left;
            }
            //这是target就指向了最小的节点
            //删除这个最小节点,并且返回这个节点的值
            delNode(target.id);
            return target.id;
        }
        //删除节点
        public void delNode(int val)
        {
            if (root == null)
                return;
            else
            {
                //找要删除的节点target和它的父节点parent
                Node target = search(val);
                if (target == null)//都没有找到要删除的节点，下面的代码也不用执行了
                    return;
                //如果这个二叉树只有一个节点
                if (root.left == null && root.right == null)
                {
                    root = null;
                    return;
                }
                Node parent = searchParent(val);
                //要删除的节点是叶子节点
                if (target.left == null && target.right == null)
                {
                    if (parent.left == target)
                        parent.left = null;
                    if (parent.right == target)
                        parent.right = null;
                }
                //如果要删除的节点有两棵子树
                else if (target.left != null && target.right != null)
                {
                    int minval = delRightTreeMin(target.right);
                    target.id = minval;
                }
                //要删除的节点只有一棵子树
                else
                {
                    if(target.left!=null)//要删除的节点有左子树
                    {
                        if (parent != null)
                        {
                            if (parent.left == target)
                                parent.left = target.left;
                            if (parent.right == target)
                                parent.right = target.left;
                        }
                        else
                            root = target.left;
                    }
                    else//要删除的节点有右子树
                    {
                        if (parent != null)
                        {
                            if (parent.left == target)
                                parent.left = target.right;
                            if (parent.right == target)
                                parent.right = target.right;
                        }
                        else
                            root = target.right;
                    }
                }
            }
        }
    }
    public class Node
    {
        public int id;
        public Node left;
        public Node right;
        public Node(int id)
        {
            this.id = id;
        }
        //返回以当前节点为根节点的树的高度
        public int height()
        {
            return Math.Max(left == null ? 0 : left.height(), right == null ? 0 : right.height())+1;//+1本身节点也要算一层
        }
        //返回左子树的高度
        public int leftHeight()
        {
            if (left == null)
                return 0;
            return left.height();
        }
        //返回右子树的高度
        public int rightHeight()
        {
            if (right == null)
                return 0;
            return right.height();
        }
        //左旋转
        public void leftRotate()
        {
            //创建新的节点，以当前节点的值
            Node newnode = new Node(this.id);
            //把新的节点的左子树设置成当前节点的左子树
            newnode.left = this.left;
            //把新的节点的右子树设置成当前节点的右子树的左子树
            newnode.right = this.right.left;
            //把当前节点的值替换成右子节点的值
            this.id = this.right.id;
            //把当前节点的右子树设置成右子树的右子树
            this.right = this.right.right;
            //把当前节点的左子树设置成新的节点
            this.left = newnode;
        }
        //右旋转
        public void rightRotate()
        {
            //创建一个新的节点，以当前节点的值
            Node newnode = new Node(this.id);
            //新节点的右节点设置为当前节点的右节点
            newnode.right = this.right;
            //新节点的左节点设置为当前节点的左节点的右节点
            newnode.left = this.left.right;
            //把当前节点的值改成左子节点的值
            this.id = this.left.id;
            //当前节点的左子树设置为左子树的左子树
            this.left = this.left.left;
            //将当前节点的右子节点设置成新的节点
            this.right = newnode;
        }
        //二叉排序树添加
        public void add(Node node)
        {
            if (node == null)
                return;
            //判断传入的节点的值，和当前子树的根节点的关系
            if (node.id < this.id)
            {
                //如果当前的左子节点为null
                if (this.left == null)
                    this.left = node;
                else
                    this.left.add(node);//递归向左子节点添加
            }
            else
            {
                if (this.right == null)
                    this.right = node;
                else
                    this.right.add(node);//递归向右节点添加
            }
            //当添加完成一个节点以后，如果：(右子树的高度-左子树的高度)>1,左旋转
            if (rightHeight() - leftHeight() > 1)
            {
                //如果它的右子树的左子树高度大于它的右子树的右子树高度
                if (right != null && right.leftHeight() > right.rightHeight())
                {
                    //先对当前节点的右节点进行右旋转
                    right.rightRotate();
                    //再对当前节点进行左旋转
                    leftRotate();
                }
                else
                {
                    //直接进行左旋转
                    leftRotate();
                }
                //因为是加一个数处理一个数，这里已经处理完了，树已经平衡了，就返回
                //不用执行下面的了没有意义
                return;
            }
            //当添加完一个节点后，如果：(左子树的高度-右子树的高度)>1,右旋转
            if (leftHeight() - rightHeight() > 1)
            {
                //如果它的左子树的右子树高度大于它的左子树的左子树高度
                if (left != null && left.rightHeight() > left.leftHeight())
                {
                    //先对当前节点的左节点进行左旋转
                    left.leftRotate();
                    //再对当前节点进行右旋转
                    rightRotate();
                }
                else
                {
                    //直接进行右旋转
                    rightRotate();
                }
            }
        }
        //中序遍历
        public void infixOrder()
        {
            //1.如果当前节点的左子节点不为空，则递归继续中序遍历
            if (this.left != null)
                this.left.infixOrder();
            //2.输出当前节点
            Console.WriteLine(this.id);
            //3.如果当前节点的右子节点不为空,则递归继续中序遍历
            if (this.right != null)
                this.right.infixOrder();
        }
        //查找节点
        public Node search(int val)
        {
            if (val == this.id)
                return this;
            else if (val < this.id)
            {
                if (this.left == null)
                    return null;
                return this.left.search(val);
            }
            else
            {
                if (this.right == null)
                    return null;
                return this.right.search(val);
            } 
        }
        //查找要删除节点的父节点
        public Node searchParent(int val)
        {
            //如果当前节点就是要删除的节点的父节点，就返回
            if (this.left != null && this.left.id == val || this.right != null && this.right.id == val)
                return this;
            else
            {
                if (val < this.id && this.left != null)//左递归
                    return this.left.searchParent(val);
                else if (val >= this.id && this.right != null)//右递归
                    return this.right.searchParent(val);
                else//没有父节点
                    return null;
            }
        }
    }
}