Por que inserção, remoção e busca em uma árvore binária de busca balanceada têm complexidade média \(O(\log n)\)?

Resposta

Resposta: A altura cresce proporcionalmente a \( \log n\); assim cada operação percorre ou reequilibra caminhos de comprimento \(O(\log n)\).

Busca: segue comparações da raiz até um nó, custo ≈ altura \( \Rightarrow O(\log n)\).

Inserção: localiza posição como na busca e aplica reajustes (rotações) em número limitado, mantendo \(O(\log n)\).

Remoção: localiza o nó, substitui se necessário e faz reajustes locais limitados, preservando \(O(\log n)\).