Árvores balanceadas: AVL e rubro-negra

Uma árvore binária de busca é rápida enquanto é “baixa”. Mas, se as chaves chegam em ordem, ela vira uma lista e a busca volta a ser O(n). Hoje vamos ver duas árvores que se reorganizam sozinhas para manter a altura em O(log n).

fb ∈ {−1, 0, +1}AVLaltura e fator de balanceamento ↻ ↺Rotaçõessimples, duplas, inserção e remoção ● ●Rubro-negracores, altura preta e recolorações ✓ 6Práticaexercícios com correção automática

Navegação: ← → trocam de etapa · V alterna entre etapas e página única · M sumário · F tela cheia · + − tamanho do texto · dentro do código, Ctrl+Enter executa.

Todo código desta aula pode ser editado e executado aqui mesmo. Altere os exemplos à vontade; o botão ↺ restaura o original. Suas alterações ficam salvas neste navegador; em Progresso você pode baixá-las em um arquivo e continuar em outro computador.

As visualizações mostram os algoritmos passo a passo: digite valores, use Próximo passo ou Animar. Nos exercícios, o botão ✓ Verificar testa seu código com várias entradas.

Relembrando: árvore binária de busca

Em uma ABB, para cada nó: tudo à esquerda é menor e tudo à direita é maior. Buscar e inserir é descer da raiz, escolhendo um lado a cada nó.

O custo é o número de níveis percorridos: a altura da árvore. Nesta aula, a altura de uma árvore vazia é 0 e a de uma folha é 1 (altura = quantidade de nós no caminho mais longo da raiz até uma folha).

buscar → O(altura)inserir → O(altura)remover → O(altura)

O problema da degeneração

A forma da ABB depende da ordem de inserção. Inserindo chaves aleatórias, a altura fica em O(log n), em geral entre 2 e 3 vezes log₂ n. Inserindo chaves já ordenadas, cada nova chave vai sempre para a direita: a árvore vira uma lista e a altura é n.

E dados ordenados são comuns: matrículas, datas, códigos sequenciais…

A ideia do balanceamento

Manter a árvore perfeitamente balanceada custaria caro demais a cada inserção. As árvores balanceadas relaxam a exigência, só o suficiente para garantir altura O(log n):

Árvore	Regra
AVL	as alturas das subárvores de cada nó diferem em no máximo 1
Rubro-negra	regras de cores que impedem um caminho de ter mais que o dobro do tamanho de outro

Com 1.000 chaves em ordem, buscar a última custa 1.000 comparações. Uma árvore balanceada precisaria de no máximo uns 10 a 20.

Altura e fator de balanceamento

Na árvore AVL (Adelson-Velsky e Landis, 1962), cada nó guarda sua altura e calculamos o fator de balanceamento:

fb(nó) = altura(nó.esq) − altura(nó.dir)

fb	Significado
`0`	subárvores com a mesma altura
`+1`	esquerda um nível mais alta
`−1`	direita um nível mais alta
`±2`	desbalanceado: precisa de rotação

Guardar a altura no nó evita recalcular a árvore inteira: ela é atualizada só no caminho que mudou, de baixo para cima: altura = 1 + max(altura(esq), altura(dir)).

Na saída, a raiz fica à esquerda e a direita da árvore fica para cima. Qual nó ficou com fb = +2?

A invariante AVL

Uma ABB é AVL quando todos os nós têm fb igual a −1, 0 ou +1. Não basta olhar a raiz: um nó lá embaixo pode estar desbalanceado.

Só duas operações podem quebrar a invariante: inserir e remover. Elas mudam alturas apenas no caminho entre a raiz e o nó alterado; é ali que procuramos o desbalanceamento e o consertamos com rotações.

Execute e compare: a terceira árvore tem a raiz equilibrada (fb = +1), mas não é AVL.

