在介绍平衡二叉树之前，我们需要先了解一下排序二叉树。因为平衡二叉树的前提就是该树为排序二叉树。
排序二叉树：
一颗空树，或者是具有下列特点的二叉树。
· 若左子树不为空，则左子树所有节点的值小于根节点。
· 若右子树不为空，则右子树所有节点的值大于根节点。
· 左右子树也都是二叉排序树。
· 没有键值相等的特点。
平衡二叉树的基本概念：
平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)是一种排序二叉树，其中每一个节点的左子树和右子树的高度差至多等于1。即任意节点的子树高度差都小于等于1。
只要二叉树上有一个节点的平衡因子绝对值大于1，则该树不为平衡二叉树。
·平衡因子：二叉树上节点的左子树深度减去右子树深度的值。
平衡二叉树的特点：
平衡二叉树若不为空树的话，则需要满足以下特点。
· 是一个排序二叉树。
· 左子树与右子树都是平衡二叉树，且左子树与右子树深度之差不超过1。
· 平衡二叉树上所有节点的平衡因子只能是-1，0，1。
例如：
例中都不是平衡二叉树，因为都不满足排序二叉树的概念。前者不满足排序二叉树，后者深度绝对值大于1。
满足排序二叉树的同时，左右子树之间深度差值大于1即为平衡二叉树。如下：
平衡二叉树操作：
在平衡因子绝对值大于1时，平衡二叉树会失衡，此时需要旋转纠正。旋转方式有两种：分为左旋和右旋。
· 左旋：
① 旧根节点为新根节点左子树。
② 新根节点左子树若存在，则为旧根节点右子树。
· 右旋：
①旧根节点为新根节点右子树。
②新根节点右子树若存在，则为旧根节点左子树。
旋转纠正类型分为四种：LL型、LR型、RL型、RR型。
· LL型：插入左孩子的左子树，右旋。
· RR型：插入右孩子的右子树，左旋。
· LR型：插入左孩子的右子树，先左旋，再右旋。
· RL型：插入右孩子的左子树，先右旋，再左旋。
LL型右旋：
旧根节点作为新根节点的右子树，新根节点的右子树（如果有）作为旧根节点的左子树。
RR型左旋：
旧根节点作为新根节点的左子树，新根节点的左子树（如果有）作为旧根节点的右子树。
LR型左旋：
①旧根节点作为新根节点的左子树，新根节点的左子树（如果有）作为旧根节点的右子树。
②旧根节点作为新根节点的右子树，新根节点的右子树（如果有）作为旧根节点的左子树。
RL型左旋：
① 旧根节点作为新根节点的右子树，新根节点的右子树（如果有）作为旧根节点的左子树。
② 旧根节点作为新根节点的左子树，新根节点的左子树（如果有）作为旧根节点的右子树。
3279916262