Árvores Binárias de Busca
Definição: É uma árvore binária em que todos os valores na subárvore esquerda são menores que o da raiz e todos os valores da subárvore direita são maiores (ou iguais) que o da raiz.
Exemplos de árvores binárias de busca:
Usando o caminhamento central, teríamos:
Seqüência (1° árvore): A, B, C, D, E, F e G.
Seqüência (2° árvore): 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 e 110.
Para ver uma implementação de uma árvore binária encadeada, abra a unit ArvBinB e para um programa que demonstra como usá-la, veja PArvBinB.
A função EncontrarChave busca na árvore passada a chave informada. Se encontrar, P apontará para o nó que a contém e a função retorna true. Caso não encontre, a função retorna false e P aponta para o nó que seria o seu pai caso existisse.
A função Inserir usa EncontrarChave para verificar se a chave já existe. Caso exista, retorna false. Se não existir, aproveita o apontador P (aponta para o pai correto do nó a ser inserido) e inclui na subárvore esquerda de P se a chave sendo inserida for menor ou na direita se for maior, retornando true.
A remoção de um nó pode ser mais simples ou complexa de acordo com o número de subárvores que possui.
a) Removendo um nó sem subárvore (folha):
Nesse caso, basta apagar o nó e atualizar o apontador para ele no pai para nil.
b) Removendo um nó com uma subávore:
Nesse caso basta desviar o apontador que apontava para o nó a ser removido para a sua única subárvore. Por último, elimina-se o nó.
c) Removendo um nó com duas subávore:
Nesse caso é necessário encontrar o sucessor imediato, copiar o seu conteúdo para o nó a ser removido e remover o nó que continha o sucessor imediato.
Para remover um nó nesse caso teremos que colocar um outro nó no lugar daquele que vai ser removido. Para a escolha desse nó podemos usar duas abordagens: