平衡二叉树和二叉排序树并没有直接的关系，但是二叉排序树的查找效率与二叉树的形态有关，所有当我们希望二叉排序树的形态是均匀的时候，这样的二叉树就被称为平衡二叉树。
 

 
1. 二叉排序树
 
二叉排序树(Binary Sort Tree)，又称二叉查找树(Binary Search Tree)，亦称二叉搜索树。二叉排序树定义：
 
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
 
若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
 
左、右子树也分别为二叉排序树。
 
如图下图所示就是一棵二叉排序树：
 

 
对二叉排序树进行中序遍历，便可得到一个按关键字排序的序列，如对上图进行一次中序遍历可得到一个有序序列：10，42，45，55，58，63，67，70，83，90，98二叉排序树的查找分析
 
就查找的平均时间性能而言，二叉排序树上的查找与折半查找类似，但就维护表的有序性而言，二叉排序树更高效，因为它无需移动节点，只需修改指针即可完成二叉排序树的插入和删除操作。
 
二叉排序树查找在在最坏的情况下，需要的查找时间取决于树的深度：当二叉排序树接近于满二叉树时，其深度为log2nlog_2nlog2n ,因此最坏情况下的查找时间为O(log2nlog_2nlog2n)，与折半查找是同数量级的。
 
当二叉树如下图所示形成单枝树时，其深度为n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。
 

 
所以为了保证二叉排序树查找有较高的查找速度，希望该二叉树接近于满二叉树，或者二叉树的每一个节点的左、右子树深度尽量相等
 
2. 平衡二叉树
 
通过上面的分析可知，二叉排序树的查找效率与二叉树的形态有关，我们希望二叉排序树的形态是均匀的，这样的二叉树称为平衡二叉树。平衡二叉树定义
 
平衡二叉树(Balanced Binary Tree)，它是一棵空树，或者是具有以下性质：它的左右两个子树的深度差的绝对值不超过1；
 
它的左右两个子树也分别是平衡二叉树。
 
将二叉树节点的左子树的深度减去它的右子树的深度称为平衡因子BF，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1，如下图左边的为平衡二叉树，右边的为非平衡二叉树。
 

 
因为平衡二叉树上任何节点的左、右子树的深度之差都不会超过1，可以证明它的深度和n个节点的完全二叉树的深度⌊log2n⌋\lfloor log_2n \rfloor⌊log2n⌋+1是同数量级的。因此，它的平均查找次数也是和⌊log2n⌋\lfloor log_2n \rfloor⌊log2n⌋+1同数量级的。
 
