Estrutura de Dados FT UNICAMP

Prévia do material em texto

12/4/2018 Estrutura de Dados - FT - UNICAMP
https://www.ft.unicamp.br/liag/siteEd/definicao/arvore-binaria.php 1/3
Árvore Binária
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:
12/4/2018 Estrutura de Dados - FT - UNICAMP
https://www.ft.unicamp.br/liag/siteEd/definicao/arvore-binaria.php 2/3
 
 
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.
12/4/2018 Estrutura de Dados - FT - UNICAMP
https://www.ft.unicamp.br/liag/siteEd/definicao/arvore-binaria.php 3/3
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):
1. Visita a raiz;
2. Percorre a sub-árvore esquerda em pré-ordem;
3. Percorre a sub-árvore direita em pré-ordem.
Ordem Simétrica:
1. Percorre a sub-árvore esquerda em ordem simétrica;
2. Visita a raiz;
3. Percorre a sub-árvore direita em ordem simétrica.
Pos-ordem:
1. Percorre a sub-árvore esquerda em pos-ordem;
2. Percorre a sub-árvore direita em pos-ordem;
3. Visita a raiz.
Vídeos Explicativos
(em português).
(em português).
(em inglês).
Referências e Fontes:
1. Antigo site de estrutura de dados do LIAG.