Java 实现 AVL树

在二叉平衡树中，我们进行插入和删除操作时都需要遍历树，可见树的结构是很影响操作效率的。在最坏的情况下，树成了一个单支树，查找的时间复杂度成了O(N)，建树跟没建树一样。那么是不是有什么办法可以建一个树避免这种情况？

一.概念

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，其又叫高度平衡树。进行插入和删除操作后对树进行一次或多次旋转，保证每个结点的左右子树高度之差的绝对值不超过1，以达到高度平衡的目的。

1.AVL树本质上还是二叉平衡树，这是必须保证的一点；

2.AVL树在二叉平衡树的基础上加入了一个平衡的条件，即：每个结点的左右子树高度之差的绝对值不超过1。

二叉平衡树：Java Map和Set-CSDN博客

二.定义节点

节点与二叉平衡树的节点差不多，多了一个平衡因子，一个父节点。

static class TreeNode {public int val;public int bf;//平衡因子public TreeNode left;public TreeNode right;public TreeNode parent;public TreeNode(int val) {this.val = val;}
}

三.插入操作

因为AVL树也是二叉平衡树，所以插入操作是一样的，只需在后面加一个调整平衡因子的操作。

//找到要插入的位置
TreeNode node = new TreeNode(val);
if(root == null) {root = node;return true;
}TreeNode parent = null;
TreeNode cur = root;
while (cur != null) {if(cur.val < val) {parent = cur;cur = cur.right;}else if(cur.val == val) {return false;}else {parent = cur;cur = cur.left;}
}//插入节点
node.parent = parent;
cur = node;
if(parent.val < val) {parent.right = node;
}else {parent.left = node;
}

上述代码就是插入节点的操作。插入完后我们要对平衡因子进行调整。

1.调整平衡因子

平衡因子可分为三种情况：、、。

1.1 等于，说明该节点的左右子树高度相同，高度相同也就意味着该节点平衡了，也就是说新插入的节点没有使树的高度发生变化，那么整个树都是平衡的。

1.2 等于，说明该节点的左右子树高度相差1，如果左子树高那么就是-1，如果右子树高，那么就是1。如果是这种情况，还要继续往上找，因为这说明我们插入的节点影响了树的高度，这是要看一下是不是不平衡了。

1.3 等于，说明该节点左右子树高度相差2，不平衡了，要进行调整。这里又要分情况讨论了。

当平衡因子等于 2 时，说明右子树高。这里又要分为两种情况：

为什么要分为这两种呢？这与加下来的旋转操作有关。

前面说了，AVL树就是靠旋转来进行调整以达到平衡。如左图右子树高，我们可以通过左旋来降低右子树的高度。这里大家可以去下面看一下左旋的具体操作。

但对于右图来说，左旋就不好用了，转了之后还是不平衡的。对于右图我们要用先右旋在左旋的操作。

为什么会这样？左旋转的本质就是将bf为的左子树接到parent节点的右子树，如果说其这个左子树本身就是更深的子树，那么接上就和原来没有什么区别。

当平衡因子等于 -2 时，也是一样，都是一个原理这里不过多赘述，直接上代码。

public boolean insert(int val) {//找到要插入的位置TreeNode node = new TreeNode(val);if(root == null) {root = node;return true;}TreeNode parent = null;TreeNode cur = root;while (cur != null) {if(cur.val < val) {parent = cur;cur = cur.right;}else if(cur.val == val) {return false;}else {parent = cur;cur = cur.left;}}//插入节点node.parent = parent;cur = node;if(parent.val < val) {parent.right = node;}else {parent.left = node;}//调整平衡因子while (parent != null) {//更新平衡因子if(cur == parent.right) {parent.bf++;}else {parent.bf--;}if(parent.bf == 1 || parent.bf == -1){//继续循环cur = parent;parent = cur.parent;}else if(parent.bf == 2){if(cur.bf == 1) {rotateLeft(parent);}else {rotateRL(parent);}break;}else if(parent.bf == -2){if(cur.bf == -1) {rotateRight(parent);}else {rotateLR(parent);}break;}else{//已经平衡了break;}}return true;
}

2.左旋

将子树向左旋转：

上图左图是没有旋转时的状态，右图时左旋后的状态，我们可以通过节点变化来得到整个过程的变化：12的左子树连接到了10上，10变成了12的左子树。

可以拆成这么几步：

1.将bf=1的节点的左子树接到parent的右子树上；

2.将bf=1的节点连接到parent的parent；

3.将parent连接到bf=1的左子树上。

private void rotateLeft(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;//将bf=1的节点的左子树接到parent的右子树上parent.right = subRL;if(subRL != null) {subRL.parent = parent;}//将bf=1的节点连接到parent的parentTreeNode pParent = parent.parent;if(root == parent) {root = subR;root.parent = null;}else {if(pParent.left == parent) {pParent.left = subR;}else {pParent.right = subR;}subR.parent = pParent;}//将parent连接到bf=1的左子树上subR.left = parent;parent.parent = subR;//调整平衡因子subR.bf = parent.bf = 0;}

3.右旋

将子树向右旋：

思路跟向左旋一样，这里是将8的右子树连在10的左子树上，将10连在8的右子树上。

具体步骤：

1.将bf=-1的节点的右子树连在parent的左子树上；

2.将bf=-1的节点与parent的parent连接；

3.将parent连接到bf=-1节点的右子树上。

private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;//将bf=-1的节点的右子树连在parent的左子树上parent.left = subLR;if(subLR != null) {subLR.parent = parent;}//将bf=-1的节点与parent的parent连接TreeNode pParent = parent.parent;if(parent == root) {root = subL;root.parent = null;}else {if(pParent.left == parent) {pParent.left = subL;}else {pParent.right = subL;}subL.parent = pParent;}//将parent连接到bf=-1的节点上subL.right = parent;parent.parent = subL;//调整平衡因子subL.bf = 0;parent.bf = 0;
}

4.先右旋后左旋

先旋转以bf=-1为父节点的树，再旋转parent的树：

表现在这张图里的是先旋转13节点的树，旋转完后再旋转10节点的树。

这里要特别说明以下平衡因子的调整：

上面两张图相当清晰表示出了平衡因子的变化。

private void rotateRL(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;rotateRight(parent.right);rotateLeft(parent);if(bf == 1) {parent.bf = -1;subR.bf = 0;subRL.bf = 0;}if(bf == -1){parent.bf = 0;subR.bf = 1;subRL.bf = 0;}
}

5.先左旋后右旋

这个跟先右旋再左旋相似，都很像。

代码：

private void rotateLR(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;int bf = subLR.bf;rotateLeft(parent.left);rotateRight(parent);if(bf == -1) {subL.bf = 0;subLR.bf = 0;parent.bf = 1;}if(bf == 1){subL.bf = -1;subLR.bf = 0;parent.bf = 0;}
}

四.判断是不是AVL树

判断什么是不是什么这种问题一般是从性质出发。

判断是不是AVL树，首先这棵树是一颗二叉平衡树，其次这棵树的高度也要平衡。

public boolean isBalanced(TreeNode root) {if(root == null){return true;}int leftH = height(root.left);int rightH = height(root.right);if(rightH-leftH != root.bf) {return false;}return Math.abs(leftH-rightH) <= 1&& isBalanced(root.left)&& isBalanced(root.right);
}

五.总结

AVL树改善了原来二叉平衡树查找的问题，但也有新的问题。我们要在AVL树上插入或删除时，要不断的转转转，这个转转转也要时间的。所以说，如果我们要存储一个要频发插入删除的树，不适合用这个。