要构造一棵平衡二叉树，Georgii M. Adelson-Velskii 和 Evgenii M. Landis 提出了一种动态保持二叉平衡树的方法，其基本思想是：在构造二叉排序树的时候，每当插入一个节点时，先检查是否因插入节点而破坏了树的平衡性，如果是，则找出其中最小不平衡子树，在保持排序树的前提下，调整最小不平衡子树中各节点之间的连接关系，以达到新的平衡，所以这样的平衡二叉树简称AVL树。其中最小平衡子树是指：离插入节点最近，且平衡因子绝对值大于1的节点作为根节点的子树。调整最小不平衡子树一般有四种情况：单向右旋(LL型)： 插入位置为左子树的左子树，以左子树为轴心，进行单次向右旋转，如下图所示。节点旁边的数字为该节点的平衡因子，I节点为当前插入节点(如果I节点处于正中，则表示I节点既可以是左孩子也可以是右孩子。
 
注意LL型，以中间节点为轴心进行旋转。为什么这里I为BL左孩子不能将B-BL-I作为LL型，是因为A节点才是离I节点最近的平衡因子绝对值>1的子树，其余节点的平衡因子绝对值都没有超过1；同理当I为BL右孩子，也不能将B-BL-I作为LR型。
 

 
2. 单向左旋(RR型)： 插入位置为右子树的右子树，右子树为轴心，进行单次向左旋转
 
注意RR型，以中间节点为轴心进行旋转。这里I为左右子树并不影响其实RR型，原理同上。
 

 
3. 双向旋转先左后右(LR型)：插入位置为左子树的右子树，要进行两次旋转，先向左旋转，再向右旋转。
 
插入节点为左孩子：注意为什么不能B-C-I作为子树将其定为RL型，原理同RR型中的解释，对于LR型，，是以R端或者L靠近插入节点端作为旋转轴心(如下图相当于先旋转以B为根的子树后，成为了LL型，再旋转以A为根的子树)。
 

 
插入节点为右孩子：
 

 
4. 双向旋转先右后左(RL型)：插入位置为右子树的左子树，进行两次调整，先右旋转再左旋转；处理情况与LR类似。
 
插入节点为左孩子：
 

 
插入节点为右孩子：
 

 
经过上面的我们可以发现，平衡因子与类型有很大的关系，需要以离插入节点最近且平衡因子绝对值>1的节点作为根节点的子树进行判定是哪种类型。练习
 
如下图所示，先插入节点2后，成为LL型，然后整体右旋处理后平衡。
 

 
再依次插入8和6之后，节点5的平衡因子绝对值>1，成为RL型，所以先以5为根节点，将其子树8-6右旋(成为RR型)，然后将5为根节点的整棵树再左旋。
 

 
继续插入节点9后，节点4的平衡因子>1，成为RR型，所以以4为根节点，将整体左旋。
 

二叉排序树的定义： 
 （1）若它的左子树不为空，则左子树所有结点均小于它的根结点的值； 
 （2）若它的右子树不为空，则右子树所有结点均大于它的根结点的值； 
 （3）它的左右子树都是二叉排序树。
 
平衡二叉树本质上是二叉排序树。 
 平衡二叉树的性质： 
 （1）根结点的左子树和右子树的深度最多相差1。 
 （2）根结点的左子树和右子树叶都是一棵平衡二叉树。
 
平衡二叉树查找关键字是否存在？ 
 解析思路： 
 （1）先根据结点个数计算平衡二叉树深度，根据深度将不符合要求的排除 
 计算过程如下： 
 ni表示深度为h的平衡二叉树中含有的最少结点数，有n0=0，n1=1,n2=2; 
 计算公式为： 
 递归的计算平衡二叉树中含有的最少结点数。 
 （2）根据平衡二叉树的性质，选择符合要求的选项 
 性质：若存在左子树则左子树小于根结点，若存在右子树则右子树大于根结点。
 
实例： 
 1、在含有15个结点的平衡二叉树上，查找关键字为28（存在该结点）的结点，则依次比较的关键字可能是（）。 
 A.30,36 
 B.38,48,28 
 C.48,18,38,28 
 D.60,30,50,40,38,36 
 答案：C 
 解析如下： 
 n0=0，n1=1，n2=2， 
 n3=n2+n1+1=4 
 n4=n3+n2+1=7 
 n5=n4+n3+1=12 
 n6=n5+n4+1=20>15
 
高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树高度为5，而最小的叶子结点的层数为3.
 
 
 如上图所示，根据D的元素构成的二叉树深度为6，显然不合要求； 
 A在查找30后应该指向左孩子，而不是右孩子；B的错误同样。
 
而C的查找路径，如下图所示： 
  
 [上图的来源] 
 (https://www.ppkao.com/daan/7007317/255767F11A95606E51099B40301AF0F3)
 
2、在含有14个结点的平衡二叉树上，查找关键字为40的结点，则依次比较的关键字可能是（） 
 A.27,48,25,43,40 
 B.47,45,18,27,36,40 
 C.46，42，18，20，28，40 
 D.15.45.40 
 答案：D
 
解析如下： 
 n0=0，n1=1，n2=2， 
 n3=n2+n1+1=4 
 n4=n3+n2+1=7 
 n5=n4+n3+1=12 
 n6=n5+n4+1=20>14 
 因此平衡二叉树的高度为5. 
 如下图所示： 
 各选项构成的二叉树如下：
 
 
显然，A选项中蓝色圆圈的25元素比根结点27小，不符合平衡二叉树的定义。 
 B,C选项的树高均为6，不满足平衡二叉树的深度为5的要求。 
 D选项符合要求。

 
文章目录
 
1、什么是二叉树(Binary Tree)
2、二叉树的存储方式
3、二叉树的遍历
4、二叉查找树(Binary Search Tree)
4.1 查找操作
4.2 插入操作
4.3 删除操作
  
5、平衡二叉树(AVL Tree)

 
1、什么是二叉树(Binary Tree)
 
  二叉树是一种特殊的树，之前我们所讲的数据结构都是线性结构，今天说的二叉树就是一种非线性结构的数据结构。它是具有如下特点的树：其一，每个结点最多只有两棵子树（也就是二叉树中不存在结点的度大于2的结点）；其二，二叉树的子树具有左右之分，而且顺序不能颠倒。这里我不会对树的概念以及二叉树的概念做太多的赘述，如果不了解请您可以先查查关于更多树和二叉树的定义和性质。
   二叉树具有以下性质：（1）在二叉树的第 i 层上最多有2^(i - 1)个结点；（2）深度为 k 的二叉树最多有(2 ^ k) -1 个结点；（3）对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1;
   这里我们看看满二叉树的概念，一棵深度为k且有(2 ^ k) -1个结点的二叉树为满二叉树。 如果我们约定给满二叉树从上到下，从左到右依次编号，那么当且仅当深度为k的二叉树的所有结点都能与满二叉树的编号一一对应，我们说这棵二叉树是完全二叉树。
 
 
2、二叉树的存储方式
 
  二叉树的存储方式有两种，一种是顺序存储方式，一种是链式存储方式。所谓顺序存储方式就是用连续地址的内存来存储二叉树也就是数组。
   基于数组的存储方式，对于完全二叉树比较友好，但是对于非完全二叉树而言就比较浪费内存空间。我们记根结点的数组索引下标为 i ，因此，其左子树根结点下标就为2 * i，右子树根结点的下标索引为 2 * i + 1，依次类推，当遇到某个结点的子树为空时，这个结点对应的索引的数组就为空。因此当二叉树为非完全二叉树会造成数组过于稀疏，从而浪费存储空间，例如
 
   对于非完全二叉树我们一般采用链式存储方式，链式存储方式就是使用链表的方式将二叉树中的结点连接起来。每个结点有两个指针域，分别指向左子树和右子树。
 
 
3、二叉树的遍历
 
  我们从定义可以看出其实二叉树是一种递归定义的结构，因此我们在遍历的时候也可以递归进行。一般来讲二叉树的遍历有三种方式：前序遍历，中序遍历，后序遍历
 （1）前序遍历：先访问根结点，前序遍历左子树，前序遍历右子树；
 （2）中序遍历：中序遍历左子树，访问根结点，中序遍历右子树；
 （3）后序遍历：后序遍历左子树，后序遍历右子树，访问跟结点；
 
 如图所示的二叉树:
 其先序遍历结果为：A,B,D,E,H,I,J,K,C,F,G
 其中序遍历的结果为：D,B,H,E,J,I,K,A,F,C,G
 其后序遍历结果为：D,H,J,K,I,E,B,F,G,C,A
   对于二叉树的遍历主要就是理解它的递归过程，通过写递归公式，这样就很简单地写出代码,其遍历的时间复杂度为O(n)：
 
// 三种遍历方式的代码
void preOrder(Node* root) {
  if (root == null) return;
  visit(root);	// 访问结点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  visit(root);
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  visit(root);
}
 
4、二叉查找树(Binary Search Tree)
 
  二叉查找树又称为二叉排序树，它的定义如下：二叉查找树是一棵空树或者是具有如下性质的二叉树：（1）若它的左子树不为空，则左子树上所有结点的值均小于根结点；（2）若它的右子树不为空，则它的右子树的所有结点均大于根结点；（3）它的左子树和右子树也分别为二叉查找树
 
 
4.1 查找操作
 
 
  根据二叉查找树的定义，现在我们给定一个数据对象的关键字key，现在我们根据关键字key先与根结点比较，假如等于则直接找到返回，如果给定关键字key小于根结点则从左子树递归查找，如果Key大于根结点则从右子树递归查找。因此我们看见实际上，这很像二分查找算法。例如我们在下图的二叉树中查找结点为 42的结点，其过程为下图中的红色箭头：
 
 那么二叉查找树的查找性能如何呢？我们从图中可以看到，查找的次数取决于二叉树的深度，因此查找性能与二叉树的形态密切相关，这里我们为了简单分析，假设这棵二叉树是结点为 n 的完全二叉树，我们怎么计算它的深度呢？我这里直接给出结论，就不证明了，你可以根据二叉树的性质自己推算很简单。deep = log2n向下取整 +１。因此查找的时间复杂度为O(logn)。
   假如我们要插入的数据是一个与二叉树中某个结点重复的怎么办呢？其中一个解决办法是，把这个结点当作比二叉树中重复的结点大的结点，然后将其插入右子树。
 
 
4.2 插入操作
 
 
  二叉查找树的插入过程有点类似查找操作。新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。插入操作我就不给图示了。
 
 
4.3 删除操作
 
 
  相比于查找和插入操作，删除操作会稍微麻烦一些，需要分为三种情况来讨论：
 （1）如果需要删除的结点是叶子结点，则我们直接将其删除即可，然后修改父节点的指针
 （2）如果待删除的结点至少包含一个子树，则只需要修改待删除结点的父节点让父节点的指针指向待删除结点的子树即可
 （3）如果待删除的结点包含两棵子树就比较麻烦，我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。例如删除下图所示的38的结点：
 
 我们根据二叉查找树的特点，很容易就能得到有序序列，只需要中序遍历这棵树就可以了。
 
5、平衡二叉树(AVL Tree)
 
  之前我们分析了二叉查找树的性能，时间复杂度，请试想一下这种情况。假如我们的二叉查找树是一棵单支树，也就是不存在度为2的结点，此时二叉树就退化成了链表，因此时间复杂度退化为O(n)。因此，我们要避免在插入和删除操作中出现的让二叉查找树性能下降的情况，也就是说我们要动态维护这棵二叉树。这就是平衡二叉树，它的定义是这样的：它或者是一棵空树或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，并且左子树和右子树的深度之差的绝对值不超过 1。如果将左右子树的深度差定义为平衡因子，那么平衡因子的值就只可能为0，-1， 1。
   当我们在建立一棵二叉树的时候，或者在插入的时候，就会判断插入操作是否会让这棵二叉树失去平衡，如果失去平衡我们就要动态调整，让它恢复平衡。怎么让它恢复平衡呢？一般我们是采取旋转操作。怎么旋转呢？我们假设由于在二叉查找树上插入结点而失去平衡的最小子树根结点的指针为a（也就是说a是离插入结点最近，且平衡因子绝对值超过1的祖先结点）调整规律一般有4种：
 （1）单向右旋平衡处理： 由于在 * a 的左子树根结点的左子树上插入结点，* a的平衡因子由1变为2，则需要进行一次向右的顺时针旋转操作；
 （2）单向左旋平衡处理： 由于在* a的右子树根结点的右子树上插入结点，* a的平衡因子由-1 变为-2，则需要进行一次向左的逆时针旋转操作；
 （3）双向旋转（先左后右）平衡处理： 由于在* a的左子树根结点的右子树插入结点，* a的平衡因子由1变为2，则需要进行两次旋转操作（先左旋后右旋）；
 （4）双向旋转（先右后左）平衡处理： 由于在* a的右子树根结点的左子树插入结点，* a的平衡因子由-1变为-2，则需要进行两次旋转操作（先右旋后左旋）；
 我们来看看对应的图示，这样帮助理解
 
   由于AVL树的左右子树高度差是严格的小于等于1，因此它是非常严格的平衡二叉树，由于它需要保持非常严格的条件，因此再插入或者删除操作中，一旦发现二叉树不平衡了，就需要维护这棵树的平衡。但是维护二叉树的平衡就需要额外的操作，额外的操作就势必会带来额外的开销，当插入和删除操作太过频繁的时候，就会触发维护操作。但实际上我们之所以要让一棵二叉树保持平衡是为了让它的查找性能不至于急速退化，因此假如说我们对一棵二叉树的平衡并不要求它能够一定满足log2n的高度，但是接近这个高度，那么实际上查找性能也不会太差。
   我们在实际的开发中，如果有一种结构能够解决我们在频繁地插入和删除操作中带来的查找性能下降的问题并且还不至于过于频繁地取维护这棵二叉树的严格平衡，这样的结构是实际我们所喜欢的。如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比 log2n 大很多（比如树的高度仍然是对数量级的），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。
   实际上，在工程应用中，更喜欢用红黑树而不是AVL树，为什么呢？AVL树我们刚才说过为了维护它的平衡它需要付出额外的开销代价，红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。关于红黑树，大家有兴趣可以自己去了解了解，这里我就不说了。
 我们也给出常规二叉查找树的代码实现：
 
public class BinarySearchTree {
  private Node tree;
  // Node类
  public static class Node {
    private int data;	// 数据域
    private Node left;	// 左子树的指针
    private Node right;	// 右子树的指针

    public Node(int data) {
      this.data = data;
    }
  }
  
  // 查找操作
  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      // 小于该结点的值则在左子树寻找
      if (data < p.data) p = p.left;
      // 大于该结点的值则在右子树寻找
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }
  
  // 插入操作
  public void insert(int data) {
    if (tree == null) {
      tree = new Node(data);
      return;
    }
    Node p = tree;
    while (p != null) {
      if (data > p.data) {
        if (p.right == null) {
          p.right = new Node(data);
          return;
        }
        p = p.right;	// 继续在右子树遍历
      } else { // data < p.data
        if (p.left == null) {
          p.left = new Node(data);
          return;
        }
        p = p.left;		// 继续在左子树遍历
      }
    }
  }

  // 删除操作
  public void delete(int data) {
    Node p = tree; // p指向要删除的节点，初始化指向根节点
    Node pp = null; // pp记录的是p的父节点
    while (p != null && p.data != data) {
      pp = p;
      if (data > p.data) p = p.right;
      else p = p.left;
    }
    if (p == null) return; // 没有找到

    // 要删除的节点有两个子节点
    if (p.left != null && p.right != null) { // 查找右子树中最小节点
      Node minP = p.right;
      Node minPP = p; // minPP表示minP的父节点
      while (minP.left != null) {
        minPP = minP;
        minP = minP.left;
      }
      p.data = minP.data; // 将minP的数据替换到p中
      p = minP; // 下面就变成了删除minP了
      pp = minPP;
    }

    // 删除节点是叶子节点或者仅有一个子节点
    Node child; // p的子节点
    if (p.left != null) child = p.left;
    else if (p.right != null) child = p.right;
    else child = null;

    if (pp == null) tree = child; // 删除的是根节点
    else if (pp.left == p) pp.left = child;
    else pp.right = child;
  }

  // 找最小的结点
  public Node findMin() {
    if (tree == null) return null;
    Node p = tree;
    while (p.left != null) {
      p = p.left;
    }
    return p;
  }

  // 找到最大的结点
  public Node findMax() {
    if (tree == null) return null;
    Node p = tree;
    while (p.right != null) {
      p = p.right;
    }
    return p;
  }
}

二叉查找树
 
　　二叉查找树，也称二叉搜索树，或二叉排序树。其定义也比较简单，要么是一颗空树，要么就是具有如下性质的二叉树：
 
（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 
（2） 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 
（3） 任意节点的左、右子树也分别为二叉查找树；
 
（4） 没有键值相等的节点。
 
 
　　如上图所示，是不同形态的二叉查找树。二叉查找树是对要查找的数据进行生成树，左支的值小于右支的值。在查找的时候也是一样的思路，从根节点开始，比节点大进入右支，比节点小进入左支，直到查找到目标值。
 
　　二叉查找树的插入算法比较简单：空树，就首先生成根节点；不是空树就按照查找的算法，找到父节点，然后作为叶子节点插入，如果值已经存在就插入失败。
 
　　删除操作稍微复杂一点，有如下几种情况：
 
​ （1）如果删除的是叶节点，可以直接删除；
 
​ （2）如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
 
​ （3）如果有两个子节点，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除。如下图：
 
 
将待删除节点与后继节点互换，变成如下图所示： 
 
 
将待删除元素删除，如下图所示：
 
 
　　另外，二叉查找树还有一个性质，即对二叉查找树进行中序遍历，即可得到有序的数列。 
 
​　　二叉查找树的查询复杂度，和二分查找一样，插入和查找的时间复杂度均为 O(logn) ，但是在最坏的情况下仍然会有 O(n) 的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（如上不同形态的二叉树图中的b）。
 
平衡二叉树
 
​　　平衡二叉搜索树，又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 —-来自百度百科
 
​　　由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，所以，这也是平衡二叉树设计的初衷。那么平衡二叉树如何保持”平衡“呢？根据定义，有两个重点，一是左右两子树的高度差的绝对值不能超过1，二是左右两子树也是一颗平衡二叉树。
 
　　如下图所示，左图是一棵平衡二叉树，根节点10，左右两子树的高度差是1，而右图，虽然根节点左右两子树高度差是0，但是右子树15的左右子树高度差为2，不符合定义，所以右图不是一棵平衡二叉树。
 
 
​　　由此可以看出平衡二叉树是一棵高度平衡的二叉查找树。所以，要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。
 
　　关于旋转，这东西不拿动态图将还真很难讲明白。所以我就借一下 最容易懂得红黑树 这篇文章中左旋右旋的图来讲。
 
​ 左旋：
 
 
​ 
 
​ 右旋：
 
 
　　不同于顺时针跟逆时针变换这种方式去记忆，上面两个动态图特别方便记忆跟理解：
 
　　左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；
 
　　而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。
 
　　即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。
 
​　　举个例子，像上图是否平衡二叉树的图里面，左图在没插入前”19“节点前，该树还是平衡二叉树，但是在插入”19“后，导致了”15“的左右子树失去了”平衡“，所以此时可以将”15“节点进行左旋，让”15“自身把节点出让给”17“作为”17“的左树，使得”17“节点左右子树平衡，而”15“节点没有子树，左右也平衡了。如下图，
 
 
　　由于在构建平衡二叉树的时候，当有新节点插入时，都会判断插入后时候平衡，这说明了插入新节点前，都是平衡的，也即高度差绝对值不会超过1。当新节点插入后，有可能会有导致树不平衡，这时候就需要进行调整，而可能出现的情况就有4种，分别称作左左，左右，右左，右右。
 
左左：
 
 
　　左左即为在原来平衡的二叉树上，在节点的左子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”10“节点的左子树”7“，的左子树”4“，插入了节点”5“或”3“导致失衡。
 
​　　左左调整其实比较简单，只需要对节点进行右旋即可，如下图，对节点”10“进行右旋，
 
　　注意：如果对左右旋变换还不是很懂或不是很熟练的，可以对照着前面的那两个动图去想象，自己动手变换几次，就明白了。
 
 
左右：
 
 
　　左右即为在原来平衡的二叉树上，在节点的左子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的左子树”7“，的右子树”9“，插入了节点”10“或”8“导致失衡。
 
　　左右的调整就不能像左左一样，进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋，结果图如下，右图的二叉树依然不平衡，而右图就是接下来要讲的右左，即左右跟右左互为镜像，左左跟右右也互为镜像。
 
 
　　右右跟左左一样，只需要旋转一次就能把树调整平衡，而左右跟右左也一样，都要进行旋转两次才能把树调整平衡，所以，首先上图的这种调整是错误的，正确的调整方式是，将左右进行第一次旋转，将左右先调整成左左，然后再对左左进行调整，从而使得二叉树平衡。
 
​　　即先对上图的节点”7“进行左旋，使得二叉树变成了左左，之后再对”11“节点进行右旋，此时二叉树就调整完成，如下图，
 
 
右左：
 
 
​　　右左即为在原来平衡的二叉树上，在节点的右子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”15“，的左子树”13“，插入了节点”12“或”14“导致失衡。
 
​　　前面也说了，右左跟左右其实互为镜像，所以调整过程就反过来，先对节点”15“进行右旋，使得二叉树变成右右，之后再对”11“节点进行左旋，此时二叉树就调整完成，如下图，
 
 
右右：
 
 
　　右右即为在原来平衡的二叉树上，在节点的右子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”13“，的左子树”15“，插入了节点”14“或”19“导致失衡。
 
　　右右只需对节点进行一次左旋即可调整平衡，如下图，对”11“节点进行左旋。
 
 
​　　平衡二叉树构建的过程，就是节点插入的过程，插入失衡情况就上面4种，算简单了，下面讲下平衡二叉树节点的删除，删除的情况会复杂一点，复杂的原因主要在于删除了节点之后要维系二叉树的平衡，但是删除二叉树节点总结起来就两个判断：①删除的是什么类型的节点？②删除了节点之后是否导致失衡？
 
　　节点的类型有三种：1.叶子节点；2.只有左子树或只有右子树；3.既有左子树又有右子树。
 
​　　针对这三种节点类型，再引入判断②，所以处理思路分别是：
 
（1）当删除的节点是叶子节点，则将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型的失衡（左左，左右，右左，右右），然后进行调整。
 
（2）删除的节点只有左子树或只有右子树，这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。
 
（3）删除的节点既有左子树又有右子树，这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。
 
　　最后总结一下，平衡二叉树是一棵高度平衡的二叉树，所以查询的时间复杂度是 O(logN) 。插入的话上面也说，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，最多也只要旋转2次，所以，插入复杂度是 O(1) ，但是平衡二叉树也不是完美的，也有缺点，从上面删除处理思路中也可以看到，就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树—-红黑树，后面再讲。