|
对于有 n 个元素的二叉搜索树，他的平均查找时间复杂度是 O(logn) ，但如果创建二叉搜索树的时候插入的是一组升序或者降序的数值，就会导致二叉搜索树始终偏向一方，变成类似链表的形状，查找时间复杂度变成了 O(n) 。 
有没有一种方式不让他变成这种形状呢？实际上是有的，这就是我们这里要讲的 AVL树(Adelson-Velsky and Landis Tree) ，AVL树 得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis 。在 AVL树 中任何节点的两个子树高度差小于等于 1 ，所以它也被称为高度平衡树，增加和删除操作需要通过一次或多次树旋转来重新平衡这棵树，先来看下 AVL 树的节点类。 public class TreeNode {
public int val;// 节点数据。
public TreeNode left;// 左子树。
public TreeNode right;// 右子树。
public int height;// 当前节点高度。
public TreeNode(int val) {
this.val = val;
}
}
为了方便计算，在节点类中添加一个变量 height 他表示当前节点的高度，默认叶子节点高度为 1 。如果没有这个变量，每次获取节点高度的时候都需要重新计算一遍，增加了时间复杂度，有了这个变量以后每次使用的时候直接从节点中取即可。 在 AVL树 中，每个节点左子树与右子树的高度差称为节点的平衡因子，任一节点的平衡因子只能是 -1 ， 0 和 1 ，如果一个节点的平衡因子绝对值大于 1 ，表示这棵二叉搜索树失去了平衡，不在是 AVL树 。 AVL树的插入： AVL 其实就是一棵二叉搜索树，他的查找和我们前面讲的二叉搜索树的查找是一样的，查找操作就不介绍了，我们来看下他的插入操作。因为 AVL 树是高度平衡的二叉搜索树，所以插入之后还需要在进行调整，防止出现偏向一边的情况。
public TreeNode root;// AVL树的根节点。
// AVL树在插入节点之后为了保持树的平衡，可能会进行旋转，导致根节点不固定。
public void insert(int val) {
root = add(root, val);
}
// 插入节点。
private TreeNode add(TreeNode node, int val) {
if (node == null)
node = new TreeNode(val);
if (val < node.val) {// 插入到左子树。
node.left = add(node.left, val);
} else if (val > node.val) {// 插入到右子树。
node.right = add(node.right, val);
}
return balanceTree(node);// 插入之后对树进行调整。
}
AVL树 插入的时候为了保证树的平衡会进行旋转，所以根节点不是固定的，每次插入的时候都需要更新根节点，所以插入的核心代码是 add 函数，我们看到他使用的是递归的实现方式，递归在这里非常重要，他最后一行的 balanceTree 函数是对树进行调整，也就是说他是自下往上的一直到根节点，只要遇到不平衡的节点都会调整，递归暂时还没讲到，如果看不懂也没关系，只需要知道有这个过程就行。AVL树 的节点在插入的时候会有 4 种情况，我们来分别看下。
情况一：LL类型 这种情况直接对不平衡的节点右旋即可。 
情况二：LR类型 这种情况需要对不平衡节点的左子节点左旋，然后就会变成 LL类型 ，接着在对不平衡节点右旋 。 
情况三：RR类型 这种情况直接对不平衡节点左旋。 
情况四：RL类型 这种情况需要对不平衡节点的右子节点右旋，然后就会变成 RR类型 ，接着在对不平衡节点左旋。 
我们来整理一下： 左左类型（LL）：直接对不平衡节点右旋。 左右类型（LR）：先对不平衡节点的左子节点左旋，然后对不平衡节点右旋。 右右类型（RR）：直接对不平衡节点左旋。 右左类型（RL）：先对不平衡节点的右子节点右旋，然后对不平衡节点左旋。
到底是哪种类型我们只需要计算每个节点的左右子树高度差即可判断，如果当前节点的左子树高度与右子树高度的差超过 1 ，基本上可以判定是 L(?) 类型，那么 ? 究竟是 L 还是 R ，还需要继续判断，判断方式我们直接看下代码。 // 对树进行调整。
private TreeNode balanceTree(TreeNode node) {
if (node == null)
return null;
if (getNodeHeight(node.left) - getNodeHeight(node.right) > 1) {// 左侧失衡。
if (getNodeHeight(node.left.left) >= getNodeHeight(node.left.right)) {
node = balanceLL(node);// LL情况。
} else {
node = balanceLR(node);// LR情况。
}
} else if (getNodeHeight(node.right) - getNodeHeight(node.left) > 1) {
if (getNodeHeight(node.right.right)>=getNodeHeight(node.right.left)) {
node = balanceRR(node); // RR情况。
} else {
node = balanceRL(node);// RL情况。
}
}
// 更新 node 节点的高度。
node.height = Math.max(getNodeHeight(node.left),
getNodeHeight(node.right)) + 1;
return node;
}
无论是左旋还是右旋，都会导致不平衡节点的高度发生改变，所以旋转之后还需要更新不平衡节点的高度，我们来看下其他函数的代码。 // LL情况，需要右旋。
private TreeNode balanceLL(TreeNode node) {
TreeNode left = node.left;
node.left = left.right;
left.right = node;
resetHeight(node);// 重新计算node节点的高度。
resetHeight(left);// 重新计算left节点的高度。
return left;
}
// RR情况，需要左旋。
private TreeNode balanceRR(TreeNode node) {
TreeNode right = node.right;
node.right = right.left;
right.left = node;
resetHeight(node);
resetHeight(right);
return right;
}
// LR情况，需要先左旋，然后在右旋。
private TreeNode balanceLR(TreeNode node) {
node.left = balanceRR(node.left);// 左旋。
return balanceLL(node);// 右旋。
}
// RL情况，需要先右旋，然后在左旋
private TreeNode balanceRL(TreeNode node) {
node.right = balanceLL(node.right);// 右旋。
return balanceRR(node);// 左旋。
}
// 获取节点高度，为了方便计算，我们让叶子节点高度为 1 。
private int getNodeHeight(TreeNode node) {
return node == null ? 0 : node.height;
}
// 重新计算node节点的高度。
private void resetHeight(TreeNode node) {
node.height = Math.max(getNodeHeight(node.left),
getNodeHeight(node.right)) + 1;
}
在来看下节点的左旋和右旋，我们先来看下左旋，如下图所示，虽然他已经平衡了，但他并不影响我们对树旋转的研究。左旋是逆时针旋转两个节点，让不平衡节点被其右子节点取代，而该节点成为其右子节点的左子节点。左旋会导致不平衡节点以及他的右子节点高度发生变化，所以旋转之后他俩的高度需要更新一下。 
在来看下右旋，右旋是顺时针旋转两个节点，让不平衡节点被其左子节点取代，而该节点成为其左子节点的右子节点。关于左旋和右旋的代码，大家可以直接通过图就可以看懂，这里就不在逐步分析。 
AVL树的删除： AVL树 的删除，如果删除的是叶子节点或只有一个子节点的节点，则直接删除，否则使用移形换位法，用它的前驱节点或者后继节点替换他，然后删除他的前驱节点或者后继节点。我们看下代码，注意删除的时候可能会出现不平衡，所以最后还需要在进行调整。
// 删除节点。
public void deleteNode(int val) {
root = deleteNode(root, val);
}
private TreeNode deleteNode(TreeNode root, int val) {
if (root == null)
return null;
if (val < root.val)// 在左子树删除。
root.left = deleteNode(root.left, val);
else if (val > root.val)// 在右子树删除。
root.right = deleteNode(root.right, val);
else {// root就是要删除的节点。
if (root.left == null || root.right == null) {
// 如果root是叶子节点或者只有一个子节点，直接删除。
root = root.left == null ? root.right : root.left;
} else {
// 先查找root的后继节点。
TreeNode tmp = postNode(root);
// 移形换位，把后继节点的值赋值到root节点，删除后继节点。
root.val = tmp.val;
// 删除后继节点，tmp.val就是后继节点的值。
root.right = deleteNode(root.right, tmp.val);
}
}
// 删除之后可能会导致树的不平衡，所以需要调整。
return balanceTree(root);
}
// 查找root的后继节点。
private TreeNode postNode(TreeNode root) {
TreeNode cur = root.right;
while (cur.left != null)
cur = cur.left;
return cur;
}
我们在来回过头来看下 balanceTree 这个函数，其中有下面两行代码。 if (getNodeHeight(node.left.left) >= getNodeHeight(node.left.right))
……
if (getNodeHeight(node.right.right) >= getNodeHeight(node.right.left))
旋转的时候就是哪边低先往哪边旋转，但如果两边子树高度都一样呢？。 
我们看到节点 12 出现了不平衡，而节点 16 的两个子树高度都是一样的，我们是按照 RR 处理还是按照 RL 处理呢？实际上你尝试着旋转下就知道，按照 RR 处理才能保证平衡。有的同学可能会说这个图是不可能存在的，因为他早已经出现了不平衡。实际上如果我们添加节点的时候这个图是不会存在的，但删除的时候就不一定了，比如 9 还有一个节点，但我们把它删除了。
|
