Árvores Auto-Balanceadas & Invariantes
Módulo 04
Árvore AVL (Adelson-Velsky & Landis)
Uma implementação rigorosa da primeira árvore de busca binária auto-balanceada inventada na ciência da computação (1962). A AVL assegura que a diferença de altura entre as subárvores esquerda e direita de qualquer nó nunca exceda 1, eliminando o risco de degeneração em listas lineares.
01. A Armadilha das BSTs Ingênuas: Degeneração para O(N)
Em uma árvore binária de busca comum, se você inserir elementos em ordem crescente (ex: [10, 20, 30, 40, 50]), cada novo nó se tornará o filho direito do anterior. A árvore se degenera em uma lista ligada de profundidade $N$, destruindo o benefício da busca binária e degradando o tempo de consulta de $O(\log N)$ para $O(N)$.
A Invariante AVL:
Para todo nó $v$: $\text{BalanceFactor}(v) = \text{height}(v.\text{left}) - \text{height}(v.\text{right}) \in \{-1, 0, 1\}$.
Se qualquer inserção provocar $|\text{BF}| > 1$, rotações de ponteiros são acionadas na subida da pilha de recursão para restaurar a invariante em $O(1)$ tempo local.
02. As 4 Rotações Fundamentais
A reestruturação da árvore é dividida em dois casos simples e dois casos duplos:
1. Rotação Direita (LL)
Ocorre quando a subárvore esquerda do nó filho esquerdo está mais pesada. A raiz desce para a direita e o filho esquerdo se torna a nova raiz local.
2. Rotação Esquerda (RR)
Espelho da rotação direita. Ocorre quando a subárvore direita do filho direito está pesada. A raiz desce para a esquerda.
3. Rotação Dupla Esquerda-Direita (LR)
Ocorre em zigue-zague à esquerda. Aplica rotação esquerda no filho esquerdo, convertendo no caso LL, seguida por rotação direita na raiz local.
4. Rotação Dupla Direita-Esquerda (RL)
Zigue-zague à direita. Aplica rotação direita no filho direito (convertendo para RR), seguida por rotação esquerda na raiz local.
03. Engenharia em Rust: Rotações Sem Unsafe
Em C++, rotações manipulam ponteiros brutos soltos. Em Rust, como cada nó possui posse exclusiva (Box<Node<T>>) de seus filhos, não é possível fazer node.left.right = node diretamente sem violar o Borrow Checker.
O Idioma Option::take():
Utilizamos node.left.take(), que move o valor de dentro do Option para uma variável local enquanto deixa temporariamente um None no lugar. Isso transfere a propriedade do nó sem violar o modelo de posse única e sem nenhuma linha de código unsafe.
use std::cmp::{max, Ordering};
use std::fmt::Display;
#[derive(Debug, Clone)]
pub struct Node<T> {
pub key: T,
pub height: i32,
pub left: Option<Box<Node<T>>>,
pub right: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
fn new(key: T) -> Self {
Self {
key,
height: 1,
left: None,
right: None,
}
}
fn left_height(&self) -> i32 {
self.left.as_ref().map_or(0, |n| n.height)
}
fn right_height(&self) -> i32 {
self.right.as_ref().map_or(0, |n| n.height)
}
fn update_height(&mut self) {
self.height = 1 + max(self.left_height(), self.right_height());
}
fn balance_factor(&self) -> i32 {
self.left_height() - self.right_height()
}
}
pub struct AvlTree<T> {
root: Option<Box<Node<T>>>,
len: usize,
}
impl<T: Ord + Display + Clone> AvlTree<T> {
pub fn new() -> Self {
Self {
root: None,
len: 0,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn height(&self) -> i32 {
self.root.as_ref().map_or(0, |n| n.height)
}
fn rotate_right(mut y: Box<Node<T>>) -> Box<Node<T>> {
let mut x = y.left.take().expect("Filho esquerdo ausente em rotação à direita");
y.left = x.right.take();
y.update_height();
x.right = Some(y);
x.update_height();
x
}
fn rotate_left(mut x: Box<Node<T>>) -> Box<Node<T>> {
let mut y = x.right.take().expect("Filho direito ausente em rotação à esquerda");
x.right = y.left.take();
x.update_height();
y.left = Some(x);
y.update_height();
y
}
fn balance(mut node: Box<Node<T>>) -> Box<Node<T>> {
node.update_height();
let bf = node.balance_factor();
if bf > 1 {
if let Some(left) = node.left.as_mut() {
if left.balance_factor() < 0 {
node.left = Some(Self::rotate_left(node.left.take().unwrap()));
}
}
return Self::rotate_right(node);
}
if bf < -1 {
if let Some(right) = node.right.as_mut() {
if right.balance_factor() > 0 {
node.right = Some(Self::rotate_right(node.right.take().unwrap()));
}
}
return Self::rotate_left(node);
}
node
}
pub fn insert(&mut self, key: T) {
let (new_root, inserted) = Self::insert_rec(self.root.take(), key);
self.root = Some(new_root);
if inserted {
self.len += 1;
}
}
fn insert_rec(node: Option<Box<Node<T>>>, key: T) -> (Box<Node<T>>, bool) {
let mut current = match node {
None => return (Box::new(Node::new(key)), true),
Some(n) => n,
};
let inserted;
match key.cmp(¤t.key) {
Ordering::Less => {
let (new_left, ins) = Self::insert_rec(current.left.take(), key);
current.left = Some(new_left);
inserted = ins;
}
Ordering::Greater => {
let (new_right, ins) = Self::insert_rec(current.right.take(), key);
current.right = Some(new_right);
inserted = ins;
}
Ordering::Equal => {
return (current, false);
}
}
(Self::balance(current), inserted)
}
pub fn contains(&self, key: &T) -> bool {
let mut curr = self.root.as_ref();
while let Some(node) = curr {
match key.cmp(&node.key) {
Ordering::Less => curr = node.left.as_ref(),
Ordering::Greater => curr = node.right.as_ref(),
Ordering::Equal => return true,
}
}
false
}
pub fn in_order(&self) -> Vec<T> {
let mut elements = Vec::new();
Self::in_order_rec(&self.root, &mut elements);
elements
}
fn in_order_rec(node: &Option<Box<Node<T>>>, out: &mut Vec<T>) {
if let Some(n) = node {
Self::in_order_rec(&n.left, out);
out.push(n.key.clone());
Self::in_order_rec(&n.right, out);
}
}
pub fn print_tree(&self) {
println!(" Status da Árvore: N = {} nós | Altura Máxima = {} níveis", self.len, self.height());
Self::print_ascii(&self.root, "", true, true);
}
fn print_ascii(node: &Option<Box<Node<T>>>, prefix: &str, is_tail: bool, is_root: bool) {
if let Some(n) = node {
let branch = if is_root {
"── "
} else if is_tail {
"└── "
} else {
"├── "
};
println!("{prefix}{branch}[{}] (BF: {:+})", n.key, n.balance_factor());
let mut children: Vec<(&Option<Box<Node<T>>>, &str)> = Vec::new();
if n.left.is_some() || n.right.is_some() {
children.push((&n.right, "R"));
children.push((&n.left, "L"));
}
let new_prefix = if is_root {
" ".to_string()
} else if is_tail {
format!("{prefix} ")
} else {
format!("{prefix}│ ")
};
for (i, (child, _side)) in children.iter().enumerate() {
let tail = i == children.len() - 1;
Self::print_ascii(child, &new_prefix, tail, false);
}
} else if !is_root {
let branch = if is_tail { "└── " } else { "├── " };
println!("{prefix}{branch}(vazio)");
}
}
}
fn main() {
println!("============================================================");
println!("🦀 RUST DATA STRUCTURES: SELF-BALANCING AVL TREE");
println!("============================================================");
let mut tree: AvlTree<i32> = AvlTree::new();
println!("\n1. Inserindo elementos ordenados [10, 20, 30, 40, 50, 25]:");
let sequence = [10, 20, 30, 40, 50, 25];
for val in sequence {
println!(" -> Inserindo {}...", val);
tree.insert(val);
}
println!("\n2. Visualização Estrutural da Árvore Balanceada (ASCII):");
tree.print_tree();
println!("\n3. Verificação do Percurso In-Order (Deve estar ordenado):");
let sorted = tree.in_order();
println!(" In-Order: {:?}", sorted);
println!("\n4. Consultas de Busca O(log N):");
println!(" contains(25) -> {}", tree.contains(&25));
println!(" contains(40) -> {}", tree.contains(&40));
println!(" contains(99) -> {}", tree.contains(&99));
println!("\n5. Auditoria de Invariantes:");
println!(" Altura balanceada: {} níveis para {} nós. Garantia de O(log N) cumprida!", tree.height(), tree.len());
}