Árvore de busca binária

Podcast

Árvores de Busca Binária: A Organização é Poder0:00 / 4:28

0:001:00 restante

1x

Uma Árvore de Busca Binária (ABB), ou Binary Search Tree (BST) em inglês, é uma estrutura de dados fundamental para organizar informações de maneira eficiente. Ela permite que operações de busca, inserção e remoção sejam realizadas de forma rápida, especialmente em grandes volumes de dados. Diferente de estruturas como arranjos ou listas encadeadas, que podem ser lentas, as ABBs oferecem um desempenho logarítmico quando bem balanceadas, o que as torna incrivelmente úteis na ciência da computação.

O que é uma Árvore de Busca Binária e Como Funciona?

Uma árvore de busca binária é um tipo de árvore binária, onde cada nó possui no máximo dois filhos: um esquerdo e um direito. Sua característica principal é a propriedade de ordenação, que garante a eficiência das operações.

Propriedades Essenciais da Árvore de Busca Binária

Para que uma ABB funcione corretamente, ela deve seguir algumas regras importantes:

• Propriedade de Ordenação: Para cada nó na árvore, todos os valores na sua subárvore esquerda são menores que o valor do próprio nó. Além disso, todos os valores na sua subárvore direita são maiores que o valor do próprio nó.
• Unicidade de Valores: Embora não seja estritamente obrigatória, é uma convenção comum que as ABBs não permitam valores duplicados. Se duplicatas forem aceitas, uma regra clara deve ser estabelecida, como enviá-las sempre para a subárvore direita ou esquerda.

Essa ordenação é crucial e deve ser mantida em todas as operações para que a árvore permaneça consistente e eficiente. Saiba mais sobre árvores binárias na Wikipedia.

Operações Fundamentais em uma Árvore de Busca Binária

As principais operações em uma ABB são busca, inserção e remoção. A agilidade dessas operações está diretamente ligada à altura da árvore.

1. Busca em Árvore de Busca Binária

A operação de busca tem como objetivo encontrar um valor específico na árvore. O processo é simples e segue a propriedade de ordenação:

• Começa-se sempre pela raiz da árvore.
• Compara-se o valor que você está procurando com o valor do nó atual.
• Se os valores forem iguais, o nó foi encontrado e a busca termina.
• Se o valor buscado for menor, a busca continua na subárvore esquerda.
• Se o valor buscado for maior, a busca continua na subárvore direita.
• Se a busca chegar a um nó nulo (uma subárvore vazia) e o valor não tiver sido encontrado, significa que ele não está presente na árvore.

A complexidade de tempo para a busca é O(h), onde h é a altura da árvore. Em uma ABB balanceada, h é aproximadamente log₂ n (onde n é o número de nós), resultando em O(log n). No pior cenário (árvore degenerada em uma lista), a complexidade pode ser O(n).

2. Inserção em Árvore de Busca Binária

Inserir um novo nó em uma ABB também respeita a propriedade de ordenação. O processo é parecido com a busca para encontrar o lugar certo para o novo nó:

• Começa-se pela raiz da árvore.
• Compara-se o valor a ser inserido com o valor do nó atual.
• Se o valor a ser inserido for menor, avança-se para a subárvore esquerda.
• Se o valor a ser inserido for maior, avança-se para a subárvore direita.
• Repete-se esses passos até encontrar um nó nulo. Este será o local onde o novo nó será inserido como filho (esquerdo ou direito) do nó pai que levou à subárvore nula.

A complexidade de tempo para a inserção é O(h), seguindo os mesmos cenários de melhor e pior caso da busca.

3. Remoção em Árvore de Busca Binária

A remoção de um nó é a operação mais elaborada em uma ABB, pois é crucial manter a propriedade de ordenação após a exclusão. Existem três situações principais ao remover um nó N:

• Caso 1: O nó N é uma folha (não tem filhos).
• Basta remover o nó N. O ponteiro do seu pai correspondente (esquerdo ou direito) deve ser definido como nulo.
• Caso 2: O nó N tem apenas um filho (esquerdo ou direito).
• O nó N é substituído pelo seu único filho. O pai de N agora passa a apontar diretamente para o filho de N.
• Caso 3: O nó N tem dois filhos.
• Este é o cenário mais complexo. Para preservar a propriedade da ABB, o nó N precisa ser substituído por um de seus sucessores ou antecessores que mantenham a ordem. Geralmente, substitui-se pelo nó de menor valor na sua subárvore direita (o sucessor in-order) ou pelo nó de maior valor na sua subárvore esquerda (o predecessor in-order). Após a substituição, o nó substituto original é removido da sua posição inicial, que se enquadrará nos casos 1 ou 2.

Perguntas Frequentes sobre Árvore de Busca Binária

Qual a principal vantagem de uma Árvore de Busca Binária?

A principal vantagem de uma ABB é a eficiência nas operações de busca, inserção e remoção. Quando a árvore está balanceada, essas operações são realizadas em tempo logarítmico, O(log n), o que é muito mais rápido do que o tempo linear O(n) de estruturas como listas encadeadas, especialmente para grandes volumes de dados.

Como saber se uma Árvore de Busca Binária está balanceada?

Uma ABB está balanceada quando sua altura é a menor possível, geralmente log₂ n, onde n é o número de nós. Isso significa que a diferença de altura entre as subárvores esquerda e direita de qualquer nó é mínima. Árvores balanceadas, como as AVL ou Red-Black Trees, garantem o desempenho O(log n) em todas as operações.

Quais são as aplicações práticas da Árvore de Busca Binária?

As ABBs são usadas em diversas áreas da computação, como em sistemas de banco de dados para indexação de informações, na implementação de dicionários e conjuntos para armazenar elementos únicos, e em algoritmos de busca e ordenação. Elas são fundamentais para organizar dados de forma que possam ser acessados e modificados rapidamente.