平衡树是一种特殊的二叉搜索树,它的设计目的是为了保持树的平衡,从而保证所有操作的时间复杂度保持在O(log n),即使在最坏的情况下也是如此。最常见的平衡树之一是AVL树,它是以发明者G.M. Adelson-Velsky和E.M. Landis的名字命名的。
在AVL树中,任何节点的两个子树的高度最大差别不超过1。这意味着AVL树总是尽可能地保持平衡,从而优化了搜索、插入和删除操作的效率。
AVL树的关键概念:
-
平衡因子:一个节点的平衡因子是其右子树的高度减去其左子树的高度。平衡因子可以是-1、0或1。
-
旋转:当插入或删除操作破坏了树的平衡时,AVL树会执行一系列的旋转操作来重新平衡树。旋转分为以下几种:
- 单旋转:右旋(Right Rotation)和左旋(Left Rotation)。
- 双旋转:右旋后再左旋(Right-Left Rotation)或左旋后再右旋(Left-Right Rotation)。
Java实现案例:
我们可以通过下面的Java代码来实现一个基本的AVL树:
public class AVLTree<T extends Comparable<T>> {
private Node<T> root;
private static class Node<T> {
T data;
Node<T> left, right;
int height;
Node(T data) {
this.data = data;
height = 1;
}
}
private int height(Node<T> N) {
if (N == null)
return 0;
return N.height;
}
private int getBalance(Node<T> N) {
if (N == null)
return 0;
return height(N.right) - height(N.left);
}
private Node<T> rightRotate(Node<T> y) {
Node<T> x = y.left;
Node<T> 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 Node<T> leftRotate(Node<T> x) {
Node<T> y = x.right;
Node<T> 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;
}
private Node<T> insert(Node<T> node, T key) {
if (node == null)
return new Node<>(key);
if (key.compareTo(node.data) < 0)
node.left = insert(node.left, key);
else if (key.compareTo(node.data) > 0)
node.right = insert(node.right, key);
else
return node;
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && key.compareTo(node.left.data) < 0)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key.compareTo(node.right.data) > 0)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key.compareTo(node.left.data) > 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key.compareTo(node.right.data) < 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
public void insert(T key) {
root = insert(root, key);
}
// ... 其他方法如删除、查找、遍历等
}
应用案例:
假设我们要构建一个AVL树来存储一组整数,并保持树的平衡状态。我们可以这样使用:
public class Main {
public static void main(String[] args) {
AVLTree<Integer> avlTree = new AVLTree<>();
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
avlTree.insert(25);
// 在此之后,avlTree应该是一个平衡的AVL树
}
}
以上代码展示了如何使用AVL树插入一些整数值,并自动调整树的平衡。在实际应用中,AVL树可以用于各种需要高效搜索、插入和删除操作的场景,比如数据库索引、符号表等。
下面,我将补充AVL树的删除、查找以及遍历方法。
删除操作
删除操作在AVL树中比较复杂,因为它涉及到保持树的平衡。在删除节点后,需要检查并修复可能的不平衡。
private Node<T> delete(Node<T> root, T key) {
if (root == null)
return root;
if (key.compareTo(root.data) < 0)
root.left = delete(root.left, key);
else if (key.compareTo(root.data) > 0)
root.right = delete(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.data = minValue(root.right);
root.right = delete(root.right, root.data);
}
root.height = Math.max(height(root.left), height(root.right)) + 1;
int balance = getBalance(root);
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);
if (balance > 1 && getBalance(root.left) < 0) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root.right) > 0) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
private T minValue(Node<T> node) {
T minv = node.data;
while (node.left != null) {
minv = node.left.data;
node = node.left;
}
return minv;
}
查找操作
查找操作在AVL树中相对简单,遵循二叉搜索树的查找规则。
public boolean contains(T key) {
return search(root, key) != null;
}
private Node<T> search(Node<T> node, T key) {
if (node == null || key.equals(node.data))
return node;
if (key.compareTo(node.data) < 0)
return search(node.left, key);
else
return search(node.right, key);
}
遍历操作
遍历操作包括前序遍历、中序遍历和后序遍历,这里展示中序遍历。
public void inorderTraversal() {
inorder(root);
}
private void inorder(Node<T> node) {
if (node != null) {
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
}
主方法使用示例
将上述代码整合进AVLTree
类中,然后在main
方法中使用:
public class Main {
public static void main(String[] args) {
AVLTree<Integer> avlTree = new AVLTree<>();
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
avlTree.insert(25);
System.out.println("Inorder traversal of the constructed AVL tree is");
avlTree.inorderTraversal();
System.out.println();
System.out.println("Deleting key 40");
avlTree.delete(40);
System.out.println("Inorder traversal after deletion is");
avlTree.inorderTraversal();
System.out.println();
System.out.println("Searching for key 25: " + avlTree.contains(25));
System.out.println("Searching for key 60: " + avlTree.contains(60));
}
}
这段代码演示了如何插入元素、遍历AVL树、删除元素以及查找元素。
以下是前序遍历和后序遍历的代码实现,我们将它们添加到之前的AVLTree
类中:
前序遍历
前序遍历的顺序是:根节点 -> 左子树 -> 右子树。
public void preorderTraversal() {
preorder(root);
}
private void preorder(Node<T> node) {
if (node != null) {
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
后序遍历
后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
public void postorderTraversal() {
postorder(root);
}
private void postorder(Node<T> node) {
if (node != null) {
postorder(node.left);
postorder(node.right);
System.out.print(node.data + " ");
}
}
更新主方法示例
我们更新main
方法来演示这些遍历方法:
public class Main {
public static void main(String[] args) {
AVLTree<Integer> avlTree = new AVLTree<>();
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
avlTree.insert(25);
System.out.println("Inorder traversal of the constructed AVL tree is");
avlTree.inorderTraversal();
System.out.println();
System.out.println("Preorder traversal of the constructed AVL tree is");
avlTree.preorderTraversal();
System.out.println();
System.out.println("Postorder traversal of the constructed AVL tree is");
avlTree.postorderTraversal();
System.out.println();
System.out.println("Deleting key 40");
avlTree.delete(40);
System.out.println("Inorder traversal after deletion is");
avlTree.inorderTraversal();
System.out.println();
System.out.println("Searching for key 25: " + avlTree.contains(25));
System.out.println("Searching for key 60: " + avlTree.contains(60));
}
}
这段代码展示了如何使用AVL树的各种遍历方法,包括中序遍历、前序遍历和后序遍历,以及插入、删除和查找操作。