Árvores Binárias de Busca

3.1 Definição de Árvore Binária de Busca (BST)

Árvore Binária de Busca (BST) é uma árvore binária, que possui as seguintes propriedades:

• Para qualquer nó, sua subárvore esquerda contém apenas nós com chaves menores que a chave do nó atual.
• Para qualquer nó, sua subárvore direita contém apenas nós com chaves maiores que a chave do nó atual.
• Ambas as subárvores de cada nó também são árvores binárias de busca.

Exemplo de BST:

BST é a abreviação de Binary Search Tree – literalmente "Árvore Binária de Busca". Basicamente, é uma organização de dados em forma de "árvore", onde é possível buscar bem rápido. A estrutura da árvore é uma espécie de ordenação oculta/esperta dos elementos.

Travessia em ordem (in-order traversal)

A tarefa da travessia é formar uma lista dos nós de uma forma específica (ou dados de nós, questão de terminologia e o que importa na prática). A travessia em ordem (simétrica) percorre a árvore colocando a raiz entre os resultados das travessias das subárvores esquerda e direita.

Juntamente com a propriedade da árvore binária de busca (sobre desigualdades, veja a teoria) isso nos diz que a travessia em ordem de uma árvore binária de busca formará uma lista de nós ordenada — legal! É assim que a travessia da árvore definida anteriormente se parece:

3.2 Princípios de funcionamento e propriedades da BST

Princípios de funcionamento:

• Organização de dados: A BST organiza os dados para garantir a busca, inserção e remoção eficiente dos elementos.
• Estrutura recursiva: Cada nó na BST segue as mesmas regras que a raiz da árvore, o que torna a estrutura recursiva.
• Balanceamento: Para garantir a performance ótima, a BST deve estar balanceada, ou seja, a altura das subárvores esquerda e direita deve ser aproximadamente igual.

Propriedades da BST:

• Ordenação: A qualquer momento é possível percorrer a árvore em ordem "in-order" (subárvore esquerda → nó atual → subárvore direita) para obter todos os elementos em ordem ordenada.
• Tempo das operações:
  • Em média, o tempo para execução das operações de busca, inserção e remoção é O(log n), onde n é o número de nós.
  • No pior caso (se a árvore não estiver balanceada), o tempo de execução das operações pode chegar a O(n).
• Chaves únicas: Todas as chaves na BST devem ser únicas para manter a ordenação.

3.3 Operações principais

1. Inserção (Insertion):

Princípio de funcionamento:

• Começamos pelo nó raiz.
• Comparamos a chave do novo nó com a chave do nó atual.
• Se a nova chave for menor, vamos para a subárvore esquerda, se for maior, para a direita.
• Repetimos o processo até encontrar um lugar adequado para a inserção do novo nó (ou o filho esquerdo ou direito está ausente).

Algoritmo:

1. Se a árvore estiver vazia, o novo nó torna-se o nó raiz.
2. Caso contrário, encontramos recursivamente o local correto e adicionamos o novo nó.

2. Remoção (Deletion):

Princípio de funcionamento:

• Encontrar o nó para remoção.
• Considerar três casos:
• O nó é uma folha (não tem filhos): basta remover o nó.
• O nó tem um filho: substituímos o nó pelo seu filho.
• O nó tem dois filhos: encontramos o nó mínimo na subárvore direita (ou o máximo na esquerda), copiamos seu valor para o nó a ser removido e removemos recursivamente o nó mínimo na subárvore direita.

Algoritmo:

1. Encontrar o nó com a chave desejada.
2. Dependendo do caso, realizar a remoção correspondente e o realocação dos nós.

3. Busca (Search):

Princípio de funcionamento:

• Começamos pelo nó raiz.
• Comparamos a chave do nó buscado com a chave do nó atual.
• Se a chave coincidir, retornamos o nó.
• Se a chave for menor, vamos para a subárvore esquerda, se for maior, para a direita.
• Repetimos o processo até encontrar o nó com a chave desejada ou alcançamos o final da árvore (nesse caso, o nó não foi encontrado).

Algoritmo:

1. Se a árvore estiver vazia ou a chave do nó coincidir com a desejada, retornamos o nó.
2. Se a chave do nó buscado for menor, buscamos recursivamente na subárvore esquerda.
3. Se a chave do nó buscado for maior, buscamos recursivamente na subárvore direita.

3.4 Exemplos de problemas resolvidos usando BST

1. Busca de elemento em um conjunto dinâmico

É necessário manter um conjunto de números, onde se pode adicionar novos elementos, remover os existentes e rapidamente buscar se um determinado número está no conjunto.

Solução usando BST:

• Inserção de novos elementos na árvore.
• Remoção de elementos existentes.
• Busca de elementos na árvore.

Exemplo de uso:

Manutenção de uma lista de usuários registrados no sistema, onde usuários podem ser adicionados e removidos, e o sistema deve rapidamente verificar se um usuário está registrado.

2. Encontrar o elemento mínimo e máximo

Necessidade de encontrar rapidamente os valores mínimo e máximo em um conjunto de dados.

Solução usando BST:

• O elemento mínimo se encontra no nó mais à esquerda da árvore.
• O elemento máximo se encontra no nó mais à direita da árvore.

Exemplo de uso:

Suporte a um sistema que monitora preços de ações, onde é necessário encontrar rapidamente o preço mínimo e máximo em um momento atual.

3. Verificação de balanceamento de expressões

Dada uma expressão matemática, é necessário verificar seu balanceamento quanto ao número de parênteses de abertura e fechamento.

Solução usando BST:

Usamos BST para armazenar estados intermediários da verificação do balanceamento dos parênteses.

Exemplo de uso:

Parsing e compilação de código, onde é necessário verificar a correta organização dos parênteses nas expressões.

4. Construção de dicionário

É necessário criar uma estrutura de dados para armazenar um dicionário, onde as palavras podem ser adicionadas, removidas e rapidamente encontradas.

Solução usando BST:

• As palavras são adicionadas na árvore em ordem alfabética.
• A busca de palavras é feita por chaves.

Exemplo de uso:

Um sistema de autocorreção de texto, onde é preciso rapidamente encontrar e corrigir palavras.