ARVORE BINÁRIA

ARVORE BINARIA

DEFINIÇÃO

Em ciência da computação, a árvore de busca binária ou árvore de pesquisa binária é uma árvore binária onde todos os nós são valores, todo nó a esquerda contêm uma sub-árvore com os valores menores ao nó raiz da sub-árvore e todos os nós da sub-árvore a direita contêm somente valores maiores ao nó raiz. (Esta é a forma padrão, podendo ser invertida as sub-árvores dependendo da aplicação). Os valores são relevantes na árvore de busca binária. O objetivo desta árvore é estruturar os dados de forma flexível permitindo pesquisa binária



Termos de árvore:

Nó: são todos os ítens guardados na árvore.
Raiz é o item do topo da árvore (neste caso o número 50).
Filho são os itens logo abaixo da raiz, 30 e 90 e assim sequencialmente, por exemplo, o 20 é filho do 30.
Parente são os nós do mesmo nível, por exemplo, o 90 é parente do 100.
Folha é um nó que não tem filho, é o último item da árvore, por exemplo, 20, 40 e 100.

Busca

Para a busca em uma árvore binária por um valor específico começamos examinando a raiz. Se o valor for igual a raiz, o valor existe na árvore. Se o valor for menor do que a raiz, então deve buscar na sub-árvore da esquerda, e assim recursivamente em todos os nós da sub-árvore.

Similarmente, se o valor for maior do que a raiz, então deve buscar na sub-árvore da direita. Até alcançar o nó folha da árvore, encontrando ou não o valor requerido.

Inserção

A inserção começa com uma busca; procurando pelo valor, mas se não for encontrado, procuraremos as sub-árvores da esquerda ou direita como na busca. Eventualmente, alcançaremos a folha, e então inserimos o valor nesta posição. Ou seja nós examinamos a raiz e introduzimos um nó novo na sub-árvore da esquerda se o valor novo é menor do que a raiz, ou na sub-árvore da direita se o valor novo for maior do que a raiz.

Uma outra maneira de explicar a inserção é que a fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menos do que a raiz, é comparado então com o valor do filho da esquerda da raiz. Se seu valor for maior, está comparado com o filho da direita da raiz. Este processo continua até que o nó novo esteja comparado com um nó da folha, e então adiciona-se o filho da direita ou esquerda, dependendo de seu valor.

Exclusão

Exclusão na folha:




Exclusão de um nó com um filho. O filho do nó excluído passa a ocupar a posição do pai.






Exclusão de um nó com dois filhos. Neste caso pode-se operar de duas maneiras diferentes. Pode-se substituir o valor do nó a ser retirado pelo valor sucessor (o nó mais a esquerda da sub-árvore direita) ou pelo valor antecessor (o nó mais a direita da sub-árvore esquerda), e aí remove-se o nó sucessor (ou antecessor).




No exemplo acima, o nó de valor 30 está para ser removido, e possui como sucessor imediato o valor 40 e como antecessor imediato do 40 o valor 35. Assim sendo, na exclusão, o filho do 40 será promovido no lugar o nó a ser excluído, o 40 continuará no mesmo lugar, como pode ser visto na figura.

Ao excluir um nó, ou mesmo ao incluir um nó, pode haver o desbalanceamento da árvore, sendo corrigido, por exemplo, com o balanceamento AVL.

Percurso

Em uma árvore binária de busca pode-se fazer os três percursos que faz para uma árvore binária qualquer (percursos em inordem, preordem e posordem). Uma característica interessante é quando se faz um percurso em ordem em uma árvore binária de busca. Ao efetuar esse percurso, os valores dos nós aparecem em ordem crescente.

A operação "Percorre" tem como objetivo percorrer a árvore numa dada ordem enumerando os seus nós. Quando um nó é enumerado, dizemos que ele foi "visitado".

Recursão

Caso trivial: Percorrer uma árvore vazia: nada é feito. Caso mais simples que o problema original:

Pré-ordem (ou profundidade):
Visita a raiz;
Percorre a sub-árvore esquerda em pré-ordem;
Percorre a sub-árvore direita em pré-ordem.

Ordem Simétrica:
Percorre a sub-árvore esquerda em ordem simétrica;
Visita a raiz;
Percorre a sub-árvore direita em ordem simétrica.

Pos-ordem:
Percorre a sub-árvore esquerda em pos-ordem;
Percorre a sub-árvore direita em pos-ordem;
Visita a raiz.

VIDEOS AULAS