Árvores são estruturas hierárquicas formadas por nós. Cada nó pode ter filhos, e o nó raiz é o ponto de entrada da árvore. Em uma árvore, um nó pai pode ter vários filhos; em uma árvore binária, cada nó possui no máximo dois filhos, chamados esquerda e direita.
Conceito básico: nós com referência para pai e filhos. Observando uma árvore de números, o nó raiz pode ter vários filhos, e cada filho pode possuir seus próprios filhos, formando uma estrutura recursiva.
Exemplo simples: uma árvore com raiz 8 e filhos 4, 2, 9 e 1. O nó 4 pode ter filhos 6 e 7, enquanto folhas são nós sem filhos (ex.: 2, 1, 9, 7, etc.).
Observação: árvores são úteis para representar hierarquias, diretórios, expressões e muito mais. Em situações reais, a organização hierárquica facilita operações como busca, inserção e remoção de elementos.
É uma árvore na qual cada nó pode ter, no máximo, dois filhos: esquerdo e direito. Um nó pode ter apenas um filho ou nenhum, desde que não haja mais de dois filhos. Esse modelo simplifica operações e permite travessias simples em profundidade.
BSTs são árvores binárias com a propriedade: todos os nós na subárvore esquerda de qualquer nó possuem chave menor que a chave do nó, e os da subárvore à direita possuem chave maior. Essa propriedade permite buscas eficientes: ao comparar a chave procurada com a do nó atual, decidimos se seguimos pela esquerda ou pela direita, reduzindo o conjunto de nós visitados.
Exemplo: para a raiz com chave 8, todas as chaves na esquerda devem ser menores que 8, e as da direita devem ser maiores que 8. Em uma BST bem organizada, podemos encontrar rapidamente elementos seguindo caminhos práticos pela árvore.
Um nó de BST (BSTNode) guarda: chave (key), valor (value) e referências aos filhos esquerdo e direito. Exemplo básico:
class BSTNode(object):
def __init__(self, key, value=None, left=None, right=None):
self.key = key
self.value = value
self.left = left
self.right = right
Inserção simples mantém a propriedade: se o valor a inserir for menor que a chave do nó atual, segue-se à esquerda; caso contrário, à direita. A inclusão de uma interface clara evita o encadeamento manual de nós.
Para tornar a BST útil, precisamos de operações básicas: busca por chave, inserção, remoção e travessia (varredura) para percorrer os nós.
A busca percorre a árvore comparando a chave procurada com a chave do nó atual. Se for menor, busca na subárvore esquerda; se for maior, busca na subárvore direita. O processo é recursivo até encontrar o nó ou alcançar um nó nulo (None).
Exemplo: procurar pela chave 4 em uma BST com raiz 8 pode exigir algumas comparações até chegar ao nó com a chave 4 ou confirmar que não existe.
Para inserir, seguimos o mesmo caminho da busca até encontrar um nó folha onde poderá ser criado o novo nó. Se o valor a inserir for menor que a chave do nó atual, inserimos à esquerda; caso contrário, à direita.
Observação: inserções contínuas sem balanceamento podem tornar a árvore desequilibrada, prejudicando operações futuras. Em BST balanceadas, usamos estruturas como AVL ou Rubro-Negra para manter a altura sob controle.
Balancear significa manter a altura das subárvores de um nó próximas entre si. Em BST não balanceadas (caso pior), inserir itens ordenados pode levar a uma árvore em forma de lista, degradando buscas para O(n).
Exemplos de árvores balanceadas: AVL e Rubro-Negra. Balancear envolve reestruturar encadeamentos para manter alturas equivalentes entre subárvores esquerda e direita.
Remover um nó envolve três situações: nó folha, nó com um filho, nó com dois filhos.
Exemplos: para remover nó folha, basta desconectar; para nó com um filho, ligar o pai ao filho; para nó com dois filhos, escolher um substituto (tipicamente o menor da subárvore à direita) e copiar seus valores, removendo o substituto de posição original.
Três estratégias centrais: pré-ordem (visita no nó antes das subárvores), travessia in-order (visita entre esquerda, nó, direita – produz chave em ordem crescente), e pós-ordem (visita após as subárvores).
É comum ter um método traverse(self, visit, order='pre') que aceita uma função visit para aplicar em cada nó, em diferentes ordens.
BSTs também podem ser representadas por um array, onde a raiz fica na posição 0, filho esquerdo em 2*i+1 e direito em 2*i+2. Embora simples, esse modelo pode desperdiçar espaço em árvores com muitos nós ausentes.
Para aprofundar, consulte artigos e visualizações online – Wikipedia, visualgo.net, livros de algoritmos. Explorar diferentes tipos de árvores pode facilitar a compreensão de problemas que envolvem hierarquias e ordenação.
Resposta correta: A) Os nós à esquerda de qualquer nó possuem chaves menores que a do nó atual.
Explicação: essa é a propriedade fundamental da BST. Em toda subárvore, a raiz da subárvore esquerda tem chave menor, e a raiz da subárvore direita tem chave maior.
Resposta correta: D) Substituir pelo menor nó da subárvore à direita.
Explicação: quando o nó a ser removido tem dois filhos, uma estratégia comum é pegar o nó substituto, que é o menor elemento da subárvore à direita, copiar seus valores para o nó a ser removido e remover o nó substituto da sua posição original (geralmente com remoção do mínimo).
Resposta correta: B) Em ordem crescente.
Explicação: a travessia in-order visita esquerda, nó atual, direita; para BST, isso resulta na impressão das chaves em ordem crescente.
Resposta correta: A) Garantir que a altura da árvore seja O(log n) nas operações de busca, inserção e remoção.
Explicação: balanceamento mantém a altura próxima a log2(n), o que garante operações eficientes. Estruturas como AVL e Rubro-Negra são exemplos de árvores balanceadas.