Esta versão recalcula alturas em cada nó: O(n²) no pior caso. Os exercícios mostram como fazer em O(n), devolvendo a altura e a resposta juntas.

Por que a altura é O(log n)?

Pergunta ao contrário: qual é o menor número de nós N(h) de uma AVL de altura h? A árvore mais “magra” possível tem uma raiz, uma subárvore de altura h−1 e outra de altura h−2.

N(h) = N(h−1) + N(h−2) + 1 é quase a sequência de Fibonacci, que cresce como 1,618ʰ. Se até a AVL mais magra tem um número de nós exponencial na altura, então a altura é logarítmica no número de nós.

Resultado: a altura de uma AVL com n nós é no máximo cerca de 1,44 · log₂ n. Com um milhão de chaves: no máximo 28 níveis.

Rotações simples

Uma rotação troca pai e filho de lugar, mudando só 2 ponteiros dentro da subárvore (mais a ligação do pai com a nova raiz) e mantendo a ordem da ABB. É uma operação O(1).

Rotação à direita em z (usada quando z pende para a esquerda): o filho esquerdo y sobe, z desce para a direita de y e a subárvore direita de y (T2) passa a ser a esquerda de z.

Rotação à esquerda é o espelho: troque esq por dir em todo lugar.

Depois de rotacionar, atualize a altura de z antes da de y: agora z é filho de y.

Os quatro casos de desbalanceamento

Seja z o nó desbalanceado mais baixo (fb = ±2). O lado para onde ele pende e o fb do filho desse lado decidem a rotação. Escolha o caso e avance os passos.

Caso	fb(z)	fb do filho pesado	Solução
LL esquerda-esquerda	+2	esquerdo com fb ≥ 0	rotação à direita em z
RR direita-direita	−2	direito com fb ≤ 0	rotação à esquerda em z
LR esquerda-direita	+2	esquerdo com fb −1	à esquerda no filho, depois à direita em z
RL direita-esquerda	−2	direito com fb +1	à direita no filho, depois à esquerda em z

Nos desenhos, T1…T4 são subárvores quaisquer e o número pequeno ao lado é a altura de cada uma (h, h+1…). Nos nós x, y e z, o número é o fator de balanceamento.

Rotações duplas

No caso LR o peso está no “joelho”: z pende para a esquerda, mas o filho esquerdo pende para a direita (um triângulo). Uma rotação simples só espelharia o problema.

A solução é rotacionar duas vezes: primeiro à esquerda no filho, o que transforma o triângulo em linha (caso LL), e depois à direita em z. O neto sobe duas posições e vira a raiz da subárvore.

O caso RL é o espelho.

30, 10, 20 → LR10, 30, 20 → RL

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None
        self.altura = 1

def altura(no):
    return no.altura if no else 0

def atualiza(no):
    no.altura = 1 + max(altura(no.esq), altura(no.dir))

def rot_direita(z):
    y = z.esq
    z.esq = y.dir
    y.dir = z
    atualiza(z); atualiza(y)
    return y

def rot_esquerda(z):
    y = z.dir
    z.dir = y.esq
    y.esq = z
    atualiza(z); atualiza(y)
    return y

def pre_ordem(no):
    return [] if no is None else [no.chave] + pre_ordem(no.esq) + pre_ordem(no.dir)

# 30 com filho esquerdo 10, que tem filho direito 20 (caso LR)
z = No(30); z.esq = No(10); z.esq.dir = No(20)
atualiza(z.esq); atualiza(z)

tentativa = rot_direita(z)              # só uma rotação: não resolve
print("simples:", pre_ordem(tentativa), "-> agora pende para a direita")

z = No(30); z.esq = No(10); z.esq.dir = No(20)
atualiza(z.esq); atualiza(z)
z.esq = rot_esquerda(z.esq)             # 1ª: vira o caso LL
r = rot_direita(z)                      # 2ª: resolve
print("dupla:  ", pre_ordem(r), "altura", r.altura)

