Árvores Binárias de Busca
Last updated
Was this helpful?
Last updated
Was this helpful?
Uma importante aplicação de árvores binárias é a pesquisa. A finalidade desta árvore é estruturar os dados de tal maneira que possibilite uma pesquisa binária.
São consideradas árvores binárias de busca as estruturas que obedecem às seguintes características:
a) todas as chaves da subárvore esquerda são menores que a chave da raiz; b) todas as chaves da subárvore direita são maiores que a chave raiz; e c) as subárvores direita e esquerda são também árvores binárias de busca.
Essa estrutura possibilita que a busca por uma determinada chave seja realizada com um número menor de comparações. A busca de uma chave “n” segue os seguintes passos:
a) inicialmente compare com a raiz; b) se menor, vá para a subárvore esquerda; e c) se maior, para a subárvore direita.
Sabendo que a árvore acima é uma árvore binária de busca, para encontrarmos a chave “H” vamos percorrer os seguintes nós: B -> J -> F -> H.
Assim, começando pela raiz temos: H é maior que B, segue a subárvore da direita; “H” é menor que “J”, segue a subárvore da esquerda; “H” é maior que “F”, segue a subárvore da direita e finalmente encontramos a chave.
As operações em árvores binárias devem satisfazer as regras que as definem, isto é, todas as chaves da subárvore esquerda devem ser menores que a chave da raiz e todas as chaves da subárvore direita devem ser maiores que a chave da raiz.
Depois de realizada uma inserção, a árvore deverá manter suas características. Para inserir um nó na árvore, são necessários os seguintes passos:
Pesquisar a chave a ser inserida; e
Se não achar, inserir no último nó da pesquisa.
No exemplo abaixo, a chave 5 deve ser inserida na árvore:
Realizamos a pesquisa da chave 5 e, inicialmente, comparamos com a raiz 6. Como o 5 é menor, vamos pela subárvore à esquerda. Comparamos com o nó 2 e, como 5 é maior, vamos pela direita, onde comparamos com o 4 e, como 5 é maior, vamos pela direita. Como o nó 4 é uma folha, não temos mais como caminhar e, então, inserimos o novo nó.
A operação de remoção de um nó é mais complexa e envolve alguns arranjos na árvore binária. De acordo com a posição do nó a ser removido, temos três condições que devem ser observadas:
a) se o nó é folha, apenas remover imediatamente;
b) se possuir um filho, pode ser removido após os ajustes do ponteiro de seu pai, isto é, seu pai deverá apontar para seu filho; e
c) se o nó possuir dois filhos, deve-se substituir este nó com o nó da subárvore à direita que possuir a chave com o menor valor e remover aquele nó. Como o menor nó da subárvore direita não pode ter um filho à esquerda, a sua remoção segue a condição do item “a”.
