Resumo de Árvore de busca binária
Árvore de Busca Binária: Guia Completo para Estudantes
Árvores de Busca Binária (ABB)
Bem-vindo ao mundo das Árvores de Busca Binária (ABBs)! Esta estrutura de dados é um dos pilares da ciência da computação, essencial para organizar informações de forma eficiente. Imagine uma biblioteca onde cada livro tem seu lugar exato, permitindo que você o encontre rapidamente. As ABBs fazem algo parecido com dados digitais, garantindo que operações como buscar, adicionar ou remover elementos sejam realizadas de maneira ágil, especialmente quando lidamos com grandes volumes de informação.
Enquanto listas simples ou arranjos podem levar muito tempo para encontrar um item (proporcional ao número total de itens), as ABBs, quando bem organizadas, conseguem fazer isso em tempo logarítmico. Isso significa que, mesmo com milhões de itens, o tempo de busca aumenta muito pouco, tornando-as incrivelmente poderosas para diversas aplicações.
Propriedades Fundamentais de uma Árvore de Busca Binária
Uma ABB é, antes de tudo, uma árvore binária, o que implica que cada nó pode ter, no máximo, dois "filhos": um esquerdo e um direito. Contudo, o que realmente a diferencia e a torna uma "árvore de busca" são suas propriedades de ordenação:
-
Propriedade de Ordenação: Para que uma árvore seja considerada uma ABB, a seguinte regra deve ser rigorosamente mantida para qualquer nó nela:
- Todos os valores localizados na subárvore esquerda de um nó são menores que o valor contido no próprio nó.
- Todos os valores localizados na subárvore direita de um nó são maiores que o valor contido no próprio nó.
-
Unicidade (Convenção Comum): Embora não seja uma regra absoluta em todas as definições, é uma prática muito comum que as ABBs não permitam valores duplicados. Se a necessidade de armazenar duplicatas surgir, uma convenção específica deve ser estabelecida (por exemplo, todos os valores iguais vão para a subárvore direita ou esquerda), mas isso pode complicar algumas operações.
Nó
Em estruturas de dados de árvore, um nó é o elemento fundamental que contém um dado (valor) e, opcionalmente, referências (ponteiros) a outros nós (seus filhos).
Essa propriedade de ordenação é a chave para a eficiência das ABBs. Ela deve ser mantida em todas as operações (inserção, busca, remoção), garantindo que a estrutura permaneça consistente e que as buscas continuem sendo realizadas de forma otimizada.
Operações Básicas em uma Árvore de Busca Binária
As principais operações em uma ABB são a busca e a inserção. A eficiência dessas operações está diretamente ligada à altura da árvore ($h$), que é a distância do nó raiz ao nó mais distante.
1. Busca (Pesquisa)
A operação de busca tem como objetivo encontrar um nó que contenha um valor específico dentro da árvore. O algoritmo é intuitivo e segue diretamente a propriedade de ordenação da ABB:
- A busca sempre começa pelo nó raiz da árvore.
- O valor que queremos encontrar é comparado com o valor do nó atual.
- Se os valores forem iguais, o nó desejado foi encontrado e a busca termina com sucesso.
- Se o valor a ser buscado for menor que o valor do nó atual, então (pela propriedade de ordenação) ele só pode estar na subárvore esquerda. A busca prossegue nesse ramo.
- Se o valor a ser buscado for maior que o valor do nó atual, ele só pode estar na subárvore direita. A busca continua por ali.
- Se a busca alcançar um nó nulo (ou seja, uma subárvore vazia) e o valor ainda não tiver sido encontrado, isso significa que o valor não está presente na árvore.
Altura da Árvore ($h$)
A altura de uma árvore é o número de arestas no caminho mais longo da raiz até uma folha. Uma árvore com apenas um nó (a raiz) tem altura $0$.
A Complexidade de Tempo da busca é g
Regista-te para o resumo completoJá tem uma conta? Entrar
Árvores de Busca Binária
Klíčová slova: Árvores de Busca Binária, Remoção de Nós em ABB
Klíčové pojmy: Uma Árvore de Busca Binária (ABB) é uma estrutura de dados fundamental., Cada nó em uma ABB tem no máximo dois filhos: esquerdo e direito., A propriedade de ordenação exige que valores à esquerda de um nó sejam menores e à direita sejam maiores., É comum que ABBs não permitam valores duplicados., A operação de busca começa na raiz e segue a propriedade de ordenação para encontrar um valor., A complexidade de tempo da busca é $O(h)$, onde $h$ é a altura da árvore., Para árvores balanceadas, a busca é $O(\log n)$; para árvores degeneradas, é $O(n)$., A inserção de um novo nó segue um processo similar à busca para encontrar o local correto., A complexidade de tempo da inserção também é $O(h)$, seguindo os mesmos cenários de melhor e pior caso., ABBs são amplamente utilizadas em indexação de bancos de dados, sistemas de arquivos e compiladores.