Java平衡二叉树实例分析

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它通过保持树的左右子树高度差不超过1来确保树的平衡性。平衡二叉树的常见实现包括AVL树和红黑树。本文将介绍如何使用Java实现一个简单的平衡二叉树，并通过实例分析其工作原理。

1. 平衡二叉树的基本概念

平衡二叉树的核心思想是通过旋转操作来调整树的结构，使得树的高度差保持在合理范围内。常见的旋转操作包括左旋和右旋。

• 左旋：将当前节点的右子节点提升为新的根节点，原根节点成为新根节点的左子节点。
• 右旋：将当前节点的左子节点提升为新的根节点，原根节点成为新根节点的右子节点。

通过这两种旋转操作，可以在插入或删除节点时保持树的平衡。

2. Java实现平衡二叉树

下面是一个简单的Java实现平衡二叉树的示例代码：

class Node {
    int key, height;
    Node left, right;

    Node(int d) {
        key = d;
        height = 1;
    }
}

class AVLTree {
    Node root;

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

    // 获取两个数的最大值
    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    // 右旋操作
    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // 左旋操作
    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        return y;
    }

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

    // 插入节点
    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 + 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;
    }

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

public class Main {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);

        System.out.println("中序遍历结果:");
        tree.inOrder(tree.root);
    }
}

3. 实例分析

在上述代码中，我们实现了一个简单的AVL树。通过插入节点10、20、30、40、50和25，我们可以看到树是如何通过旋转操作保持平衡的。

• 插入10：树中只有一个节点10，高度为1。
• 插入20：20插入到10的右子树，树的高度为2。
• 插入30：30插入到20的右子树，导致树不平衡，触发左旋操作，20成为新的根节点。
• 插入40：40插入到30的右子树，树的高度为3。
• 插入50：50插入到40的右子树，导致树不平衡，触发左旋操作，40成为新的根节点。
• 插入25：25插入到20的右子树，树的高度为4。

最终，通过中序遍历输出结果为：10 20 25 30 40 50，表明树的结构是正确的。

4. 总结

平衡二叉树通过旋转操作保持树的平衡性，确保在最坏情况下树的高度为O(log n)，从而保证了插入、删除和查找操作的时间复杂度为O(log n)。本文通过Java实现了一个简单的AVL树，并通过实例分析了其工作原理。希望本文能帮助读者更好地理解平衡二叉树的概念和实现。