一、AVL树的定义
在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
——百度百科
二、AVL树添加、删除元素
说明：
AVLTress: 外部类
root: AVL树的根节点
nodeStack: 存放某次删除元素时遍历过的节点栈
Node: 内部类，节点类型
this：当前节点
left：当前节点的左子节点
right：当前节点的右子节点
value: 当前节点存放的值
height(): 当前节点高度
rightHeight:右子树高度
leftHeight()：左子树高度
leftRoate()：令当前节点左旋转
rightRotate()：令当前节点右旋转
balance(): 调整以当前节点为根节点的子树平衡
1.添加
往AVL树 this 添加新节点 node 的思想是使用递归 ：
外部类函数 add(E value) , 由根节点调用 root.add( new Node( value ) )
内部类函数 add(Node node)，由当前节点调用
步骤：
- node.value <= this.value ,将其添加到当前树的左子树，
this.left !=null 则 this.left.add( node )
this.left ==null , this.left = node- nodevalue > this.value , 将其添加到当前树的右子树
this.right != null 则 this.right.add( node )
this.right == null , this.right = node
在每次寻找适当的插入位置时，当前节点 this 遍历过的节点为所有可能发生失衡的节点，因此需要在插入节点完成后对当前节点进行平衡调整：this.balance()。
添加元素 代码：
/**
* Desc: 添加新元素 value
*
* @author pikachu
*/
public void add(E value) {
if (root == null) {
root = new Node(value);
} else {
root.add(new Node(value));
}
}
/**
* Desc: 将 node加入到当前节点 this
*
* @param node 待加入节点
* @author pikachu
*/
private void add(Node node) {
if (node.value.compareTo(this.value) <= 0) {
if (this.left != null) {
this.left.add(node);
} else {
this.left = node;
}
} else {
if (this.right != null) {
this.right.add(node);
} else {
this.right = node;
}
}
balance();
}
2.旋转
往AVL树中添加元素时可能会破环树的平衡，处理形况分为4种：LL、RR、LR、RL。
对树进行旋转时总是以高度较大的子树为圆心旋转，从而降低其高度，
左旋转：逆时针旋转
右旋转：顺时针旋转
LL
LL型：破环平衡的节点在左子树的左子节点，leftHeight>rightHeight && left.leftHeight >= left.rightHeight，4(this)绕2(left)右转（顺时针）
RR
RR型：破环平衡的节点在右子树的右子节点，rightHeight>leftHeight && right.rightHeight >= right.leftHeight，6(this)绕8(right)左转（逆时针）
LR
LR型：破环平衡的节点在左子树的右子节点，leftHeight > rightHeight &&
left.rightHeight > left.leftHeight。
- 2(left)绕3(left.right)左转（逆时针）
- 5（this）绕3（left）右旋转（顺时针）
RL
RL型：破环平衡的节点在右子树的左子节点， rightHeight > leftHeight &&
right.leftHeight > right.rightHeight。
- 5(right)绕4(right.left)右转（顺时针）
- 2（this）绕4（right）左旋转（逆时针）
调节平衡代码
/**
* Desc:调节当前节点的子树平衡
*/
private void balance() {
// 平衡调整
if (rightHeight() - leftHeight() > 1) {
if (right.rightHeight() >= right.leftHeight()) {
//RR型
leftRotate();
} else {
//RL型
right.rightRotate();
leftRotate();
}
return;
}
if (leftHeight() - rightHeight() > 1) {
if (left.leftHeight() >= left.rightHeight()) {
//LL型
rightRotate();
} else {
//LR型
left.leftRotate();
rightRotate();
}
}
}
3.删除
remove( Node parent, Node delNode ) : 移除preNode的子树中的node节点(如果存在), 当待删除的节点有左右子树时，将右子树的最小节点作为 parent的新子节点, 删除后将遍历路径上的节点nodesStack平衡。
说明：
this 当前节点
parent 当前节点的父节点
delNode 待删除节点
rightMinNode 扫描 this 右子树最小节点（this.right != null 时实际删除的节点）
preNode rightMinNode的父节点，初始为this
寻找待删除节点时的路径可能不只是每次遍历的当前节点 this ，还有 preNode 遍历过的节点。如以下情况：
此时 preNNode 遍历过的节点 17 失衡，因此每次当 preNode 发生移动时也需要将 preNode 压入 nodeStack。
步骤：
- delNode < this,往左子树查找删除,若左子树为空则结束
- delNode > this,往右子树查找删除,若右子树为空则结束
- delNode = this 找到待删除的节点 this
3.1 this.right不为空，在 this.right的子树中寻找最小节点 rightMinNode，作为新子树的根节点
3.1.1preNode和rightMinNode发生移动，待删除节点的右子节点有左子树， 并在该树（根节点 rightMinNode,left = null, right 不一定为 null）中找到最小值。
3.1.2 preNode和rightMinNode没有移动,待删除节点的右子节点无左子树,this.right.left = null,
右子树的最小节点就是this.right,令this拼接上this.right.right。
3.1.3 将 this.value 替换为 rightMinNode.value
3.2 this.right为空
3.2.1 this =parent.right)，parent.right = this.left;
this = parent.left， parent.left = this.left;
3.2.2 this = parent ,删除树中根节点,替换根节点 root = root.left;
删除元素时也可能破环树的平衡，需要记录删除时遍历的节点 nodeStack，然后将其逆序取每个遍历过的节点 node 进行平衡化 : node.balance();
删除元素代码
/**
* Desc:
*
* @param value 待移除的元素
* @author pikachu
*/
public void remove(E value) {
if (root == null) {
System.out.println("Tree is empty");
} else {
root.remove(root, new Node(value));
// 本次删除结束，将nodes清空
nodeStack.clear();
}
}
/**
* Desc:移除preNode的子树中的node节点(如果存在),
* 当待删除的节点有左右子树时，将右子树的最小节点作为 parent的新子节点,
* 删除后将遍历路径上的节点nodesStack平衡
*
* @param parent 当前节点的父节点
* @param delNode 待删除节点
* @author pikachu
*/
private void remove(Node parent, Node delNode) {
nodeStack.push(this);
// 1.delNode < this,往左子树查找删除；若左子树为空则结束
if (delNode.value.compareTo(this.value) < 0) {
if (this.left != null) {
this.left.remove(this, delNode);
}
}
// 2.delNode > this,往右子树查找删除；若右子树为空则结束
else if (delNode.value.compareTo(this.value) > 0) {
if (this.right != null) {
this.right.remove(this, delNode);
}
}
// 3.delNode = this 找到待删除的节点 this
else if (delNode.value.compareTo(this.value) == 0) {
Node preNode = this;
// 3.1 this.right不为空，在 this.right的子树中寻找最小节点 rightMinNode，作为新子树的根节点
if (this.right != null) {
Node rightMinNode = preNode.right;
while (rightMinNode.left != null) {
preNode = rightMinNode;
rightMinNode = rightMinNode.left;
// !!!添加遍历路径
nodeStack.add(preNode);
}
if (preNode.right != rightMinNode) {
// 3.1.1 preNode和rightMinNode发生移动，待删除节点的右子节点有左子树,
// 并在该树（根节点 rightMinNode,left = null, right 不一定为 null）中找到最小值
preNode.left = rightMinNode.right;
} else {
// 3.1.2 preNode和rightMinNode没有移动,待删除节点的右子节点无左子树,this.right.left = null,
// 右子树的最小节点就是this.right,令this拼接上this.right.right
preNode.right = preNode.right.right;
}
// 3.1.3 将 this.value 替换为 rightMinNode.value
this.value = rightMinNode.value;
}
// 3.2 this.right为空
else {
if (this == parent.right) {
parent.right = this.left;
} else if (this == parent.left) {
parent.left = this.left;
}
// 3.2.1 删除树中根节点
else {
root = root.left;
}
}
// 逆序平衡遍历过的节点
while (nodeStack.size() > 0) {
nodeStack.pop().balance();
}
}
}
三、完整代码
Test 为测试类
package 树;
import java.util.*;
class TestLL {
public static void main(String[] args) {
Integer[] a = new Integer[]{6, 5, 8, 7, 9, 10};
AVLTree<Integer> avlTree = new AVLTree<>(a);
System.out.println(avlTree.height());
System.out.println("avlTree = " + avlTree);
avlTree.infixOrder();
System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
}
}
class TestRR {
public static void main(String[] args) {
Integer[] a = new Integer[]{2, 1, 3, 5, 6, 4};
AVLTree<Integer> avlTree = new AVLTree<>(a);
System.out.println(avlTree.height());
System.out.println("avlTree = " + avlTree);
avlTree.infixOrder();
System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
}
}
class TestLR {
public static void main(String[] args) {
Integer[] a = new Integer[]{5, 2, 6, 1, 3, 4};
AVLTree<Integer> avlTree = new AVLTree<>(a);
System.out.println("avlTree.height() = " + avlTree.height());
System.out.println("avlTree = " + avlTree);
avlTree.infixOrder();
System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
}
}
class TestRL {
public static void main(String[] args) {
Integer[] a = new Integer[]{2, 1, 5, 4, 6, 3};
AVLTree<Integer> avlTree = new AVLTree<>(a);
System.out.println("avlTree.height() = " + avlTree.height());
System.out.println("avlTree = " + avlTree);
avlTree.infixOrder();
avlTree.infixOrder();
System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
}
}
class RandomTest {
public static void main(String[] args) {
int n = 40;
Random random = new Random();
Integer[] a = new Integer[n];
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt(n);
}
System.out.println(n + "个随机数:");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ,");
if (i % 20 == 0) {
System.out.println();
}
}
AVLTree<Integer> avlTree = new AVLTree<>();
// 测试创建
System.out.println("\n- - - - - - - - 测试随机数创建AVL树 - - - - - - - -");
for (Integer integer : a) {
avlTree.add(integer);
// System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
}
System.out.println("- - - - - - - - - - - 创建完成 - - - - - - - - - -");
System.out.println("avlTree = " + avlTree);
avlTree.infixOrder();
System.out.println("avlTree.height() = " + avlTree.height());
// 测试删除
System.out.println("- - - - - - - - 测试AVL树中删除随机数 - - - - - - - -");
for (int i = 0; i < a.length; i++) {
Integer data = a[random.nextInt(a.length)];
System.out.print(" remove = " + data);
avlTree.remove(data);
// System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
avlTree.testBalance();
if (i % 10 == 0) {
System.out.println();
}
}
System.out.println();
System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
System.out.println("- - - - - - - - - - 删除完成 - - - - - - - - - -");
avlTree.infixOrder();
}
}
class TestRemove {
public static void main(String[] args) {
Integer[] a = new Integer[]{11, 14, 17, 6, 11, 19, 9, 13, 7, 15, 13, 8, 7, 19, 9, 12, 2, 4, 7, 19};
int n = 100;
Random random = new Random();
// Integer[] a = new Integer[n];
// for (int i = 0; i < a.length; i++) {
// a[i] = random.nextInt(n);
// }
AVLTree<Integer> avlTree = new AVLTree<>(a);
System.out.println(n + "个随机数:");
System.out.println("- - - - - - 创建 - - - - - ");
System.out.println("avlTree.height() = " + avlTree.height());
System.out.println("avlTree = " + avlTree);
avlTree.infixOrder();
System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
System.out.println("- - - - - - 删除 - - - - - ");
for (Integer integer : a) {
avlTree.remove(integer);
avlTree.infixOrder();
System.out.println("avlTree.testBalance() = " + avlTree.testBalance());
}
System.out.println("avlTree = " + avlTree);
}
}
/**
* Desc: 平衡二叉树
*
* @author pikachu
* @date: 2022/8/20 9:54
*/
public class AVLTree<E extends Comparable<E>> {
private Node root;
private Stack<Node> nodeStack = new Stack<>(); // 删除过程中遍历的节点
public AVLTree() {
}
public AVLTree(E[] value) {
for (E item : value) {
add(item);
}
}
/**
* Desc: 添加新元素 value
*
* @author pikachu
*/
public void add(E value) {
if (root == null) {
root = new Node(value);
} else {
root.add(new Node(value));
}
}
/**
* Desc:
*
* @param value 待移除的元素
* @author pikachu
*/
public void remove(E value) {
if (root == null) {
System.out.println("Tree is empty");
} else {
root.remove(root, new Node(value));
// 本次删除结束，将nodes清空
nodeStack.clear();
}
}
/**
* Desc: 中序遍历该子树（从小到大输出）
*
* @author pikachu
*/
public void infixOrder() {
if (root == null) {
System.out.println("Tree is empty");
} else {
root.infixOrder();
System.out.println();
}
}
/**
* Desc:测试当前树是否满足AVL树
*
* @return 树是否平衡
*/
public boolean testBalance() {
if (root != null) {
return root.testBalance();
}
return false;
}
/**
* Desc:获取树的高度
*
* @return {@link int}
*/
public int height() {
System.out.println("leftHeight() = " + root.leftHeight() + " & rightHeight() = " + root.rightHeight());
return root.height();
}
@Override
public String toString() {
return root == null ? "Tree is empty" : "root : " + root.value;
}
private class Node {
private Node left;
private Node right;
private E value;
private Node(E value) {
this.value = value;
}
/**
* Desc: 将 node加入到当前节点 this
*
* @param node 待加入节点
* @author pikachu
*/
private void add(Node node) {
if (node.value.compareTo(this.value) <= 0) {
if (this.left != null) {
this.left.add(node);
} else {
this.left = node;
}
} else {
if (this.right != null) {
this.right.add(node);
} else {
this.right = node;
}
}
balance();
}
/**
* Desc:移除preNode的子树中的node节点(如果存在),
* 当待删除的节点有左右子树时，将右子树的最小节点作为 parent的新子节点,
* 删除后将遍历路径上的节点nodesStack平衡
*
* @param parent 当前节点的父节点
* @param delNode 待删除节点
* @author pikachu
*/
private void remove(Node parent, Node delNode) {
nodeStack.push(this);
// 1.delNode < this,往左子树查找删除；若左子树为空则结束
if (delNode.value.compareTo(this.value) < 0) {
if (this.left != null) {
this.left.remove(this, delNode);
}
}
// 2.delNode > this,往右子树查找删除；若右子树为空则结束
else if (delNode.value.compareTo(this.value) > 0) {
if (this.right != null) {
this.right.remove(this, delNode);
}
}
// 3.delNode = this 找到待删除的节点 this
else if (delNode.value.compareTo(this.value) == 0) {
Node preNode = this;
// 3.1 this.right不为空，在 this.right的子树中寻找最小节点 rightMinNode，作为新子树的根节点
if (this.right != null) {
Node rightMinNode = preNode.right;
while (rightMinNode.left != null) {
preNode = rightMinNode;
rightMinNode = rightMinNode.left;
// !!!添加遍历路径
nodeStack.add(preNode);
}
if (preNode.right != rightMinNode) {
// 3.1.1 preNode和rightMinNode发生移动，待删除节点的右子节点有左子树,
// 并在该树（根节点 rightMinNode,left = null, right 不一定为 null）中找到最小值
preNode.left = rightMinNode.right;
} else {
// 3.1.2 preNode和rightMinNode没有移动,待删除节点的右子节点无左子树,this.right.left = null,
// 右子树的最小节点就是this.right,令this拼接上this.right.right
preNode.right = preNode.right.right;
}
// 3.1.3 将 this.value 替换为 rightMinNode.value
this.value = rightMinNode.value;
}
// 3.2 this.right为空
else {
if (this == parent.right) {
parent.right = this.left;
} else if (this == parent.left) {
parent.left = this.left;
}
// 3.2.1 删除树中根节点
else {
root = root.left;
}
}
// 逆序平衡遍历过的节点
while (nodeStack.size() > 0) {
nodeStack.pop().balance();
}
}
}
private int leftHeight() {
return left != null ? left.height() : 0;
}
private int rightHeight() {
return right != null ? right.height() : 0;
}
private int height() {
return Math.max(left != null ? left.height() : 0, right != null ? right.height() : 0) + 1;
}
/**
* Desc:当前节点 this绕 right左旋转
*/
private void leftRotate() {
Node newNode = new Node(this.value);
newNode.left = left;
newNode.right = right.left;
value = right.value;
right = right.right;
left = newNode;
}
/**
* Desc:当前节点 this绕 left右旋转
*/
private void rightRotate() {
Node newNode = new Node(value);
newNode.left = left.right;
newNode.right = right;
left.right = newNode;
value = left.value;
left = left.left;
right = newNode;
}
/**
* Desc:调节当前节点的子树平衡
*/
private void balance() {
// 平衡调整
if (rightHeight() - leftHeight() > 1) {
if (right.rightHeight() >= right.leftHeight()) {
//RR型
leftRotate();
} else {
//RL型
right.rightRotate();
leftRotate();
}
return;
}
if (leftHeight() - rightHeight() > 1) {
if (left.leftHeight() >= left.rightHeight()) {
//LL型
rightRotate();
} else {
//LR型
left.leftRotate();
rightRotate();
}
}
}
/**
* Desc:
* 中序遍历二叉排序树后刚好从小到大输出
*
* @author pikachu
*/
private void infixOrder() {
if (left != null) {
left.infixOrder();
}
System.out.print(value + " ,");
if (right != null) {
right.infixOrder();
}
}
/**
* Desc:测试当前子树是否平衡
*
* @return {@link boolean} 平衡：true 不平衡：false
*/
private boolean testBalance() {
boolean flag = true;
if (flag && left != null) {
flag = left.testBalance();
}
if (flag && Math.abs(leftHeight() - rightHeight()) > 1) {
System.out.println("AVL 树失衡！");
// System.out.println("失衡节点:" + value + " & leftHeight=" + leftHeight() + " & rightHeight=" + rightHeight());
flag = false;
throw new RuntimeException("失衡节点:" + value + " & leftHeight=" + leftHeight() + " & rightHeight=" + rightHeight());
}
if (flag && right != null) {
flag = right.testBalance();
}
return flag;
}
@Override
public String toString() {
return this.value.toString();
}
}
}
四、测试
TestRandom：随机数创建AVL树，测试添加/元素后树的平衡
- 只在添加时调整平衡
- 删除元素后也调整平衡
- 增加数据，不逐个输出树是否平衡，不平衡时将抛出异常
