鲁达 平衡二叉树对于初学者一直是一个比较复杂的知识点，因为其里面涉及到了大量的旋转操作。把大量的同学都给转晕了。这篇文章最主要的特点就是通过动画的形式演示。确保大家都能看懂。最后是手写一个平衡二叉树。
一、概念
平衡二叉树是外国的两个大爷发明的。一开始发明的是二叉查找树。后来觉得不给力演化成了平衡二叉树。那什么是二叉查找树呢？我们给出一张图来看看：
看到这张图我们就会发现如下的特征。从每个节点出发，左边的节点一定小于右边的。但是你会发现这可以高低不平，看起来很不美观。于是慢慢的演化成了平衡二叉树。（当然不是因为美观演化的）。也就是说平衡二叉树的前提就是一颗二叉查找树
平衡二叉树定义(AVL)：
（1）它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，
（2）它的左子树和右子树都是一颗平衡二叉树。
也就是说以上两条规则，只要破坏了一个就不是平衡二叉树了。比如说下面这张图。
上面这张图就是破坏了二叉查找树这一条规则。当然了还有一条规则。也就是他的高度只差不能超过1
现在相信我们已经明白了什么是平衡二叉树。下面我们就来看看平衡二叉树的增删改查操作是怎么样的。
二、平衡二叉树的插入操作
我们先从最简单的入手，一步一步来。
1、右旋
首先我们插入几个数字，50,45,44。通过动画我们来演示一遍
（1）插入50根节点不会出现任何操作
（2）插入45，往左边插入即可
（3）插入44，破坏了平衡，于是右旋。
2、左旋
我们插入几个数字，50,60,70。通过动画我们来演示一遍
（1）插入50根节点不会出现旋转
（2）插入60，往右边插入即可
（3）插入70，破坏了平衡，于是左旋。
3、先右旋再左旋
我们依次插入50,60,55.通过动画我们演示一遍
（1）插入55,根节点，不会出现旋转
（2）插入60，往右边插入
（3）插入55，破坏了平衡，于是先把55和60右旋，然后整体左旋。
4、先左旋后右旋
我们依次插入50,40,45.通过动画我们演示一遍。
（1）插入55,根节点，不会出现旋转
（2）插入40，往左边插入
（3）插入45，破坏了平衡，于是先把45和40左旋，然后整体右旋。
现在我们基本上已经把插入的几种情况罗列出来了。现在我们画一张图，来一个总结。
上图对于每一种情况，从上往下看就好了。对于平衡二叉树的删除操作，其实也是同样的道理，找到相应的元素之后，对其进行删除，删除之后如果破坏了平衡，只需要按照上面的这几种情况进行调整即可。下面我们来分析一下平衡二叉树的查找操作。
三、平衡二叉树的查找
平衡二叉树的查找很简单，只需要按照二叉查找树的顺序执行就好。我们使用一张动画演示一下：
现在平衡二叉树的操作相信你已经能够理解。下面我们就来关注最后一个问题，那就是如何手写一颗平衡二叉树呢？
四、手写一颗平衡二叉树
平衡二叉树的代码操作，难点在于旋转。只要把旋转弄清楚基本上整个树就能完成了，根据上面旋转的特点我们从零开始定义一颗。
第一步：定义节点
第二步：插入数据
第三步：左旋和右旋的调整
1、右旋
2、左旋
第四步：计算平衡和深度
1、计算平衡
2、计算深度
看起来代码有些多，其实梳理一下就不多了。
（1）首先定义一个节点，里面有get和set方法，构造函数等等做准备工作
（2）直接写业务流程，比如说这里的insert操作，里面涉及到的旋转操作先用方法代替
（3）对主业务流程的操作，缺哪一个方法，写哪一个方法即可