Árvore de busca

Em ciência da computação, uma árvore de busca é uma árvore utilizada para a localização de chaves específicas dentro de um conjunto. Para que uma árvore funcione como uma árvore de busca, a chave para cada nó deve ser maior do que quaisquer chaves presentes em subárvores da esquerda e menor a quaisquer chaves em subárvores à direita.^[1]

A vantagem dessas árvores está no seu eficiente tempo de busca quando a árvore está razoavelmente balanceada, o que equivale a dizer que as folhas em cada extremidade, estão em igual profundidade. Vários tipos de árvores de pesquisa existem, muitos dos quais também permitem uma eficiente inserção e exclusão de elementos.

Tipos de Árvores

Árvore binária de busca

Árvore Binária De Busca

Uma Árvore binária de busca é uma estrutura de dados vinculada, baseada em nós, onde cada nó contém uma chave e duas subárvores à esquerda e a direita. Para todos nós, a chave da subárvore esquerda deve ser menor que a chave desse nó, e a chave da subárvore direita deve ser maior. Todas estas subárvores devem qualificar-se como árvores binárias de busca.

O pior caso de tempo de complexidade para a pesquisa em uma árvore binária de busca é a altura da árvore, isso pode ser tão pequeno como O(log n) para uma árvore com n elementos.

Árvore B

Árvores B são generalizações de árvores binárias de busca que podem ter um número variável de subárvores e chaves em cada nó. Mesmo que nós-filhos possuam um tamanho pré-definido, eles podem não necessariamente estar preenchidos com os dados, o que significa árvores B podem desperdiçar certo espaço. A vantagem é que as árvores B não precisam ser reequilibrados com frequência, assim como outras árvores auto-balanceadas.

Devido à faixa variável do tamanho de cada nó, árvores B são úteis para sistemas que realizam leitura de grandes blocos de dados. Elas também são muito utilizadas em bancos de dados.

O tempo de complexidade para a busca em uma árvore B é O(log n).

Árvores (a,b)

Uma árvore (a,b) é uma árvore de busca onde todas as suas folhas têm a mesma profundidade. Cada nó tem, no mínimo, a filhos e, no máximo, b filhos, enquanto que a raiz tem, no mínimo, 2 filhos e, no máximo, b filhos.

a e b podem ser decididos de acordo com a seguinte fórmula:^[2]

$2\leq a\leq {\frac {(b+1)}{2}}$

O tempo de complexidade para o algoritimo de busca em uma árvore (a,b) é O(log n).

Árvore ternária de busca

Uma árvore ternária de busca é um tipo de trie que pode ter de 3 nós: um filho menor, um filho igual, e um filho maior. Cada nó armazena um único caractere, e a árvore em si é ordenada da mesma forma que uma árvore binária de busca é, com a exceção do possível terceiro nó.

Procurar em uma árvore ternária de busca envolve passar uma sequência de caracteres para testar se qualquer caminho a contém.

O tempo de complexidade para a busca em uma árvore ternária de busca balanceada é O(log n).

Ver também

Referências

↑ Black, Paul and Pieterse, Vreda (2005). "search tree".
↑ Toal, Ray. "(a,b) Trees"

[1] Black, Paul and Pieterse, Vreda (2005). "search tree".

[2] Toal, Ray. "(a,b) Trees"

[1]

[2]