--- title: "Árvore Rubro-Negra (Red-Black Tree)" url: "https://rustlang.com.br/estruturas-dados/arvore-rubro-negra/" markdown_url: "https://rustlang.com.br/estruturas-dados/arvore-rubro-negra.MD" description: "Entenda as 5 propriedades da árvore rubro-negra, as regras de coloração e rebalanceamento, e sua relação com BTreeMap da biblioteca padrão de Rust." date: "" author: "Equipe Rust Brasil" --- # Árvore Rubro-Negra (Red-Black Tree) Entenda as 5 propriedades da árvore rubro-negra, as regras de coloração e rebalanceamento, e sua relação com BTreeMap da biblioteca padrão de Rust. ## Introdução A **árvore rubro-negra** (Red-Black Tree) é uma árvore de busca binária autobalanceada que utiliza um esquema de coloração — cada nó é marcado como **vermelho** ou **negro** — para manter o balanceamento. Inventada por Rudolf Bayer em 1972 e refinada por Leonidas Guibas e Robert Sedgewick em 1978, ela é uma das estruturas de dados mais utilizadas na prática. A grande vantagem da árvore rubro-negra sobre a AVL é que ela requer **menos rotações** durante inserções e remoções, tornando-a mais eficiente em cenários com muitas modificações. Por essa razão, ela é a estrutura escolhida para a maioria das implementações de mapas e conjuntos ordenados em linguagens de programação, incluindo a implementação interna do `BTreeMap` em Rust (que usa uma variante B-Tree, mas o conceito rubro-negro é fundamental na ciência da computação). --- ## Conceito e Teoria ### As 5 Propriedades Fundamentais Uma árvore rubro-negra é uma BST que satisfaz **todas** as seguintes propriedades: 1. **Todo nó é vermelho ou negro.** 2. **A raiz é sempre negra.** 3. **Toda folha (NIL/nula) é considerada negra.** 4. **Se um nó é vermelho, ambos os seus filhos devem ser negros** (não pode haver dois vermelhos consecutivos). 5. **Para cada nó, todos os caminhos dele até qualquer folha descendente contêm o mesmo número de nós negros** (black-height). ```text Árvore Rubro-Negra válida: [13:N] N = Negro / \ V = Vermelho [8:V] [17:V] / \ \ [1:N] [11:N] [25:N] \ / [6:V] [22:V] Verificação da propriedade 5 (black-height = 2 para raiz): 13 → 8 → 1 → NIL : negros = {13, 1} = 2 ✓ 13 → 8 → 1 → 6 → NIL: negros = {13, 1} = 2 ✓ 13 → 8 → 11 → NIL : negros = {13, 11} = 2 ✓ 13 → 17 → 25 → NIL : negros = {13, 25} = 2 ✓ 13 → 17 → 25 → 22 : negros = {13, 25} = 2 ✓ ``` ### Por que essas propriedades funcionam? A combinação das propriedades 4 e 5 garante que o caminho mais longo da raiz até uma folha é no máximo **2 vezes** o caminho mais curto. Isso porque: - O caminho mais curto pode ter apenas nós negros. - O caminho mais longo alterna entre negros e vermelhos. - Como a propriedade 5 garante o mesmo número de negros, o caminho mais longo tem no máximo o dobro de nós. Portanto, a altura é no máximo **2 * log2(n+1)**, garantindo O(log n) para todas as operações. ### Casos de Inserção Ao inserir um nó (sempre colorido de **vermelho** inicialmente), podem surgir violações que são corrigidas por **recoloração** ou **rotações**: ```text Caso 1 — Tio é vermelho (recoloração): [G:N] [G:V] / \ / \ [P:V] [T:V] → [P:N] [T:N] / / [X:V] [X:V] Recolore P e T para negro, G para vermelho. Continue verificando a partir de G. Caso 2 — Tio é negro, X é filho interno (rotação + caso 3): [G:N] [G:N] / \ / \ [P:V] [T:N] → [X:V] [T:N] \ / [X:V] [P:V] Rotação à esquerda em P. Agora trata como Caso 3. Caso 3 — Tio é negro, X é filho externo (rotação + recoloração): [G:N] [P:N] / \ / \ [P:V] [T:N] → [X:V] [G:V] / \ [X:V] [T:N] Rotação à direita em G. Troca cores de P e G. ``` --- ## Complexidade | Operação | Melhor Caso | Caso Médio | Pior Caso | |------------------|-------------|------------|-----------| | Busca | O(1) | O(log n) | O(log n) | | Inserção | O(log n) | O(log n) | O(log n) | | Remoção | O(log n) | O(log n) | O(log n) | | Rotações/inserção| O(1) | O(1) | 2 | | Rotações/remoção | O(1) | O(1) | 3 | | Espaço | — | O(n) | O(n) | > **Destaque:** A inserção requer no máximo 2 rotações e a remoção no máximo 3 rotações, independente do tamanho da árvore. Isso é significativamente melhor que a AVL, que pode fazer até O(log n) rotações na remoção. --- ## Implementação em Rust ```rust use std::cmp::Ordering; use std::fmt::Display; /// Cores dos nós: vermelho ou negro #[derive(Debug, Clone, Copy, PartialEq)] enum Cor { Vermelho, Negro, } /// Nó da árvore rubro-negra #[derive(Debug, Clone)] struct No { valor: T, cor: Cor, esquerda: ArvoreRN, direita: ArvoreRN, } /// Tipo da árvore rubro-negra type ArvoreRN = Option>>; /// Verifica se um nó é vermelho fn eh_vermelho(no: &ArvoreRN) -> bool { match no { Some(n) => n.cor == Cor::Vermelho, None => false, // NIL é negro (propriedade 3) } } /// Rotação à esquerda (link vermelho à direita vai para esquerda) fn rotacao_esquerda(mut no: Box>) -> Box> { let mut novo_raiz = no.direita.take().expect("Filho direito necessário"); no.direita = novo_raiz.esquerda.take(); novo_raiz.cor = no.cor; no.cor = Cor::Vermelho; novo_raiz.esquerda = Some(no); novo_raiz } /// Rotação à direita (link vermelho à esquerda sobe) fn rotacao_direita(mut no: Box>) -> Box> { let mut novo_raiz = no.esquerda.take().expect("Filho esquerdo necessário"); no.esquerda = novo_raiz.direita.take(); novo_raiz.cor = no.cor; no.cor = Cor::Vermelho; novo_raiz.direita = Some(no); novo_raiz } /// Inverte as cores do nó e seus dois filhos fn inverter_cores(no: &mut Box>) { no.cor = if no.cor == Cor::Vermelho { Cor::Negro } else { Cor::Vermelho }; if let Some(ref mut esq) = no.esquerda { esq.cor = if esq.cor == Cor::Vermelho { Cor::Negro } else { Cor::Vermelho }; } if let Some(ref mut dir) = no.direita { dir.cor = if dir.cor == Cor::Vermelho { Cor::Negro } else { Cor::Vermelho }; } } /// Corrige violações rubro-negras (implementação Left-Leaning Red-Black Tree) fn corrigir(mut no: Box>) -> Box> { // Se o filho direito é vermelho e o esquerdo não, rotaciona à esquerda if eh_vermelho(&no.direita) && !eh_vermelho(&no.esquerda) { no = rotacao_esquerda(no); } // Se o filho esquerdo e o neto esquerdo são vermelhos, rotaciona à direita if eh_vermelho(&no.esquerda) && no .esquerda .as_ref() .map_or(false, |e| eh_vermelho(&e.esquerda)) { no = rotacao_direita(no); } // Se ambos os filhos são vermelhos, inverte as cores if eh_vermelho(&no.esquerda) && eh_vermelho(&no.direita) { inverter_cores(&mut no); } no } /// Árvore Rubro-Negra (Left-Leaning Red-Black Tree) #[derive(Debug)] struct ArvoreRubroNegra { raiz: ArvoreRN, tamanho: usize, } impl ArvoreRubroNegra { /// Cria uma árvore rubro-negra vazia fn nova() -> Self { ArvoreRubroNegra { raiz: None, tamanho: 0, } } /// Retorna o número de elementos fn tamanho(&self) -> usize { self.tamanho } /// Insere um valor na árvore fn inserir(&mut self, valor: T) { self.raiz = Self::inserir_rec(self.raiz.take(), valor); // Propriedade 2: a raiz é sempre negra if let Some(ref mut raiz) = self.raiz { raiz.cor = Cor::Negro; } self.tamanho += 1; } fn inserir_rec(no: ArvoreRN, valor: T) -> ArvoreRN { match no { None => Some(Box::new(No { valor, cor: Cor::Vermelho, // Novo nó é sempre vermelho esquerda: None, direita: None, })), Some(mut atual) => { match valor.cmp(&atual.valor) { Ordering::Less => { atual.esquerda = Self::inserir_rec(atual.esquerda.take(), valor); } Ordering::Greater => { atual.direita = Self::inserir_rec(atual.direita.take(), valor); } Ordering::Equal => { return Some(atual); // Duplicado ignorado } } Some(corrigir(atual)) } } } /// Busca um valor na árvore fn buscar(&self, valor: &T) -> bool { let mut atual = &self.raiz; while let Some(no) = atual { match valor.cmp(&no.valor) { Ordering::Less => atual = &no.esquerda, Ordering::Greater => atual = &no.direita, Ordering::Equal => return true, } } false } /// Travessia em ordem (valores ordenados) fn em_ordem(&self) -> Vec { let mut resultado = Vec::new(); Self::em_ordem_rec(&self.raiz, &mut resultado); resultado } fn em_ordem_rec(no: &ArvoreRN, resultado: &mut Vec) { if let Some(atual) = no { Self::em_ordem_rec(&atual.esquerda, resultado); resultado.push(atual.valor.clone()); Self::em_ordem_rec(&atual.direita, resultado); } } /// Calcula a black-height (número de nós negros até uma folha) fn black_height(&self) -> usize { let mut contagem = 0; let mut atual = &self.raiz; while let Some(no) = atual { if no.cor == Cor::Negro { contagem += 1; } atual = &no.esquerda; } contagem } /// Verifica se a árvore satisfaz todas as propriedades rubro-negras fn verificar_propriedades(&self) -> bool { // Propriedade 2: raiz é negra if eh_vermelho(&self.raiz) { println!("Violação: raiz é vermelha"); return false; } // Verifica propriedades 4 e 5 recursivamente Self::verificar_rec(&self.raiz).is_some() } /// Retorna Some(black_height) se válida, None se inválida fn verificar_rec(no: &ArvoreRN) -> Option { match no { None => Some(1), // NIL é negro Some(atual) => { // Propriedade 4: vermelhos não podem ter filhos vermelhos if atual.cor == Cor::Vermelho { if eh_vermelho(&atual.esquerda) || eh_vermelho(&atual.direita) { println!("Violação: nó vermelho {} tem filho vermelho", atual.valor); return None; } } let bh_esq = Self::verificar_rec(&atual.esquerda)?; let bh_dir = Self::verificar_rec(&atual.direita)?; // Propriedade 5: black-height igual em ambos os lados if bh_esq != bh_dir { println!( "Violação: black-height diferente no nó {} (esq={}, dir={})", atual.valor, bh_esq, bh_dir ); return None; } let incremento = if atual.cor == Cor::Negro { 1 } else { 0 }; Some(bh_esq + incremento) } } } } fn main() { let mut arvore = ArvoreRubroNegra::nova(); // Inserção de valores em ordem crescente let valores = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100]; println!("Inserindo em ordem crescente: {:?}", valores); for v in &valores { arvore.inserir(*v); } println!("Tamanho: {}", arvore.tamanho()); println!("Black-height: {}", arvore.black_height()); println!("Propriedades válidas: {}", arvore.verificar_propriedades()); println!("Em ordem: {:?}", arvore.em_ordem()); // Busca println!("\nBuscar 50: {}", arvore.buscar(&50)); println!("Buscar 55: {}", arvore.buscar(&55)); } ``` --- ## Métodos Principais | Método | Descrição | |---------------------------|-------------------------------------------------------------| | `nova()` | Cria uma árvore rubro-negra vazia | | `inserir(valor)` | Insere com recoloração e rotações automáticas | | `buscar(valor)` | Busca iterativa O(log n) | | `em_ordem()` | Retorna vetor com elementos em ordem crescente | | `black_height()` | Calcula a black-height (nós negros até folha) | | `verificar_propriedades()`| Verifica se todas as 5 propriedades são satisfeitas | | `rotacao_esquerda(no)` | Move link vermelho da direita para esquerda | | `rotacao_direita(no)` | Move link vermelho da esquerda para cima | | `inverter_cores(no)` | Inverte cores do nó e seus dois filhos | | `corrigir(no)` | Aplica as correções necessárias após inserção | --- ## Exemplo Prático: Agendamento de Intervalos A árvore rubro-negra é excelente para manter intervalos de tempo ordenados, permitindo encontrar conflitos rapidamente. ```rust use std::fmt; /// Representa um intervalo de tempo (ex: reunião) #[derive(Debug, Clone)] struct Intervalo { inicio: u32, // Hora de início (em minutos desde meia-noite) fim: u32, // Hora de término descricao: String, } impl Intervalo { fn novo(inicio: u32, fim: u32, descricao: &str) -> Self { Intervalo { inicio, fim, descricao: descricao.to_string(), } } /// Verifica se dois intervalos se sobrepõem fn sobrepoe(&self, outro: &Intervalo) -> bool { self.inicio < outro.fim && outro.inicio < self.fim } /// Formata hora em formato HH:MM fn formato_hora(minutos: u32) -> String { format!("{:02}:{:02}", minutos / 60, minutos % 60) } } impl fmt::Display for Intervalo { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!( f, "{}-{} {}", Self::formato_hora(self.inicio), Self::formato_hora(self.fim), self.descricao ) } } impl PartialEq for Intervalo { fn eq(&self, other: &Self) -> bool { self.inicio == other.inicio } } impl Eq for Intervalo {} impl PartialOrd for Intervalo { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } impl Ord for Intervalo { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.inicio.cmp(&other.inicio) } } fn main() { let mut agenda = ArvoreRubroNegra::nova(); // Inserir compromissos agenda.inserir(Intervalo::novo(540, 600, "Reunião diária")); agenda.inserir(Intervalo::novo(600, 720, "Desenvolvimento")); agenda.inserir(Intervalo::novo(720, 780, "Almoço")); agenda.inserir(Intervalo::novo(840, 900, "Code review")); agenda.inserir(Intervalo::novo(960, 1020, "Retrospectiva")); println!("=== Agenda do Dia (ordenada) ==="); for intervalo in agenda.em_ordem() { println!(" {}", intervalo); } // Verificar conflito com novo compromisso let novo = Intervalo::novo(570, 630, "Entrevista"); println!("\nTentar agendar: {}", novo); let conflitos: Vec<_> = agenda .em_ordem() .iter() .filter(|i| i.sobrepoe(&novo)) .cloned() .collect(); if conflitos.is_empty() { println!("Sem conflitos! Pode agendar."); } else { println!("Conflitos encontrados:"); for c in &conflitos { println!(" - {}", c); } } } ``` --- ## Comparação com Outras Estruturas | Critério | Rubro-Negra | AVL | BST | B-Tree | |--------------------------|----------------|---------------|--------------|--------------| | Busca (pior caso) | O(log n) | O(log n) | O(n) | O(log n) | | Rotações por inserção | Até 2 | Até 2 | 0 | 0* | | Rotações por remoção | Até 3 | Até O(log n) | 0 | 0* | | Altura máxima | 2 log(n+1) | 1.44 log n | n-1 | log_t(n) | | Busca mais rápida? | Não | Sim | — | Depende | | Modificação mais rápida? | Sim | Não | — | Sim (disco) | | Uso em stdlib Rust | — | — | — | BTreeMap | *\* B-Trees usam splits/merges ao invés de rotações.* ### Quando usar Árvore Rubro-Negra? - **Use** quando inserções e remoções são tão frequentes quanto buscas. - **Use** quando precisa de uma árvore balanceada com rebalanceamento rápido. - **Na prática em Rust**, use `BTreeMap`/`BTreeSet` para dados ordenados — são a escolha padrão da biblioteca padrão. - **Não use** se buscas predominam fortemente — AVL é levemente mais rápida em buscas. --- ## Exercícios ### Exercício 1: Implementar Remoção Implemente o método `remover(valor)` para a árvore rubro-negra. A remoção é significativamente mais complexa que a inserção e requer tratar vários subcasos. Dica: use a abordagem de "mover vermelho para baixo" durante a busca pelo nó a ser removido. ### Exercício 2: Contagem de Nós por Cor Adicione métodos `contar_vermelhos()` e `contar_negros()` que retornem o número de nós vermelhos e negros na árvore, respectivamente. Verifique empiricamente que a proporção de nós vermelhos diminui conforme a árvore cresce. ### Exercício 3: Comparação Empírica AVL vs Rubro-Negra Implemente ambas as árvores e compare o número total de rotações ao inserir 10.000 elementos aleatórios seguidos de 5.000 remoções aleatórias. Meça também o tempo de execução usando `std::time::Instant`. Qual árvore é mais rápida para cada operação? --- ## Conclusão A árvore rubro-negra é uma das estruturas de dados mais importantes da computação moderna. Sua abordagem de coloração permite manter o balanceamento com um número limitado de rotações por operação, tornando-a ideal para cenários com muitas modificações. Em Rust, a implementação Left-Leaning Red-Black Tree (LLRB) simplifica significativamente o código em comparação com a implementação clássica, mantendo as mesmas garantias de complexidade. Embora a biblioteca padrão de Rust use B-Trees para `BTreeMap` e `BTreeSet`, compreender árvores rubro-negras é fundamental para qualquer programador, pois elas aparecem em praticamente todas as linguagens de programação e sistemas operacionais. A compreensão profunda dessa estrutura prepara o terreno para entender B-Trees, que veremos a seguir.