AVL树是一种自平衡的二叉搜索树,由于其特有的平衡性质,可以确保树的高度始终保持在O(log n)的范围内。AVL树的发明者G.M. Adelson-Velsky和E.M. Landis在1962年首次提出,因此得名“AVL”树。AVL树通过在节点上维护一个“平衡因子”来确保树的平衡,平衡因子的定义为左子树的高度减去右子树的高度。AVL树的平衡因子只能为-1、0、1。若插入或删除操作导致平衡因子的绝对值大于1,则需要通过旋转操作来调整树的结构。
以下是Java中AVL树的基本实现,包括插入、删除和旋转操作的示例代码。
AVL树的实现
class TreeNode {
int key;
int height;
TreeNode left;
TreeNode right;
public TreeNode(int key) {
this.key = key;
this.height = 1; // 新节点的高度为1
}
}
public class AVLTree {
private TreeNode root;
// 获取节点高度
private int height(TreeNode node) {
return node == null ? 0 : node.height;
}
// 获取平衡因子
private int getBalance(TreeNode node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
// 右旋转
private TreeNode rightRotate(TreeNode y) {
TreeNode x = y.left;
TreeNode T2 = x.right;
// 进行旋转
x.right = y;
y.left = T2;
// 更新高度
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
// 返回新的根节点
return x;
}
// 左旋转
private TreeNode leftRotate(TreeNode x) {
TreeNode y = x.right;
TreeNode T2 = y.left;
// 进行旋转
y.left = x;
x.right = T2;
// 更新高度
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
// 返回新的根节点
return y;
}
// 插入节点
public TreeNode insert(TreeNode node, int key) {
// 1.执行普通的二叉搜索树插入
if (node == null) {
return new TreeNode(key);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node; // 不允许重复元素
}
// 2.更新高度
node.height = 1 + Math.max(height(node.left), height(node.right)));
// 3.获取平衡因子,检查是否需要平衡
int balance = getBalance(node);
// 如果不平衡,则有四种情况
// 左左情况
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// 右右情况
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// 左右情况
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// 右左情况
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
// 这个节点是平衡的,直接返回
return node;
}
// 前序遍历
public void preOrder(TreeNode node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
// 公开插入功能
public void insert(int key) {
root = insert(root, key);
}
// 公开前序遍历功能
public void preOrder() {
preOrder(root);
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* 插入节点 */
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);
/* 前序遍历 */
System.out.println("前序遍历结果:");
tree.preOrder();
}
}
总结
以上代码展示了AVL树的基本结构和实现。通过自平衡的特性,AVL树能够高效地进行插入、删除和查找操作。每次插入后,AVL树都会检查并维护平衡因子,确保树的高度始终在O(log n)的范围内,这使得AVL树比其他一些二叉搜索树在大规模数据操作时表现得更为出色。在实际应用中,AVL树特别适合于频繁插入和删除操作的场景。