Qual rotação?

Desenhe a árvore no papel, calcule os fatores e só então clique. As inserções partem de uma árvore vazia.

Inserção na AVL

Insira como em uma ABB comum (recursivamente).
Na volta da recursão, cada nó do caminho atualiza sua altura e confere seu fb.
Se fb = ±2, aplique a rotação do caso e devolva a nova raiz da subárvore, que o pai pendura no lugar certo (no.esq = inserir(...)).

Na inserção, uma única rotação (simples ou dupla) basta: a subárvore volta à altura que tinha antes, e os ancestrais acima não mudam.

Custo: descer O(log n) + subir O(log n) + rotação O(1) = O(log n).

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None
        self.altura = 1

def altura(no):
    return no.altura if no else 0

def fb(no):
    return altura(no.esq) - altura(no.dir)

def atualiza(no):
    no.altura = 1 + max(altura(no.esq), altura(no.dir))

def rot_direita(z):
    y = z.esq
    z.esq = y.dir
    y.dir = z
    atualiza(z); atualiza(y)
    return y

def rot_esquerda(z):
    y = z.dir
    z.dir = y.esq
    y.esq = z
    atualiza(z); atualiza(y)
    return y

def balancear(no):
    atualiza(no)
    if fb(no) > 1:                      # pende para a esquerda
        if fb(no.esq) < 0:              # caso LR
            no.esq = rot_esquerda(no.esq)
        return rot_direita(no)          # caso LL
    if fb(no) < -1:                     # pende para a direita
        if fb(no.dir) > 0:              # caso RL
            no.dir = rot_direita(no.dir)
        return rot_esquerda(no)         # caso RR
    return no

def inserir(no, chave):
    if no is None:
        return No(chave)
    if chave < no.chave:
        no.esq = inserir(no.esq, chave)
    elif chave > no.chave:
        no.dir = inserir(no.dir, chave)
    else:
        return no                       # repetida: ignora
    return balancear(no)

def mostrar(no, nivel=0):
    if no:
        mostrar(no.dir, nivel + 1)
        print("      " * nivel + f"{no.chave} (fb={fb(no)})")
        mostrar(no.esq, nivel + 1)

raiz = None
for x in range(1, 16):                  # chaves em ordem: o pior caso da ABB
    raiz = inserir(raiz, x)
mostrar(raiz)
print("altura:", raiz.altura, "com 15 chaves")

AVL passo a passo

Digite valores (separados por espaço) e clique em Inserir: eles entram na árvore atual, um de cada vez. O número ao lado de cada nó é o seu fator de balanceamento.

Comece com Crescente 1–10 e observe: sem as rotações, essa seria a lista degenerada de altura 10. Depois clique em Limpar e experimente 30 10 20 (caso LR) e, de novo a partir da árvore vazia, 10 30 20 (caso RL).

Remoção na AVL

A remoção segue a da ABB:

nó com 0 ou 1 filho: o filho (ou None) toma o lugar dele;
nó com 2 filhos: copia o sucessor (menor da subárvore direita) e remove o sucessor lá embaixo.

Na volta da recursão, cada nó chama o mesmo balancear. Duas diferenças em relação à inserção:

o filho pesado pode ter fb = 0; aí a rotação simples resolve (por isso o teste é < 0 e > 0, e não != 0);
uma rotação pode diminuir a altura da subárvore, desbalanceando um ancestral: na remoção podem ocorrer até O(log n) rotações.

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None
        self.altura = 1

def altura(no): return no.altura if no else 0
def fb(no): return altura(no.esq) - altura(no.dir)
def atualiza(no): no.altura = 1 + max(altura(no.esq), altura(no.dir))

def rot_direita(z):
    y = z.esq; z.esq = y.dir; y.dir = z
    atualiza(z); atualiza(y)
    return y

def rot_esquerda(z):
    y = z.dir; z.dir = y.esq; y.esq = z
    atualiza(z); atualiza(y)
    return y

