关于数据结构:数据结构-AVL-树

AVL 树是最早被创造的自均衡的二叉查找树，在 AVL 树中，任意结点的两个子树的高度最大差异为 1，所以它也被称为高度均衡树，其本质依然是一颗二叉查找树。

联合二叉查找树，AVL 树具备以下个性：

上述的前三项都是二叉查找树的个性，第四个是 AVL 树自均衡的个性。

为了保障二叉树的均衡，AVL 树引入了监督机制，就是在树的某一部分的不均衡度超过一个阈值后触发相应的均衡操作，保障树的均衡度在能够承受的范畴内。

既然引入了监督机制，则必然须要一个监督指标，以此来判断是否须要进行均衡操作。这个监督指标被称为 均衡因子（Balance Factor）。定义如下：

某个结点的右子树的高度减去左子树的高度失去的差值。

基于均衡因子，就能够这样定义 AVL 树：

所有结点的均衡因子的绝对值都不超过 1 的二叉查找树。

为了计算均衡因子，天然须要在结点中引入高度这一属性。结点的高度为以下定义：

左右子树的高度的最大值。

class AVLNode {
    AVLNode left;       // 左子树
    AVLNode right;      // 右子树
    int height;         // 以后结点的高度
    int value;          // 以后结点的值
}

自均衡是指在对均衡二叉树执行插入或删除结点操作后，可能会导致树中某个结点的均衡因子绝对值超过 1，即均衡二叉树变得“不均衡”，为了复原该结点左右子树的均衡，此时须要对结点执行旋转操作。

二叉树的均衡化有两大根底操作：左旋和右旋。左旋，即是逆时针旋转；右旋，即是顺时针旋转。

这两种操作都是从失去平衡的最小子树根结点开始的（即离插入结点最近且均衡因子超过 1 的祖结点）。

所谓左旋操作，就是把上图中的 B 结点和 A 结点进行所谓“父子替换”。在仅有这三个结点时候，是非常简略的。然而当 B 结点处存在左孩子时，事件就变得有点简单了。

通常的操作是：结点 B 摈弃左孩子，将之与旋转后的结点 A 相连，成为结点 A 的右孩子。

所谓右旋操作，就是把上图中的 B 结点和 C 结点进行所谓“父子替换”。在仅有这三个结点时候，也是是非常简略的。然而当 B 结点处存在右孩子时，事件就变得有点简单了。

这时通常的操作是：结点 B 摈弃右孩子，将之和旋转后的结点 C 相连，成为结点 C 的左孩子。

LL 型又被称为“左左”，从上图中能够看得出，A 结点的均衡因子绝对值达到了 2，须要进行修复能力从新成为一棵均衡二叉树。F 结点为新插入的结点，优先会通过 A 结点的 左孩子 B 结点，最终落到 B 结点的 左子树 上，这即是“左左”的来由。

能够应用均衡因子来定义 LL 状况：A 结点的均衡因子为 -2，左孩子 B 结点的均衡因子为 -1。

这时候仅须要对 A 结点做一次右旋的操作即可达到均衡状态：

RR 型又被称为“右右”，与下面的 LL 型具备对称性，展现的状况如下：

也能够应用均衡因子来定义：A 结点的均衡因子为 2，右孩子 C 结点的均衡因子为 1。

这里则是仅须要对 A 结点做一次左旋的操作即可达到均衡状态：

应用均衡因子定义 LR 型为：A 结点的均衡因子为 -2，左孩子 B 结点的均衡因子为 1。

上面有一个例子：

第一步：对 A 结点的左子结点 —— B 结点执行左旋操作，失去一个 LL 型的构造：

第二步：对 A 结点执行右旋操作：

RL 型和下面的 LR 型对称，A 结点的均衡因子为 2，右孩子 C 结点的均衡因子为 -1。

第一步：对 A 结点的右子结点 —— C 结点执行右旋操作，失去一个 RR 型的构造：

第二步：对 A 结点执行左旋操作：

简介