JavaDS —— AVL树

在Java中实现一个AVL树，您可以定义一个内部节点类，并在该类中实现插入、删除和旋转操作。以下是一个简化的JavaDS AVL树实现的示例：

public class AVLTree {
 
    private static class Node {
        int key;
        int height;
        Node left;
        Node right;
 
        Node(int key) {
            this.key = key;
            height = 1;
        }
    }
 
    private Node root;
 
    public Node getRoot() {
        return root;
    }
 
    private int getHeight(Node node) {
        return node == null ? 0 : node.height;
    }
 
    private int getBalance(Node node) {
        return getHeight(node.left) - getHeight(node.right);
    }
 
    private Node rotateRight(Node node) {
        Node temp = node.left;
        node.left = temp.right;
        temp.right = node;
        
        // Update heights
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        temp.height = Math.max(getHeight(temp.left), node.height) + 1;
        
        return temp;
    }
 
    private Node rotateLeft(Node node) {
        Node temp = node.right;
        node.right = temp.left;
        temp.left = node;
        
        // Update heights
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        temp.height = Math.max(getHeight(temp.right), node.height) + 1;
        
        return temp;
    }
 
    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 {
            // Duplicate keys not allowed
            return node;
        }
 
        // Update balance factor and nodes height and return new root
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
        int balance = getBalance(node);
        
        // Left left case
        if (balance > 1 && key < node.left.key)
            return rotateRight(node);
        
        // Right right case
        if (balance < -1 && key > node.right.key)
            return rotateLeft(node);
        
        // Left right case
        if (balance > 1 && key > node.left.key) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        
        // Right left case
        if (balance < -1 && key < node.right.key) {
            node.right = rot