Fator de balanceamento = altura(esquerda) - altura(direita)
Valores válidos: -1, 0, +1

Rotação simples à direita (LL):      Rotação simples à esquerda (RR):
      z            y                    x           y
     / \         /   \                 / \        /   \
    y   T4 →    x     z              T1  y   →  x     z
   / \         / \   / \                / \    / \   / \
  x  T3       T1 T2 T3 T4             T2  z  T1 T2 T3 T4
 / \                                      / \
T1 T2                                    T3 T4

Rotação dupla LR:              Rotação dupla RL:
    z         z         x        z        z         x
   / \       / \      /   \     / \      / \      /   \
  y   T4 →  x  T4 → y     z   T1  y →  T1  x → z     y
 / \       / \      / \   / \     / \      / \  / \   / \
T1  x     y  T3    T1 T2 T3 T4  x  T4    T2  y T1 T2 T3 T4
   / \   / \                    / \          / \
  T2 T3 T1 T2                 T2 T3        T3 T4

const std = @import("std");
const Allocator = std.mem.Allocator;

pub fn AVL(comptime T: type) type {
    return struct {
        const Self = @This();

        pub const No = struct {
            valor: T,
            esquerdo: ?*No,
            direito: ?*No,
            altura: i32,
        };

        raiz: ?*No,
        tamanho: usize,
        allocator: Allocator,

        pub fn init(allocator: Allocator) Self {
            return .{ .raiz = null, .tamanho = 0, .allocator = allocator };
        }

        pub fn deinit(self: *Self) void {
            liberarNo(self.allocator, self.raiz);
        }

        fn liberarNo(allocator: Allocator, no: ?*No) void {
            if (no) |n| {
                liberarNo(allocator, n.esquerdo);
                liberarNo(allocator, n.direito);
                allocator.destroy(n);
            }
        }

        fn alturaDe(no: ?*const No) i32 {
            return if (no) |n| n.altura else 0;
        }

        fn fatorBalanceamento(no: *const No) i32 {
            return alturaDe(no.esquerdo) - alturaDe(no.direito);
        }

        fn atualizarAltura(no: *No) void {
            no.altura = 1 + @max(alturaDe(no.esquerdo), alturaDe(no.direito));
        }

        fn rotacaoDireita(y: *No) *No {
            const x = y.esquerdo.?;
            y.esquerdo = x.direito;
            x.direito = y;
            atualizarAltura(y);
            atualizarAltura(x);
            return x;
        }

        fn rotacaoEsquerda(x: *No) *No {
            const y = x.direito.?;
            x.direito = y.esquerdo;
            y.esquerdo = x;
            atualizarAltura(x);
            atualizarAltura(y);
            return y;
        }

        fn balancear(no: *No) *No {
            atualizarAltura(no);
            const fb = fatorBalanceamento(no);

            // Caso LL
            if (fb > 1 and fatorBalanceamento(no.esquerdo.?) >= 0)
                return rotacaoDireita(no);

            // Caso RR
            if (fb < -1 and fatorBalanceamento(no.direito.?) <= 0)
                return rotacaoEsquerda(no);

            // Caso LR
            if (fb > 1 and fatorBalanceamento(no.esquerdo.?) < 0) {
                no.esquerdo = rotacaoEsquerda(no.esquerdo.?);
                return rotacaoDireita(no);
            }

            // Caso RL
            if (fb < -1 and fatorBalanceamento(no.direito.?) > 0) {
                no.direito = rotacaoDireita(no.direito.?);
                return rotacaoEsquerda(no);
            }

            return no;
        }

        /// Insere um valor — O(log n).
        pub fn inserir(self: *Self, valor: T) !void {
            self.raiz = try inserirNo(self.allocator, self.raiz, valor);
            self.tamanho += 1;
        }

        fn inserirNo(allocator: Allocator, no: ?*No, valor: T) !*No {
            if (no == null) {
                const novo = try allocator.create(No);
                novo.* = .{ .valor = valor, .esquerdo = null, .direito = null, .altura = 1 };
                return novo;
            }
            const n = no.?;
            if (valor < n.valor) {
                n.esquerdo = try inserirNo(allocator, n.esquerdo, valor);
            } else if (valor > n.valor) {
                n.direito = try inserirNo(allocator, n.direito, valor);
            } else return n; // duplicata

            return balancear(n);
        }

        /// Busca — O(log n).
        pub fn buscar(self: *const Self, valor: T) bool {
            var atual = self.raiz;
            while (atual) |no| {
                if (valor == no.valor) return true;
                atual = if (valor < no.valor) no.esquerdo else no.direito;
            }
            return false;
        }

        /// Remove — O(log n).
        pub fn remover(self: *Self, valor: T) void {
            var removido = false;
            self.raiz = removerNo(self.allocator, self.raiz, valor, &removido);
            if (removido) self.tamanho -= 1;
        }

        fn removerNo(allocator: Allocator, no: ?*No, valor: T, removido: *bool) ?*No {
            if (no == null) return null;
            const n = no.?;

            if (valor < n.valor) {
                n.esquerdo = removerNo(allocator, n.esquerdo, valor, removido);
            } else if (valor > n.valor) {
                n.direito = removerNo(allocator, n.direito, valor, removido);
            } else {
                removido.* = true;
                if (n.esquerdo == null or n.direito == null) {
                    const filho = n.esquerdo orelse n.direito;
                    allocator.destroy(n);
                    return filho;
                }
                // Sucessor in-order
                var suc = n.direito.?;
                while (suc.esquerdo) |e| suc = e;
                n.valor = suc.valor;
                n.direito = removerNo(allocator, n.direito, suc.valor, &(struct { v: bool }{ .v = false }).v);
            }

            return balancear(n);
        }

        /// Travessia in-order.
        pub fn inOrder(self: *const Self, allocator: Allocator) ![]T {
            var res = std.ArrayList(T).init(allocator);
            inOrderHelper(self.raiz, &res) catch {};
            return try res.toOwnedSlice();
        }

        fn inOrderHelper(no: ?*const No, res: *std.ArrayList(T)) !void {
            if (no == null) return;
            const n = no.?;
            try inOrderHelper(n.esquerdo, res);
            try res.append(n.valor);
            try inOrderHelper(n.direito, res);
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var avl = AVL(i32).init(allocator);
    defer avl.deinit();

    // Inserção sequencial (pior caso para BST normal, mas AVL balanceia)
    for ([_]i32{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }) |v| {
        try avl.inserir(v);
    }

    try stdout.print("Tamanho: {d}\n", .{avl.tamanho});
    try stdout.print("Altura da raiz: {d} (log2(10)≈3.3)\n", .{avl.raiz.?.altura});
    try stdout.print("Raiz: {d}\n", .{avl.raiz.?.valor});

    const ordenado = try avl.inOrder(allocator);
    defer allocator.free(ordenado);
    try stdout.print("In-order: ", .{});
    for (ordenado) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});

    // Busca
    try stdout.print("Buscar 7: {}\n", .{avl.buscar(7)});
    try stdout.print("Buscar 11: {}\n", .{avl.buscar(11)});

    // Remoção
    avl.remover(4);
    avl.remover(7);
    try stdout.print("Após remover 4 e 7, tamanho: {d}\n", .{avl.tamanho});
}