def balancear(no):
    atualiza(no)
    if fb(no) > 1:
        if fb(no.esq) < 0:
            no.esq = rot_esquerda(no.esq)
        return rot_direita(no)
    if fb(no) < -1:
        if fb(no.dir) > 0:
            no.dir = rot_direita(no.dir)
        return rot_esquerda(no)
    return no

def inserir(no, chave):
    if no is None: return No(chave)
    if chave < no.chave: no.esq = inserir(no.esq, chave)
    elif chave > no.chave: no.dir = inserir(no.dir, chave)
    return balancear(no)

def remover(no, chave):
    if no is None:
        return None
    if chave < no.chave:
        no.esq = remover(no.esq, chave)
    elif chave > no.chave:
        no.dir = remover(no.dir, chave)
    else:
        if no.esq is None: return no.dir
        if no.dir is None: return no.esq
        suc = no.dir
        while suc.esq:
            suc = suc.esq
        no.chave = suc.chave            # copia o sucessor
        no.dir = remover(no.dir, suc.chave)
    return balancear(no)

def pre_ordem(no):
    return [] if no is None else [no.chave] + pre_ordem(no.esq) + pre_ordem(no.dir)

raiz = None
for x in [20, 10, 30, 5, 25, 40, 35]:
    raiz = inserir(raiz, x)
print("inicial:      ", pre_ordem(raiz))
raiz = remover(raiz, 5)      # 10 fica sem filhos; 20 passa a pender para a direita
print("sem o 5:      ", pre_ordem(raiz))
raiz = remover(raiz, 30)     # nó com dois filhos
print("sem o 30:     ", pre_ordem(raiz), "altura", raiz.altura)

Árvore rubro-negra: as cinco propriedades

Em vez de alturas, cada nó guarda um bit de cor. Uma ABB é rubro-negra quando:

Todo nó é vermelho ou preto.
A raiz é preta.
As folhas nulas (None, chamadas de NIL) são consideradas pretas.
Um nó vermelho não tem filho vermelho (não há dois vermelhos seguidos).
Todo caminho de um nó até as folhas nulas abaixo dele passa pelo mesmo número de nós pretos.

Árvore montada a partir de 10 20 30 15 25 5 1 28. Volte os passos para ver como ela chegou aqui.

Altura preta e a garantia de altura

A altura preta de uma árvore é o número de nós pretos em qualquer caminho da raiz até um None (nesta aula, contando a raiz). A propriedade 5 diz que esse número é o mesmo em todos os caminhos.

Pela propriedade 4, entre dois pretos há no máximo um vermelho. Então o caminho mais longo (alternando preto e vermelho) tem no máximo o dobro do caminho mais curto (só pretos).

Daí sai a garantia: altura ≤ 2 · log₂(n + 1). Um pouco mais alta que a AVL (1,44 · log₂ n), mas ainda O(log n).

Inserção: os três casos

Insira como na ABB e pinte o novo nó de vermelho: assim nenhuma altura preta muda. O único problema possível é o pai também ser vermelho (propriedade 4). Olhamos então o tio (irmão do pai):

Caso	Situação	O que fazer
1	tio vermelho	pai e tio ficam pretos, avô fica vermelho; repita a verificação a partir do avô
2	tio preto e nó em “triângulo” (é filho direito de um filho esquerdo, ou o espelho)	rotação no pai: vira o caso 3
3	tio preto e nó em “linha”	pai fica preto, avô fica vermelho, rotação no avô: fim

No fim, a raiz é pintada de preto. São no máximo 2 rotações por inserção; recolorações podem subir até a raiz, mas cada uma é O(1).

Compare com a AVL: o caso 1 só troca cores (barato) e “empurra” o problema para cima. Os casos 2 e 3 correspondem às rotações duplas e simples da AVL.

