在上一篇博客中实现了二叉排序树。我们发现，查找的效率取决于树的高度。比如对于{62,88,58,47,35,73,51,99,37,93}这样的数组，利用上一篇博客实现的插入，得到的二叉排序树为:

但当我们改变一下数组中元素的顺序，比如改成{35,37,47,51,58,62,73,88}，那得到的二叉排序树就为：

不难看出，这时的二叉排序树退化成了一个线性表。这时已经完全没有了二叉排序树的优势。次吃的解决方案是就是尽量让树的高度降低，那就要求树的左右孩子的高度尽可能相近，即树要尽可能平衡。

一、相关定义

• 1.平衡二叉树： 是一种二叉排序树， 其中每个节点的左右子树的高度差至多等于1。这里有两个地方要注意：第一，平衡二叉树首先是一颗二叉排序树；第二，每个节点的左右子树高度差要么是0，要么是1。
• 2.平衡因子： 为了描述节点的左右子树差，我们将二叉树上节点的左子树高度减去右子树高度得到的值称为该节点的平衡因子。根据二叉树的定义，每个节点的平衡因子为-1,0,1三个中的一个。
• 3.最小不平衡子树： 距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树， 称为最小不平衡子树。如下所示的二叉排序树，当插入35时，58的左子树高度为2，右子树高度为0，该树变不平衡，因此以节点58为根的子树为最小不平衡子树。
  

二、平衡调整

从上面的图可以看出，要让不平衡的二叉排序树重新平衡，就需要对最小不平衡子树进行调整，使其平衡。有四种调整方式：LL型、RR型、LR型、RL型。在月雲之霄 大佬的博客中，对这四种调整讲的相当清楚了，我这里将月雲之霄 大佬的博客中的图整理成一张图（本文重点讲解删除的各种情况，插入的情况可以先去看看月雲之霄大佬的博客，讲的可以说非常好了），用来解释调整情况：

三、节点插入

通过上面的图示，我们知道LR和RL是LL和RR的组合情况。知道了这个，我们在插入节点的时候，从上往下，利用递归，插入后，判断插入过程路径上的节点的平衡因子，当平衡因子大于1或小于-1时，就去调整该接节点（根据递归的特性，在寻找插入点位置时，是从上到下的，那在判断平衡因子时，就是从下往上的，这样其实调整的肯定就是最小不平衡子树了）。在月雲之霄 大佬的博客中对插入讲的相当详细了，我这里就不赘述了，可以详细看一遍大佬的博客，肯定能理解。我们来看月雲之霄 大佬没讲的节点删除的情况。

四、节点删除

我感觉节点删除是平衡二叉树中最难的部分了，它其实分为6中情况，除了LL型和RR型两种调整情况，LR型和LR型这两种情况，每种都要考虑是在左子树还是右子树上进行的，所以其实一共有LL、RR、LLR（左子树上的LR型调整）、RLR（右子树上的LR型调整）、LRL（左子树上的RL型调整）、RRL（右子树上的RL型调整）。我们来分别讲解。

1.LL型