在之间介绍数据结构的文章中我们介绍过二叉树查找，如果忘记的大家可以查看下这篇文章数据结构-树的那些事(四)，这里对二叉树就不做介绍，我们来说一下二叉排序树；
二叉排序树(Binary Search Tree):又被称为二叉查找树或者二叉搜索树，当然首先是二叉树，另外特点如下：
1.若它的左子树不为空，则左子树的结点小于它根节点的值；
2.若它的右子树不为空，则右子树的结点大于它根节点的值；
3.它的左、右子树也分别为二叉排序树；
明白特点接下来我们来说一下查找的性能，二叉排序树查找性能取决于二叉树的形状，但是二叉树排序的形状是不确定，最坏的情况查找性能为O(n)，最好情况查找性能为O(logn)，如下图
接下来我们谈一下二叉排序树的增加和删除操作，查询就没必要说明，就写下代码实现下就好；
增加操作:
1.若当前的二叉树排序树为空，则插入元素的根节点；
2.若插入的值小于根节点，则插入到左子树当中；
3.若插入的值大于根节点，则插入到右子树当中；
删除操作：
1.若删除的是子节点，则直接删除该结点；
2.若删除的节点仅有左或者右子树的结点，则让该结点的子树与父亲节点相连，删除该结点即可；
3.若删除的节点左子树和右子树都有子结点，如下面两幅图，这里面强调一下第二幅图，删除47以后用37或者48都可以满足二叉排序树，这里我们为什么选择47而要放弃37，是因为二叉排序树按照中序遍历以后形成的是一个有序序列(由小到大排序)，选择37以后不满足这个特征；
上面我们谈到二叉排序树性能问题，接下来我们来说一下平衡二叉树看如何处理二叉树性能问题，所有代码在介绍完成以后提供实现；
平衡二叉树(AVL树):首先平衡二叉树是一颗二叉树排序树，他的特点是每一个节点左子树和右子树的高度差至多等于1,这样就能避免照成单枝树，影响查询效率,来个看图识AVL树，下图中图二满足二叉排顺序树的特征，58节点的左子树大于59，图三58的左子树的高度为2，右子树的高度为0，高度差大于1，所以不满足平衡二叉树，接下来我们谈谈平衡二叉树插入和删除照成失衡以后的操作(平衡二叉树的旋转)。
失衡以后操作:
失衡以后可能造成4种情况:LL(左左)、RR(右右)、LR(左右)、RL(右左)，接下来我们用图说话,看一下这4种情况；
对这4种情况进行统一整理就是：插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。就用第一种说一下当插入D的时候导致，导致5左子树的高度为3，5的右子树为1，差值大于1，这个时候我们抓住3，使5进行右旋，3的右孩子变成5的左孩子这个时候平衡达成。
这里简单讲一下对应结点的抽象，不同于二叉树的情况就是这里要增加一个高度的属性，好用来判断左子树和右子树的差值；