novo nó → vermelhotio vermelho → recolorirtio preto → rotacionarraiz → sempre preta

Inserção rubro-negra em Python

Aqui cada nó guarda também um ponteiro para o pai, porque a correção sobe pela árvore com um laço em vez de usar a volta da recursão.

A rotação precisa atualizar três ligações: o filho que muda de dono, o nó que sobe e o pai (ou a raiz da árvore).

O ramo else do laço é o espelho do primeiro: troque esq ↔ dir.

Execute com as chaves em ordem de 1 a 10 e compare a altura com a da AVL do slide de inserção.

VERMELHO, PRETO = "R", "B"

class NoRB:
    def __init__(self, chave):
        self.chave = chave
        self.cor = VERMELHO
        self.esq = self.dir = self.pai = None

class ArvoreRB:
    def __init__(self):
        self.raiz = None

def rot_esquerda(self, x):
        y = x.dir
        x.dir = y.esq
        if y.esq: y.esq.pai = x
        y.pai = x.pai
        if x.pai is None: self.raiz = y
        elif x is x.pai.esq: x.pai.esq = y
        else: x.pai.dir = y
        y.esq = x
        x.pai = y

def rot_direita(self, x):
        y = x.esq
        x.esq = y.dir
        if y.dir: y.dir.pai = x
        y.pai = x.pai
        if x.pai is None: self.raiz = y
        elif x is x.pai.dir: x.pai.dir = y
        else: x.pai.esq = y
        y.dir = x
        x.pai = y

def inserir(self, chave):
        pai, atual = None, self.raiz
        while atual:                                  # desce como na ABB
            pai = atual
            if chave == atual.chave: return
            atual = atual.esq if chave < atual.chave else atual.dir
        z = NoRB(chave)
        z.pai = pai
        if pai is None: self.raiz = z
        elif chave < pai.chave: pai.esq = z
        else: pai.dir = z
        self.corrigir(z)

def corrigir(self, z):
        while z.pai and z.pai.cor == VERMELHO:
            p, a = z.pai, z.pai.pai
            if p is a.esq:
                tio = a.dir
                if tio and tio.cor == VERMELHO:       # caso 1
                    p.cor = tio.cor = PRETO
                    a.cor = VERMELHO
                    z = a
                else:
                    if z is p.dir:                    # caso 2
                        z = p
                        self.rot_esquerda(z)
                        p = z.pai
                    p.cor, a.cor = PRETO, VERMELHO    # caso 3
                    self.rot_direita(a)
            else:
                tio = a.esq
                if tio and tio.cor == VERMELHO:
                    p.cor = tio.cor = PRETO
                    a.cor = VERMELHO
                    z = a
                else:
                    if z is p.esq:
                        z = p
                        self.rot_direita(z)
                        p = z.pai
                    p.cor, a.cor = PRETO, VERMELHO
                    self.rot_esquerda(a)
        self.raiz.cor = PRETO

def pre_ordem(no):
    return [] if no is None else [f"{no.chave}{no.cor}"] + pre_ordem(no.esq) + pre_ordem(no.dir)

def altura(no):
    return 0 if no is None else 1 + max(altura(no.esq), altura(no.dir))

t = ArvoreRB()
for x in range(1, 11):
    t.inserir(x)
print(pre_ordem(t.raiz))
print("altura:", altura(t.raiz))

Rubro-negra passo a passo

Os valores digitados entram na árvore atual, um de cada vez. A cada passo, a explicação mostra qual caso foi aplicado.

Insira 15 e veja o caso 1 (tio vermelho). Depois limpe e tente 30 10 20 (caso 2 seguido do caso 3). Por fim, compare Crescente 1–10 aqui e na AVL: quem fez mais rotações?

AVL × rubro-negra

	AVL	Rubro-negra
altura máxima	≈ 1,44 log₂ n	2 log₂(n + 1)
busca	um pouco mais rápida	um pouco mais lenta
rotações na inserção	até 2	até 2
rotações na remoção	até O(log n)	até 3
informação extra por nó	altura (ou fb)	1 bit de cor

