跳转至

Java 实现 AVL 树：从基础到实践

简介

AVL 树是一种自平衡的二叉搜索树，由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年发明。它通过在每次插入或删除节点后进行平衡操作，确保树的高度始终保持在 $O(log n)$，从而保证了插入、删除和查找操作的时间复杂度均为 $O(log n)$。本文将详细介绍 AVL 树在 Java 中的实现，包括基础概念、使用方法、常见实践以及最佳实践。

目录

  1. AVL 树的基础概念
  2. Java 实现 AVL 树
  3. 使用方法
  4. 常见实践
  5. 最佳实践
  6. 小结
  7. 参考资料

1. AVL 树的基础概念

二叉搜索树（BST）

二叉搜索树是一种二叉树，对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这种特性使得二叉搜索树在查找、插入和删除操作上具有较好的时间复杂度。

平衡因子

AVL 树通过平衡因子来保持树的平衡。平衡因子是指一个节点的左子树的高度减去右子树的高度。在 AVL 树中，每个节点的平衡因子只能是 -1、0 或 1。如果某个节点的平衡因子的绝对值大于 1，则需要进行旋转操作来恢复树的平衡。

旋转操作

为了保持树的平衡，AVL 树引入了四种旋转操作：左旋、右旋、左右旋和右左旋。 - 左旋：当某个节点的右子树高度过高时，需要进行左旋操作。 - 右旋：当某个节点的左子树高度过高时，需要进行右旋操作。 - 左右旋：先对左子树进行左旋，再对该节点进行右旋。 - 右左旋：先对右子树进行右旋，再对该节点进行左旋。

2. Java 实现 AVL 树

class AVLTree {
    private class Node {
        int key;
        int height;
        Node left;
        Node right;

        Node(int key) {
            this.key = key;
            this.height = 1;
        }
    }

    private Node root;

    // 获取节点的高度
    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    // 获取平衡因子
    private int getBalance(Node node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    // 右旋操作
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node 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 leftRotate(Node x) {
        Node y = x.right;
        Node 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 insert(Node node, int key) {
        if (node == null) {
            return new Node(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;
        }

        node.height = 1 + Math.max(height(node.left), height(node.right));

        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 insert(int key) {
        root = insert(root, key);
    }

    // 中序遍历
    private void inorder(Node node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.key + " ");
            inorder(node.right);
        }
    }

    public void inorder() {
        inorder(root);
    }
}

public class Main {
    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);

        tree.inorder();
    }
}

3. 使用方法

插入节点

通过调用 insert 方法可以向 AVL 树中插入一个新的节点。例如：

AVLTree tree = new AVLTree();
tree.insert(10);
tree.insert(20);

遍历树

可以使用中序遍历方法 inorder 来遍历 AVL 树中的所有节点。例如：

tree.inorder();

4. 常见实践

查找操作

可以在 AVL 树中实现查找操作，通过递归或迭代的方式找到指定值的节点。

private Node search(Node node, int key) {
    if (node == null || node.key == key) {
        return node;
    }

    if (key < node.key) {
        return search(node.left, key);
    }

    return search(node.right, key);
}

public Node search(int key) {
    return search(root, key);
}

删除操作

删除操作相对复杂，需要考虑多种情况，并且在删除节点后需要进行平衡操作。

private Node minValueNode(Node node) {
    Node current = node;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

private Node deleteNode(Node root, int key) {
    if (root == null) {
        return root;
    }

    if (key < root.key) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.key) {
        root.right = deleteNode(root.right, key);
    } else {
        if (root.left == null || root.right == null) {
            Node temp = null;
            if (temp == root.left) {
                temp = root.right;
            } else {
                temp = root.left;
            }

            if (temp == null) {
                temp = root;
                root = null;
            } else {
                root = temp;
            }
        } else {
            Node temp = minValueNode(root.right);
            root.key = temp.key;
            root.right = deleteNode(root.right, temp.key);
        }
    }

    if (root == null) {
        return root;
    }

    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.left) < 0) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }

    // 右右情况
    if (balance < -1 && getBalance(root.right) <= 0) {
        return leftRotate(root);
    }

    // 右左情况
    if (balance < -1 && getBalance(root.right) > 0) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }

    return root;
}

public void delete(int key) {
    root = deleteNode(root, key);
}

5. 最佳实践

异常处理

在插入、删除和查找操作中，需要考虑边界情况，例如插入重复值、删除不存在的节点等，并进行相应的异常处理。

性能优化

在实际应用中，可以根据具体需求对 AVL 树进行性能优化，例如使用迭代代替递归，减少栈空间的使用。

6. 小结

本文详细介绍了 AVL 树的基础概念，包括二叉搜索树、平衡因子和旋转操作。通过 Java 代码实现了 AVL 树的插入、遍历、查找和删除操作，并介绍了使用方法、常见实践和最佳实践。AVL 树在需要高效查找、插入和删除操作的场景中具有很好的性能表现，但在插入和删除操作时需要进行额外的平衡操作，会增加一定的时间复杂度。

7. 参考资料

  • "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
  • Wikipedia: AVL tree (https://en.wikipedia.org/wiki/AVL_tree){: rel="nofollow"}