Uso de árvores

5.1 Uso de árvores para busca de dados

Árvores binárias de busca (Binary Search Trees — BST) são usadas para procurar dados:

Árvores binárias de busca (BST) organizam dados de forma que para qualquer nó, todas as chaves na subárvore à esquerda são menores que a chave do nó, e todas as chaves na subárvore à direita são maiores que a chave do nó.

Essa propriedade permite realizar operações de busca de forma eficiente.

Princípios de funcionamento:

• A busca por um elemento na BST começa na raiz.
• Se o valor buscado for menor que o valor do nó atual, a busca se desloca para a subárvore à esquerda.
• Se o valor buscado for maior, a busca se desloca para a subárvore à direita.
• O processo se repete até que o elemento buscado seja encontrado ou se alcance o final da árvore.

Vantagens:

• Tempo médio de busca — O(log n), onde n é o número de nós na árvore.
• A eficiência da busca depende do equilíbrio da árvore.

5.2 Ordenação por árvore

Ordenação por árvore é um método de ordenação baseado no uso de uma árvore binária de busca. Os elementos são adicionados ao BST, e então a travessia da árvore na ordem "in-order" (subárvore à esquerda → nó atual → subárvore à direita) produz um array ordenado.

Passos do algoritmo:

1. Insira todos os elementos do array em uma árvore binária de busca.
2. Execute a travessia da árvore na ordem "in-order" para obter um array ordenado.

Vantagens:

• Ordenação por árvore proporciona um tempo médio de execução de O(n log n).
• Proporciona ordenação estável (se os dados originais possuem elementos iguais, sua ordem relativa é mantida).

Desvantagens:

No pior caso, quando a árvore não está balanceada, o tempo de execução pode chegar a O(n^2).

5.3 Exemplos de problemas resolvidos usando árvores

1. Busca de elemento mínimo e máximo:

Descrição:

• Encontrar o valor mínimo na BST pode ser feito indo até o nó mais à esquerda.
• Encontrar o valor máximo pode ser feito indo até o nó mais à direita.

Aplicação:

• Em sistemas de controle de estoque para encontrar a quantidade mínima e máxima de produtos.
• Em sistemas bancários para determinar transações mínimas e máximas.

2. Busca por intervalo:

Descrição:

• Encontre todos os elementos cujos valores estão em um intervalo especificado.
• A travessia na ordem "in-order" é usada com verificação adicional para ver se o nó está dentro do intervalo.

Aplicação:

• Em bancos de dados para realizar consultas de intervalo.
• Em sistemas de monitoramento, onde é necessário rastrear valores de parâmetros dentro de limites especificados.

3. Suporte a operações de autocomplete:

Descrição:

• Armazenamento de strings (por exemplo, palavras) em forma de árvore (por exemplo, trie).
• Busca rápida de todas as strings que começam com um prefixo dado.

Aplicação:

• Em motores de busca para sugestões ao digitar uma consulta.
• Em editores de texto para sugestões de autocomplete.

4. Otimização de rotas e caminhos:

Descrição:

• Armazenamento de pontos e rotas em forma de árvore.
• Busca de caminhos ótimos e distâncias mínimas usando algoritmos em árvores.

Aplicação:

• Em sistemas de navegação para traçar rotas.
• Em sistemas logísticos para otimizar a entrega.

5. Organização de dados hierárquicos:

Descrição:

• Uso de árvores para representar e gerenciar estruturas hierárquicas, como estruturas organizacionais, sistemas de arquivos e árvores genealógicas.

Aplicação:

• Em sistemas de informação corporativa para representar a estrutura da empresa.
• Em sistemas de gestão de conteúdo (CMS) para organização de arquivos e documentos.