1. Estrutura e Operações Básicas

A WBLT é uma árvore onde todas as informações (valores) são armazenadas nas folhas. Os nós internos servem apenas para combinar informações dos filhos e garantir o balanceamento. Um nó não-folha sempre possui exatamente dois filhos.

1.1 Informações do Nó

Cada nó armazena: ch[x][2] (ponteiros para os filhos esquerdo e direito), siz[x] (número de folhas na subárvore) e val[x] (maior chave na subárvore).

class Node {
public:
    int val, siz;
    int left, right;
} tree[200200];

#define LEFT(x) tree[x].left
#define RIGHT(x) tree[x].right
#define VAL(x) tree[x].val
#define SIZ(x) tree[x].siz

1.2 Funções Auxiliares

As funções update(x), newNode(v), del(x), join(x, y) e cut(x) manipulam a estrutura.

void update(int x) {
    SIZ(x) = SIZ(LEFT(x)) + SIZ(RIGHT(x));
    VAL(x) = VAL(RIGHT(x));
}

int newNode(int v = 0) {
    int x = (top > 0) ? stack[top--] : ++cnt;
    SIZ(x) = LEFT(x) = RIGHT(x) = 0;
    VAL(x) = v;
    SIZ(x) = 1;
    return x;
}

void del(int &x) {
    stack[++top] = x;
    x = 0;
}

int join(int x, int y) {
    int z = newNode();
    LEFT(z) = x;
    RIGHT(z) = y;
    update(z);
    return z;
}

pair<int, int> cut(int &x) {
    int l = LEFT(x), r = RIGHT(x);
    del(x);
    return {l, r};
}

1.3 Balanceamento

O balanceamento é o núcleo da WBLT. Para um nó x, definimos seu fator de balanceamento ρ como:

A rotação é usada para manter o balanceamento. Se um filho é muito pesado, uma rotação simples ou dupla é aplicada, dependendo de uma constante β = 1/(2 - α).

const double alpha = 0.292;

void rotate(int &x, bool isRight) {
    int a, b, c, d;
    tie(a, b) = cut(x);
    if (isRight) {
        tie(c, d) = cut(b);
        x = join(join(a, c), d);
    } else {
        tie(c, d) = cut(a);
        x = join(c, join(d, b));
    }
}

bool isHeavy(int a, int b) {
    return b < alpha * (a + b);
}

bool needsDoubleRotate(int x, bool childDir) {
    return SIZ(getChild(x, childDir)) > SIZ(x) / (2 - alpha);
}

void balance(int &x) {
    if (SIZ(x) == 1) return;
    bool biggerChild = SIZ(RIGHT(x)) > SIZ(LEFT(x));
    if (!isHeavy(SIZ(getChild(x, biggerChild)), SIZ(getChild(x, !biggerChild)))) return;
    if (needsDoubleRotate(getChild(x, biggerChild), !biggerChild)) {
        rotate(getChildRef(x, biggerChild), !biggerChild);
    }
    rotate(x, biggerChild);
}

1.4 Inserção e Remoção

Para inserir um valor, encontramos seu predecessor/sucessor e criamos um novo nó pai. Para remover, o nó filho do lado oposto substitui o pai.

void insert(int &root, int value) {
    if (!root) {
        root = newNode(value);
        return;
    }
    if (SIZ(root) == 1) {
        bool goRight = (value >= VAL(root));
        setChild(root, goRight, newNode(value));
        setChild(root, !goRight, newNode(VAL(root)));
        update(root);
        return;
    }
    bool goRight = (value > VAL(LEFT(root)));
    insert(getChildRef(root, goRight), value);
    update(root);
    balance(root);
}

void remove(int &root, int value) {
    if (!root) return;
    if (SIZ(root) == 1) {
        if (VAL(root) == value) del(root);
        return;
    }
    bool goRight = (value > VAL(LEFT(root)));
    remove(getChildRef(root, goRight), value);
    if (!getChild(root, goRight)) {
        root = getChild(root, !goRight);
        return;
    }
    update(root);
    balance(root);
}

1.5 Consultas

As funções de consulta (rank, kth, predecessor, sucessor) são implementadas de forma similar à busca binária em uma árvore de segmentos.

1.6 Merge (Intercalação)

Para fundir duas árvores, se uma for muito maior que a outra, ela é dividida e mesclada recursivamente. Caso contrário, a fusão é direta.

int merge(int x, int y) {
    if (!x || !y) return x + y;
    int a, b;
    if (isHeavy(SIZ(x), SIZ(y))) {
        tie(a, b) = cut(x);
        int z = join(a, merge(b, y));
        balance(z);
        return z;
    } else if (isHeavy(SIZ(y), SIZ(x))) {
        tie(a, b) = cut(y);
        int z = join(merge(x, a), b);
        balance(z);
        return z;
    } else {
        return join(x, y);
    }
}

1.7 Split (Divisão)

Divide a árvore em duas com base em um tamanho k.

pair<int, int> split(int x, int k) {
    if (!x) return {0, 0};
    if (k == 0) return {0, x};
    if (k == SIZ(x)) return {x, 0};
    int a, b, c, d;
    tie(a, b) = cut(x);
    if (k <= SIZ(a)) {
        tie(c, d) = split(a, k);
        return {c, merge(d, b)};
    } else {
        tie(c, d) = split(b, k - SIZ(a));
        return {merge(a, c), d};
    }
}

2. Análise de Rotação e Balanceamento

O balanceamento da árvore é garantido pelas operações de rotação. A análise matemática a seguir demosntra que, com a escolha apropriada de α e β, as rotações mantêm o fator de balanceamento dentro dos limites desejados.

As fórmulas para o novo fator de balanceamento após rotação simples e dupla são derivadas a partir das definições dos tamanhos das subárvores.

3. Análise da Operação Merge

A prova de que a operação merge preesrva o balanceamento e tem complexidade O(log n) é baseada na análise dos tamanhos relativos das subárvores e nas constantes α e β.

A complexidade da operação merge é O(log (x/y)), onde x e y são os tamanhos das árvores a serem fundidas.

4. Análise da Operação Split

A operação split também possui complexidade O(log n). A análise é feita considerando o tamanho da subárvore a ser separada e a profundidade da recursão.

5. Código Completo

Os códigos completos para uma árvore balanceada simples e uma árvore de intervaol reversível (ágil/recreational) são fornecidos a seguir.

</details><details><summary>Árvore de Intervalo Reversível</summary>```
// Implementação de uma WBLT com lazy propagation para reversão de intervalo.
// Inclui funções como build, reverse, e merge para construir a árvore inicial.
// A função split divide a árvore em duas com base no número de folhas.