java平衡二叉树平衡因子

平衡二叉树的平衡因子是指每个节点的左子树高度减去右子树高度的值。平衡因子可以用来判断一个节点是否平衡，如果平衡因子的绝对值大于1，则该节点不平衡。

在Java中实现平衡二叉树时，可以通过计算每个节点的平衡因子来判断是否需要进行平衡操作。当插入或删除节点后，如果某个节点的平衡因子超过了1或小于-1，就需要进行相应的平衡操作，以保持树的平衡性。

以下是一个示例代码，演示了如何计算平衡二叉树的平衡因子：

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class AVLTree {
    Node root;

    // 计算节点的高度
    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    // 计算节点的平衡因子
    private int balanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    // 插入节点
    public void insert(int value) {
        root = insertNode(root, value);
    }

    private Node insertNode(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }
        if (value < node.value) {
            node.left = insertNode(node.left, value);
        } else if (value > node.value) {
            node.right = insertNode(node.right, value);
        } else {
            // 如果节点值已存在，则不进行插入操作
            return node;
        }

        // 更新节点的平衡因子
        int balance = balanceFactor(node);

        // 左子树不平衡
        if (balance > 1) {
            if (value < node.left.value) {
                // 左-左情况，进行右旋转
                return rightRotate(node);
            } else {
                // 左-右情况，先左旋转再右旋转
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }
        }

        // 右子树不平衡
        if (balance < -1) {
            if (value > node.right.value) {
                // 右-右情况，进行左旋转
                return leftRotate(node);
            } else {
                // 右-左情况，先右旋转再左旋转
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }
        }

        return node;
    }

    // 左旋转
    private Node leftRotate(Node node) {
        Node newRoot = node.right;
        node.right = newRoot.left;
        newRoot.left = node;
        return newRoot;
    }

    // 右旋转
    private Node rightRotate(Node node) {
        Node newRoot = node.left;
        node.left = newRoot.right;
        newRoot.right = node;
        return newRoot;
    }
}

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);
    }
}