Vídeo: Estrutura de Dados - Aula 16 - Árvores binárias de pesquisa - Parte 1 2024
Um tipo especial de estrutura de árvore é o binário, que coloca cada um dos elementos do nó em uma ordem especial. As árvores de pesquisa permitem que você procure dados rapidamente. Obtendo itens de dados, colocando-os em ordem ordenada em uma árvore, e depois pesquisando essa árvore é uma das maneiras mais rápidas de encontrar informações.
Em uma pilha binária, o nó da raiz sempre contém o menor valor. Ao visualizar os ramos, você vê que os ramos do nível superior são sempre um valor menor que os ramos e as folhas de nível inferior. O efeito é manter a árvore equilibrada e em uma ordem previsível para que a busca se torne extremamente eficiente. O custo é manter a árvore equilibrada.
De todas as tarefas que as aplicações fazem, a pesquisa é mais demorada e também a mais necessária. Mesmo que adicionar dados (e ordená-lo mais tarde) exige algum tempo, o benefício para criar e manter um conjunto de dados vem de usá-lo para executar trabalhos úteis, o que significa pesquisá-lo para informações importantes. Consequentemente, às vezes você consegue passar por uma funcionalidade CRUD menos eficiente e até mesmo uma rotina de classificação menos ótima, mas as pesquisas devem ser realizadas com a maior eficiência possível. O único problema é que nenhuma busca executa cada tarefa com eficiência absoluta, então você deve pesar suas opções com base no que você espera fazer como parte das rotinas de pesquisa.
Dois dos métodos de pesquisa mais eficientes envolvem o uso da árvore de pesquisa binária (BST) e pilha binária. Ambas as técnicas de busca dependem de uma estrutura semelhante a uma árvore para manter as chaves usadas para acessar elementos de dados. No entanto, o arranjo dos dois métodos é diferente, razão pela qual um tem vantagens sobre o outro ao executar certas tarefas. Esta figura mostra o arranjo para um BST.
Observe como as teclas seguem um pedido em que números menores aparecem à esquerda e os números maiores aparecem à direita. O nó raiz contém um valor que está no meio do intervalo de chaves, dando à BST uma abordagem equilibrada facilmente compreendida para armazenar as chaves. Contraste este arranjo para o monte binário mostrado aqui.
Cada nível contém valores que são inferiores ao nível anterior e a raiz contém o valor da chave máxima para a árvore. Além disso, neste caso particular, os valores menores aparecem à esquerda e maior à direita (embora esta ordem não seja rigorosa). A figura realmente representa um montão máximo binário. Você também pode criar um bin binário infinito em que a raiz contém o valor da chave mais baixa e cada nível cria valores maiores, com os valores mais altos que aparecem como parte das folhas.
Como observado anteriormente, o BST tem algumas vantagens sobre o heap binário quando usado para realizar uma pesquisa. A lista a seguir fornece alguns dos destaques dessas vantagens:
- A procura de um elemento requer tempo O (log n), contrastado com o tempo O (n) para um heap binário.
- Imprimir os elementos em ordem requer apenas o tempo O (log n), contrastado com o tempo O (n log n) para uma pilha binária.
- Encontrar o piso e o teto requerem tempo de O (log n).
- Localizando Kth menor / maior elemento requer tempo O (log n) quando a árvore está configurada corretamente.
Se estes tempos são importantes depende da sua aplicação. BST tende a funcionar melhor em situações em que você gasta mais tempo buscando e menos tempo construindo a árvore. Uma pilha binária tende a funcionar melhor em situações dinâmicas nas quais as chaves mudam regularmente. O hebra binário também oferece vantagens, conforme descrito na seguinte lista:
- A criação das estruturas necessárias requer menos recursos porque os montes binários dependem de arrays, tornando-os mais amigáveis para o cache.
- Construir uma pilha binária requer tempo O (n), contrastado com BST, que requer tempo O (n log n).
- Usar ponteiros para implementar a árvore não é necessário.
- Baseando-se em variações de hemer binário (por exemplo, o Fibonacci Heap) oferece vantagens como aumentar e diminuir os tempos-chave do tempo de O (1).
