GitHub源码分享
微信搜寻：码农StayUp
主页地址：https://gozhuyinglong.github.io
源码分享：https://github.com/gozhuyinglong/blog-demos
1. AVL树
AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树，又叫做均衡二叉树。在AVL树中任何节点的两个子树高度差最多为1，所以它又被称为高度均衡树。
如下图中能够清晰的看出，右边的树其根节点左子树高度为3，右子树高度为2，合乎AVL树的特点；而左边的树其根节点左子树高度为3，右子树高度为1，不合乎AVL树的特点。因而右边的树为AVL树，左边的树不是AVL树。
那么怎样才能放弃这种均衡呢？
答案便是在插入或删除节点时，通过对树进行简略的修改来保持平衡，咱们称之为旋转。
2. 旋转（rotation）
旋转分为单旋转（single rotation）和双旋转（double rotation）。
- 当左右子树的高度差超过1，并且最高的叶子节点在“外边”时，应用单旋转。
- 当左右子树的高度差超过1，并且最高的叶子节点在“外面”时，应用双旋转。
而单旋转又分为：
- 左旋转，即向左旋转。当右子树的高度大于左子树时，进行左旋转。
- 右旋转，即向右旋转。当左子树的高度大于右子树时，进行右旋转。
双旋转又分为：
- 左-右双旋转，即先向左旋转（左子节点），再向右旋转。当左子树的高度大小右子树，并且左子树最高的叶子节点为其父节点的右子节点，那么须要左-右双旋转。
- 右-左双旋转，即先向右旋转（右子节点），再向左旋转。当右子树的高度大小左子树，并且右子树最高的叶子节点为其父节点的左子节点，那么须要右-左双旋转。
单看这些名词概念是不容易了解的，上面咱们通过图例来一一介绍。
3. 左旋转
看下图中右边的树，该树是一棵二叉查找树，但是否满足AVL的个性呢？能够发现其根节点的左子树的高度为1，而右子树的高度为3，所以其不一棵AVL树。
通过察看，其右子树高于左子树，并且最高的叶子节点也在左边，那么咱们应用左旋转进行均衡。
具体旋转过程：
- 将根节点4复制出一个新的节点，其左子节点为3放弃不变，将其右子节点指向5（即原根节点的右子节点的左子节点）。
- 将原根节点的右子节点6的左子节点指向新节点4，其右子节点为7放弃不变，那么6便成了新的根节点。
哈哈，是不是有点绕，其实也能够简略了解为：既然右子树比左子树高，那么将树根4向左下移，将树根的右子节点6向上移，成为新的树根，这样便使左右子树的高度均衡了。联合上图，重复练习几次吧。
4. 右旋转
右旋转与左旋转正好是对称的，看下图中右边的树，该二叉查找树的左子树高度为3，而右子树高度为1，不满足AVL树的旋转。
因其左子树高于右子树，并且最高的叶子节点在右边，所以咱们应用右旋转。
具体旋转过程：
- 将根节点7复制出一个新的节点，其右子节点为9放弃不变，左子节点指向5（即原根节点的左子节点的右子节点）。
- 将原根节点的左节点降级为新的根节点，即其左子树为3放弃不变，右子节点指向新的根节点7。
左旋转与右旋转肯定要了解，不然上面的双旋转就更容易晕菜了！
5. 双旋转
在介绍双旋转之前，先来看下图，其根节点的左子树高度为3，右子树高度为9，那么咱们先应用右旋转的形式，看能不能达均衡的成果。
通过观察右旋转后的成果，是不满足AVL树的个性的。这便须要应用双旋转了。
咱们应用左-右旋转来均衡上图中的树，即先进行左旋转，再进行右旋转，但其平衡点不同，如下图所示。
具体旋转过程：
- 先将根节点的左子树（5节点）进行左旋转，升高其（5节点）右子树的高度。
- 再将根节点进行右旋转，便达到了均衡成果。
那么反过来，右-左双旋转的具体过程：
- 先将根节点的右子树进行右旋转，升高其右子树的高度。
- 再将根节点进行左旋转。
6. 代码实现
AVL树的实现是在二叉查找树的根底上增加了均衡操作。
6.1 求节点高度
在Node类中增加节点高度办法height、leftHeight和rightHeight，若节点为空则高度为0。
// 以后节点高度public int height() { return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;}// 左子节点高度public int leftHeight() { if (left == null) { return 0; } return left.height();}// 右子节点高度public int rightHeight() { if (right == null) { return 0; } return right.height();}6.2 左旋转
在Node类中减少左旋转办法leftRotate。
public void leftRotate() { // 将以后节点向左下移，成为新的左节点 Node newLeftNode = new Node(element); newLeftNode.left = left; // 将右子节点设为原根节点右子树的左子树 newLeftNode.right = right.left; // 将右节点上移，成为新的树根（以后节点） element = right.element; // 将左子节点设为新的左子节点（原树根） left = newLeftNode; right = right.right;}6.3 右旋转
在Node类中减少右旋转办法rightRotate。
public void rightRotate() { // 将以后节点向右下移，成为新的右子节点 Node newRightNode = new Node(element); // 将左子节点指向原根节点的左子树的右子树 newRightNode.left = left.right; newRightNode.right = right; // 将左子节点上移，成为新的树根（以后节点） element = left.element; left = left.left; // 将右子节点设为新的右子节点（原树根） right = newRightNode;}6.4 均衡办法
在AVLTree类中增加均衡办法balance，该办法用于判断是须要单旋转还是双旋转。
public void balance(Node node) { if (node == null) { return; } if (node.leftHeight() - node.rightHeight() > 1) { if (node.left.rightHeight() > node.left.leftHeight()) { node.left.leftRotate(); } node.rightRotate(); } else if (node.rightHeight() - node.leftHeight() > 1) { if (node.right.leftHeight() > node.right.rightHeight()) { node.right.rightHeight(); } node.leftRotate(); }}6.5 增加节点
在AVLTree类中减少增加节点办法，当增加完一个节点后，进行调用balance办法，来维持均衡。
private void add(Node node, int element) { if (node.compareTo(element) < 0) { if (node.left == null) { node.left = new Node(element); } else { add(node.left, element); } } else if (node.compareTo(element) > 0) { if (node.right == null) { node.right = new Node(element); } else { add(node.right, element); } } balance(node);}6.6 删除节点
在AVLTree类中减少删除节点办法，当删除完一个节点后，也进行调用balance办法，来保护均衡。
private void remove(Node parentNode, Node node, int element) { if (node == null) { return; } // 先找到指标元素 int compareResult = node.compareTo(element); if (compareResult < 0) { remove(node, node.left, element); } else if (compareResult > 0) { remove(node, node.right, element); } else { // 找到指标元素，判断该节点是父节点的左子树还是右子树 boolean isLeftOfParent = false; if (parentNode.left != null && parentNode.left.compareTo(element) == 0) { isLeftOfParent = true; } // 删除指标元素 if (node.left == null && node.right == null) { // （1）指标元素为叶子节点，间接删除 if (isLeftOfParent) { parentNode.left = null; } else { parentNode.right = null; } } else if (node.left != null && node.right != null) { // （2）指标元素即有左子树，也有右子树 // 找到右子树最小值（叶子节点），并将其删除 Node minNode = findMin(node.right); remove(minNode.element); // 将该最小值替换要删除的指标节点 minNode.left = node.left; minNode.right = node.right; if (isLeftOfParent) { parentNode.left = minNode; } else { parentNode.right = minNode; } } else { // （3）指标元素只有左子树，或只有右子树 if (isLeftOfParent) { parentNode.left = node.left != null ? node.left : node.right; } else { parentNode.right = node.left != null ? node.left : node.right; } } } balance(node);}6.7 残缺代码
因为残缺代码篇幅过长，这里就不展现了，能够通过GitHub进行拜访，地址如下：
https://github.com/gozhuyinglong/blog-demos/blob/main/java-data-structures/src/main/java/io/github/gozhuyinglong/datastructures/tree/AVLTreeDemo.java
7. 总结
总结一句话来示意AVL树：AVL树是一棵其均衡因子（左右子树的高度差）的绝对值小于1的二叉查找树，其能够通过单旋转或双旋转来保持平衡。