AVL é mais rigidamente equilibrada: boa quando há muitas buscas e poucas alterações (índices em memória, dicionários de consulta).

Rubro-negra aceita um desequilíbrio maior em troca de menos reestruturações: boa quando há muitas inserções e remoções. Por isso é a escolha de bibliotecas de uso geral: TreeMap do Java, std::map e std::set do C++ e o escalonador de processos (CFS) do Linux.

Conceitos e saídas

Responda primeiro no papel. Nas questões com código, considere as funções vistas nesta aula.

Desafio: AVL a partir de um vetor ordenado

Inserir n chaves uma a uma custa O(n log n). Se as chaves já estão ordenadas, dá para montar uma árvore balanceada em O(n), sem nenhuma rotação.

Escreva construir(v, ini, fim), recursiva: o elemento do meio vira a raiz; a metade esquerda vira a subárvore esquerda e a direita, a subárvore direita. Lembre de calcular a altura de cada nó.

Com v = 1..15 você deve obter altura 4, pré-ordem começando por 8 4 2 1 e eh_avl verdadeiro.

Mostrar uma solução

Prática 1: alturas e fatores

Nos dois exercícios, as chaves (inteiros na mesma linha) são inseridas, nessa ordem, em uma ABB comum, sem balanceamento; repetidas são ignoradas. Altura de None = 0, folha = 1 e fb = altura(esq) − altura(dir).

1. Altura e fatores básico

Mostre Altura: H e depois, em ordem crescente de chave, uma linha chave: fb=F para cada nó (F sem sinal de +, como o Python imprime).

Entrada	Saída esperada
20 10 30 25	Altura: 3 10: fb=0 20: fb=-1 25: fb=0 30: fb=1

Mostrar uma solução

2. É AVL? básico

Mostre AVL: sim se todos os nós da ABB têm fb entre −1 e +1, ou AVL: não caso contrário. Desafio extra: faça em O(n), com uma função que devolve a altura, ou −1 se a subárvore não for AVL.

Entrada	Saída esperada
20 10 30 25	AVL: sim
1 2 3	AVL: não

Mostrar uma solução

Prática 2: inserção na AVL

Agora as chaves são inseridas em uma AVL, nessa ordem; repetidas são ignoradas. O código inicial já traz o nó, as alturas e as duas rotações simples.

3. Inserir e mostrar a pré-ordem médio

Complete balancear e inserir. Mostre Pré-ordem: … (chaves separadas por um espaço) e Altura: H.

Entrada	Saída esperada
10 20 30	Pré-ordem: 20 10 30 Altura: 2

Mostrar uma solução

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None
        self.altura = 1

def altura(no):
    return no.altura if no else 0

def fb(no):
    return altura(no.esq) - altura(no.dir)

def atualiza(no):
    no.altura = 1 + max(altura(no.esq), altura(no.dir))

def rot_direita(z):
    y = z.esq
    z.esq = y.dir
    y.dir = z
    atualiza(z); atualiza(y)
    return y

def rot_esquerda(z):
    y = z.dir
    z.dir = y.esq
    y.esq = z
    atualiza(z); atualiza(y)
    return y

def balancear(no):
    atualiza(no)
    if fb(no) > 1:
        if fb(no.esq) < 0:
            no.esq = rot_esquerda(no.esq)
        return rot_direita(no)
    if fb(no) < -1:
        if fb(no.dir) > 0:
            no.dir = rot_direita(no.dir)
        return rot_esquerda(no)
    return no

def inserir(no, chave):
    if no is None:
        return No(chave)
    if chave < no.chave:
        no.esq = inserir(no.esq, chave)
    elif chave > no.chave:
        no.dir = inserir(no.dir, chave)
    else:
        return no
    return balancear(no)

