java代码如何实现平衡二叉树的旋转操作 java代码平衡树维护的基础编写教程​

// 节点类
class Node {
    int data;
    Node left, right;
    int height; // 节点高度

    Node(int d) {
        data = d;
        height = 1; // 新节点高度为1
    }
}

// 平衡二叉树类
class AVLTree {
    Node root;

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

    // 更新节点高度
    void updateHeight(Node node) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

    // 获取平衡因子（左子树高度 - 右子树高度）
    int getBalance(Node node) {
        if (node == null)
            return 0;
        return height(node.left) - height(node.right);
    }

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

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新高度
        updateHeight(y);
        updateHeight(x);

        // 返回新的根节点
        return x;
    }

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

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新高度
        updateHeight(x);
        updateHeight(y);

        // 返回新的根节点
        return y;
    }

    // 插入节点
    Node insert(Node node, int data) {
        // 1. 执行标准BST插入
        if (node == null)
            return (new Node(data));

        if (data < node.data)
            node.left = insert(node.left, data);
        else if (data > node.data)
            node.right = insert(node.right, data);
        else // 不允许重复值
            return node;

        // 2. 更新当前节点的高度
        updateHeight(node);

        // 3. 获取平衡因子
        int balance = getBalance(node);

        // 4. 如果节点不平衡，则有四种情况
        // 左左情况
        if (balance > 1 && data < node.left.data)
            return rightRotate(node);

        // 右右情况
        if (balance < -1 && data > node.right.data)
            return leftRotate(node);

        // 左右情况
        if (balance > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 右左情况
        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // 删除节点（简略，完整实现还需要考虑多种情况）
    Node deleteNode(Node root, int data) {
        if (root == null)
            return root;

        if (data < root.data)
            root.left = deleteNode(root.left, data);
        else if (data > root.data)
            root.right = deleteNode(root.right, data);
        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.data = temp.data;

                // 删除中序后继
                root.right = deleteNode(root.right, temp.data);
            }
        }

        // 如果树只有一个节点，则返回
        if (root == null)
            return root;

        // 2. 更新当前节点的高度
        updateHeight(root);

        // 3. 获取平衡因子
        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;
    }

    Node minValueNode(Node node) {
        Node current = node;

        /* 循环下降到最左边的叶子 */
        while (current.left != null)
            current = current.left;

        return current;
    }


    // 打印树（中序遍历）
    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrder(node.left);
            preOrder(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("Preorder traversal of constructed AVL tree is: ");
        tree.preOrder(tree.root);

        tree.root = tree.deleteNode(tree.root, 30);

        System.out.println("\nPreorder traversal after deletion of 30: ");
        tree.preOrder(tree.root);
    }
}