Árvore binária de busca: quando O(log n) vira O(n)
Pergunta
Qual a ideia de uma árvore binária de busca (BST) e por que a complexidade das operações depende do balanceamento?
Resposta esperada
Numa BST, cada nó tem chave; tudo à esquerda é menor, tudo à direita é maior. Buscar/inserir/remover desce comparando, descartando metade da subárvore a cada passo — O(altura). Se a árvore está balanceada, altura ≈ log n, e as operações são O(log n). Mas inserir dados já ordenados numa BST simples produz uma 'lista encadeada torta' (cada nó só tem filho à direita): altura n, operações O(n) — o pior caso. Por isso, na prática, se usa BSTs auto-balanceadas (AVL, rubro-negra) que fazem rotações pra manter a altura logarítmica, ou estruturas alternativas (skip list, B-tree pra disco). A resposta boa reconhece que 'BST é O(log n)' só vale com a hipótese de balanceamento.
Por que perguntam isso
Pergunta pleno. O que separa: saber o pior caso (inserção ordenada → O(n)) e que árvores auto-balanceadas existem pra evitar isso.