أشجار AVL المتوازنة

int height(TreeNode node) {
    return node == null ? 0 : node.height;
}

int getBalance(TreeNode node) {
    return node == null ? 0 : height(node.left) - height(node.right);
}

TreeNode rotateRight(TreeNode y) {
    TreeNode x = y.left;
    TreeNode T2 = x.right;
    x.right = y;
    y.left = T2;
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    x.height = Math.max(height(x.left), height(x.right)) + 1;
    return x;
}

TreeNode rotateLeft(TreeNode x) {
    TreeNode y = x.right;
    TreeNode T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    return y;
}

TreeNode insert(TreeNode node, int value) {
    if (node == null) return new TreeNode(value);

    if (value < node.value)
        node.left = insert(node.left, value);
    else if (value > node.value)
        node.right = insert(node.right, value);
    else
        return node; // قيمة مكررة

    node.height = 1 + Math.max(height(node.left), height(node.right));

    int balance = getBalance(node);

    // LL
    if (balance > 1 && value < node.left.value)
        return rotateRight(node);

    // RR
    if (balance < -1 && value > node.right.value)
        return rotateLeft(node);

    // LR
    if (balance > 1 && value > node.left.value) {
        node.left = rotateLeft(node.left);
        return rotateRight(node);
    }

    // RL
    if (balance < -1 && value < node.right.value) {
        node.right = rotateRight(node.right);
        return rotateLeft(node);
    }

    return node;
}

BST avl = new BST();
// إدراج أرقام مرتبة (ستسبب ميل في BST عادية)
for (int i = 1; i <= 7; i++) {
    avl.root = avl.insert(avl.root, i);
}
// الشجرة تبقى متوازنة — الارتفاع O(log n) دائمًا