Java 数据结构篇-实现 AVL 树的核心方法

public class AVLTree<T extends Comparable<T>> {
    private Node<T> root;
 
    // 内部节点类
    private static class Node<T> {
        T data;
        Node<T> left;
        Node<T> right;
        int height;
 
        Node(T data) {
            this.data = data;
            left = null;
            right = null;
            height = 1;
        }
    }
 
    // 插入节点的方法
    public void insert(T data) {
        root = insert(root, data);
    }
 
    // 计算节点高度的方法
    private int height(Node<T> node) {
        return node == null ? 0 : node.height;
    }
 
    // 获取平衡因子的方法
    private int getBalance(Node<T> node) {
        return height(node.left) - height(node.right);
    }
 
    // 更新节点高度的方法
    private void updateHeight(Node<T> node) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }
 
    // 左旋转的方法
    private Node<T> rotateLeft(Node<T> node) {
        Node<T> temp = node.right;
        node.right = temp.left;
        temp.left = node;
        updateHeight(node);
        updateHeight(temp);
        return temp;
    }
 
    // 右旋转的方法
    private Node<T> rotateRight(Node<T> node) {
        Node<T> temp = node.left;
        node.left = temp.right;
        temp.right = node;
        updateHeight(node);
        updateHeight(temp);
        return temp;
    }
 
    // 插入节点并保持平衡的方法
    private Node<T> insert(Node<T> node, T data) {
        if (node == null) {
            return new Node<>(data);
        }
 
        if (data.compareTo(node.data) < 0) {
            node.left = insert(node.left, data);
        } else if (data.compareTo(node.data) > 0) {
            node.right = insert(node.right, data);
        } else {
            return node;
        }
 
        int balance = getBalance(node);
 
        if (balance > 1 && data.compareTo(node.left.data) < 0) {
            return rotateRight(node);
        }
 
        if (balance < -1 && data.compareTo(node.right.data) > 0) {
            return rotateLeft(node);
        }
 
        if (balance > 1 && data.compareTo(node.left.data) > 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
 
        if (balance < -1 && data.compareTo(node.right.data) < 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }
 
        updateHeight(node);
        return node;
    }
}

这段代码实现了AVL树的插入操作，包括旋转和重新计算高度等操作。它展示了