在介绍平衡二叉树之前，我们需要先了解一下排序二叉树。因为平衡二叉树的前提就是该树为排序二叉树。

排序二叉树：

一颗空树，或者是具有下列特点的二叉树。

· 若左子树不为空，则左子树所有节点的值小于根节点。

· 若右子树不为空，则右子树所有节点的值大于根节点。

· 左右子树也都是二叉排序树。

· 没有键值相等的特点。

平衡二叉树的基本概念：

平衡二叉树(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型左旋：

① 旧根节点作为新根节点的右子树，新根节点的右子树（如果有）作为旧根节点的左子树。

② 旧根节点作为新根节点的左子树，新根节点的左子树（如果有）作为旧根节点的右子树。