数据结构在自考的时候学过,所以一些简单的概念大概了解，但是必定考纲不一样，所以在软考中还是会有一些陌生的知识，现在就说一下平衡二叉树

一、什么是平衡二叉树

      根据二叉树的基本概念可想到：平衡二叉树的左右子树都是平衡二叉树；除此之外，左子树和右子树的高度差的绝对值不能超过1

二、平衡二叉树的作用

     因为在二叉排序树查找过程中，只有树的形态比较均匀的时候，查找效率才能比较好，因此采用平衡二叉树可以使得在构造二叉排序树的时候使得其保持均匀，从而可以提高查找效率；所以平衡二叉树一定是二叉排序树。

三、平衡二叉树的插入

    插入的情况分为四类：左子树的左子树插入，右子树的右子树插入，左子树的右子树插入，右子树的左子树插入；根据四种插入的情况，有四种调整平衡的规律，归纳如下：

（1）单向右旋(针对于左子树的左子树插入结点点1)

（2）单向左旋(针对于右子树的右子树插入结点5)

（3）先左后右双向旋转（针对于左子树的右子树插入结点3）

（4）先右后左双向旋转(针对于右子树的左子树插入结点18)

四、平衡二叉树的删除

        平衡二叉树的删除同二叉排序树的删除是一样的，但是需要在二叉排序树的基础上保持平衡。

（1）删除叶子结点

          直接删除即可，然后进行平衡调整

（2）删除只有一个子树的结点

         用要删除结点的左子树（右子树）代替删除结点，直接删除即可，然后进行平衡调整

（3）删除有两个子树的结点

        这种情况比较复杂，可分两种情况进行删除操作：

       a.如果该节点的平衡因子为0或者1，则找到其左子树中具有最大值的节点max（中序遍历的直接前驱）将max的内容与x的内容交换，并且max即为新的要删除的节点

      b.如果该节点的平衡因子为-1，则找到其右节点中具有最小值的节点min（中序遍历的直接后继），将min的内容与x的内容交换，并且min即为新的要删除的节点。

       不要忘记删除后要进行平衡调整。