def pre_ordem(no, saida):
    if no:
        saida.append(str(no.chave))
        pre_ordem(no.esq, saida)
        pre_ordem(no.dir, saida)
    return saida

raiz = None
for x in input("Chaves: ").split():
    raiz = inserir(raiz, int(x))
print("Pré-ordem:", " ".join(pre_ordem(raiz, [])))
print("Altura:", altura(raiz))

4. Contando rotações médio

Insira as chaves em uma AVL e conte quantas vezes cada tipo de correção foi aplicado: caso LL ou RR conta como rotação simples; caso LR ou RL conta como uma rotação dupla. Mostre Rotações simples: S e Rotações duplas: D.

Entrada	Saída esperada
3 1 2	Rotações simples: 0 Rotações duplas: 1

Mostrar uma solução

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None
        self.altura = 1

def altura(no):
    return no.altura if no else 0

def fb(no):
    return altura(no.esq) - altura(no.dir)

def atualiza(no):
    no.altura = 1 + max(altura(no.esq), altura(no.dir))

def rot_direita(z):
    y = z.esq
    z.esq = y.dir
    y.dir = z
    atualiza(z); atualiza(y)
    return y

def rot_esquerda(z):
    y = z.dir
    z.dir = y.esq
    y.esq = z
    atualiza(z); atualiza(y)
    return y

simples = 0
duplas = 0

def balancear(no):
    global simples, duplas
    atualiza(no)
    if fb(no) > 1:
        if fb(no.esq) < 0:
            no.esq = rot_esquerda(no.esq)
            duplas += 1
        else:
            simples += 1
        return rot_direita(no)
    if fb(no) < -1:
        if fb(no.dir) > 0:
            no.dir = rot_direita(no.dir)
            duplas += 1
        else:
            simples += 1
        return rot_esquerda(no)
    return no

def inserir(no, chave):
    if no is None:
        return No(chave)
    if chave < no.chave:
        no.esq = inserir(no.esq, chave)
    elif chave > no.chave:
        no.dir = inserir(no.dir, chave)
    else:
        return no
    return balancear(no)

raiz = None
for x in input("Chaves: ").split():
    raiz = inserir(raiz, int(x))
print("Rotações simples:", simples)
print("Rotações duplas:", duplas)

Prática 3: rubro-negra

Altura preta: número de nós pretos em um caminho da raiz até um None, contando a raiz. Cores: R (vermelho) e B (preto).

5. Verificando as propriedades médio

Cada item da entrada é uma chave seguida da cor (10B 5R 20R). Insira os nós, nessa ordem, em uma ABB comum, com as cores dadas. Confira, nesta ordem: raiz preta, nenhum vermelho com filho vermelho, mesma altura preta em todos os caminhos. Mostre Rubro-negra: sim e Altura preta: K, ou Rubro-negra: não (MOTIVO) com o primeiro problema encontrado: raiz vermelha, vermelho com filho vermelho ou altura preta diferente.

Entrada	Saída esperada
10B 5R 20R	Rubro-negra: sim Altura preta: 1
10B 5B 20R	Rubro-negra: não (altura preta diferente)

Mostrar uma solução

class No:
    def __init__(self, chave, cor):
        self.chave = chave
        self.cor = cor
        self.esq = None
        self.dir = None

def inserir(no, chave, cor):
    if no is None:
        return No(chave, cor)
    if chave < no.chave:
        no.esq = inserir(no.esq, chave, cor)
    else:
        no.dir = inserir(no.dir, chave, cor)
    return no

def vermelho(no):
    return no is not None and no.cor == "R"

def vermelho_duplo(no):
    if no is None:
        return False
    if vermelho(no) and (vermelho(no.esq) or vermelho(no.dir)):
        return True
    return vermelho_duplo(no.esq) or vermelho_duplo(no.dir)

def altura_preta(no):              # -1 se os caminhos discordam
    if no is None:
        return 0
    e = altura_preta(no.esq)
    d = altura_preta(no.dir)
    if e == -1 or d == -1 or e != d:
        return -1
    return e + (1 if no.cor == "B" else 0)

raiz = None
for item in input("Nós: ").split():
    raiz = inserir(raiz, int(item[:-1]), item[-1])

if vermelho(raiz):
    print("Rubro-negra: não (raiz vermelha)")
elif vermelho_duplo(raiz):
    print("Rubro-negra: não (vermelho com filho vermelho)")
elif altura_preta(raiz) == -1:
    print("Rubro-negra: não (altura preta diferente)")
else:
    print("Rubro-negra: sim")
    print("Altura preta:", altura_preta(raiz))

6. Inserção rubro-negra desafio

Insira as chaves, nessa ordem, em uma árvore rubro-negra (repetidas são ignoradas). Mostre a pré-ordem com a cor colada à chave (Pré-ordem: 20B 10R 30R) e Altura preta: K. Use o algoritmo da aula (casos 1, 2 e 3).

Entrada	Saída esperada
10 20 30	Pré-ordem: 20B 10R 30R Altura preta: 1

Mostrar uma solução

VERMELHO, PRETO = "R", "B"

class NoRB:
    def __init__(self, chave):
        self.chave = chave
        self.cor = VERMELHO
        self.esq = self.dir = self.pai = None

raiz = None

def rotacionar(x, lado):
    """lado = "esq": rotação à esquerda em x; "dir": à direita."""
    global raiz
    outro = "dir" if lado == "esq" else "esq"
    y = getattr(x, outro)
    setattr(x, outro, getattr(y, lado))
    if getattr(y, lado):
        getattr(y, lado).pai = x
    y.pai = x.pai
    if x.pai is None:
        raiz = y
    elif x is x.pai.esq:
        x.pai.esq = y
    else:
        x.pai.dir = y
    setattr(y, lado, x)
    x.pai = y

def inserir(chave):
    global raiz
    pai, atual = None, raiz
    while atual:
        if chave == atual.chave:
            return
        pai = atual
        atual = atual.esq if chave < atual.chave else atual.dir
    z = NoRB(chave)
    z.pai = pai
    if pai is None:
        raiz = z
    elif chave < pai.chave:
        pai.esq = z
    else:
        pai.dir = z
    while z.pai and z.pai.cor == VERMELHO:
        p, a = z.pai, z.pai.pai
        lado_p = "esq" if p is a.esq else "dir"
        outro = "dir" if lado_p == "esq" else "esq"
        tio = getattr(a, outro)
        if tio and tio.cor == VERMELHO:              # caso 1
            p.cor = tio.cor = PRETO
            a.cor = VERMELHO
            z = a
        else:
            if z is getattr(p, outro):               # caso 2: triângulo
                z = p
                rotacionar(z, lado_p)
                p = z.pai
            p.cor, a.cor = PRETO, VERMELHO           # caso 3: linha
            rotacionar(a, outro)
    raiz.cor = PRETO

def pre_ordem(no, saida):
    if no:
        saida.append(f"{no.chave}{no.cor}")
        pre_ordem(no.esq, saida)
        pre_ordem(no.dir, saida)
    return saida

for x in input("Chaves: ").split():
    inserir(int(x))
print("Pré-ordem:", " ".join(pre_ordem(raiz, [])))
k, no = 0, raiz
while no:                    # qualquer caminho serve: todos têm a mesma altura preta
    if no.cor == PRETO:
        k += 1
    no = no.esq
print("Altura preta:", k)

Laboratório livre

Espaço para testar ideias durante a aula. Sugestões: insira 1.000 chaves em ordem em uma AVL e compare a altura com 1,44 · log₂ 1000; conte as rotações da AVL e da rubro-negra para as mesmas chaves; aplique uma rotação simples no caso LR e veja por que ela não resolve.