Análise de Algoritmo e Estrutura de Dados

Árvores

As árvores são estruturas de dados multidimensionais que permitem a representação de hierarquias,

ou a representação em vários níveis. Uma árvore é composta por um conjunto de nós, que podem
ou não ter ramificações. Existe um nó denominado raiz, que pode ramificar-se (ou não) em
“subárvores”, cujas raízes são ligadas diretamente a essa raiz, e assim sucessivamente. Esses nós-
raízes das “subárvores” são ditos filhos do nó-pai que podem ter mais nós-filhos. Portanto, em razão
dessa característica de comportamento igual entre nó-pai e nó-filho, uma estrutura de árvore pode
ser trabalhada usando a recursividade.

Nós com filhos são comumente chamados de nós internos, e nós que não têm filhos são chamados
de folhas ou nós externos. É tradicional desenhar as árvores com a raiz para cima e as folhas para
baixo.

Estrutura e dados do tipo árvore binária

1
Árvores binárias: uma árvore binária é um caso
especial de árvore em que um pai tem, no máximo,
dois filhos (zero, um ou dois). Assim,
recursivamente, os filhos são pais que têm, no
máximo, dois filhos. O uso da árvore binária é o
mais difundido, e muitas vezes a adotamos sem
saber que a estamos utilizando. Quando

efetuamos: montamos
uma árvore binária da seguinte forma:

Árvores binárias: em uma árvore binária, o

caminho percorrido para sair de um nó e chegar a
outro sempre será único. Assim, a propriedade
fundamental da árvore binária é que, da raiz até
qualquer um dos seus nós, haverá somente um
caminho. A quantidade de nós percorridos da raiz
(sem contá-la) até a folha mais distante determina a
altura da árvore. Uma árvore apenas com a raiz
tem altura zero.

Árvore com altura dois:

Numa árvore binária, quando um nó tem ramificações, cada uma delas recebe um nome. A
ramificação esquerda receberá o nome de Subárvore Esquerda (SAE), e a ramificação direita será a
Subárvore Direita (SAD).

2
Mesmo tendo duas informações iguais, uma árvore que tem uma informação na SAE e outra que
tem a mesma informação na SAD são diferentes:

Percurso em árvores binárias: a posição da informação nas subárvores é importante, pois, muitas
vezes, precisamos percorrer uma árvore para buscar informação, ou mesmo para descrevê-la. Ao
percorrer uma árvore, precisamos ter um critério, pois não podemos tomar um caminho qualquer,
sob o risco de passarmos e colhermos informação de um mesmo nó.

Dentro de uma árvore, o conceito de recursividade torna-se fundamental, pois, em árvores grandes,
dificilmente teríamos duas subárvores iguais e, portanto, não podemos antever uma sequência fixa
de operações.

Percurso em pré-ordem ou prefixo (busca em profundidade):

O percurso completo resulta: 5 2 1 3 4 7 6 8.

Percurso em ordem ou infixo (ordem simétrica):

3
 O percurso completo resulta: 1 2 3 4 5 6 7 8.
Percurso em pós-ordem ou posfixo:

O percurso completo resulta: 1 4 3 2 6 8 7 5.

Assinale a alternativa que apresenta o percurso em pós-ordem (posfixo) na
árvore abaixo:

4
 a) A B C D E F H I

b) E B H A C F I D

c) A B C D E F G H

d) A D C B F I H E

e) E D B H A C F I

Árvores binárias de busca

Uma árvore binária de busca ou árvore binária de pesquisa é uma estrutura de dados em que todos
os nós da subárvore esquerda possuem valor inferior ao do nó-raiz e todos os nós da subárvore
direita possuem um valor superior ao do nó-raiz. Dessa forma, a busca de um valor torna-se muito
fácil, pois, a partir de simples comparações, podemos localizá-lo com menos passos.

No caso de uma estrutura linear, teríamos:

Na mesma sequência de entrada, em uma árvore, temos:

5
Fazendo a busca do número 2:

Estrutura linear:

Estrutura em árvore

Operação de busca
Na busca, as seguintes operações devem ser realizadas recursivamente, lembrando que a cada
movimentação, o novo nó passa a ser a raiz:

6
  se o valor procurado for igual ao da raiz, o valor será encontrado;
 se o valor procurado for menor que o da raiz, deveremos buscar na SAE;
 se o valor procurado for maior que o da raiz, deveremos buscar na SAD;
 Se o nó for folha da árvore, o valor requerido não terá sido encontrado.

Achar o valor 72 na árvore:

Nós percorridos: 50, 67, 80 (Não

encontrado).

Achar o valor 31 na árvore:

Nós percorridos: 50, 20, 31.

Operação de inserção
Deve ser feita com bastante critério, pois o novo valor inserido não pode quebrar a estrutura da
árvore, mas é bem simples, uma vez entendida a operação de busca. Fazemos a operação de
busca; ao encontrarmos uma subárvore livre ou uma folha, devemos obedecer ao seguinte critério:
 se a chave a ser inserida for menor que a chave do nó analisado, inseriremos a chave na
subárvore esquerda;
 se a chave a ser inserida for maior que a chave do nó analisado, inseriremos a chave na
subárvore direita;
 se a subárvore estiver ocupada, seguiremos com a busca

7
Inserir o valor 88:

Operação de remoção
Fazer a remoção de um nó sem comprometer a estrutura é um processo mais complexo. Para
excluir um nó de uma árvore binária de busca, devemos considerar três situações:
 remoção na folha;
 remoção de um nó com um filho;
 remoção de um nó com dois filhos.

Remoção de folha

basta remover o
nó da árvore

Remoção de folha com um filho:

8
Excluímos o nó, e
o filho sobe para a
posição do pai.

Remoção de folha
com dois filhos
(primeira forma):
substituímos o valor
do nó a ser retirado
pelo nó mais à
direita da subárvore
esquerda.

Remoção de folha
com dois filhos
(segunda forma):
substituímos o valor
do nó a ser retirado
pelo nó mais à
esquerda da
subárvore direita.

9
Em uma árvore binária cada nó tem no máximo
duas “subárvores”, e quando há somente um
presente é necessário distinguir entre “subárvore”
esquerda e direita. Formalmente uma árvore binária
pode ser definida como um conjunto finito de nós,
que é vazio, ou consiste em um nó raiz e dois
conjuntos disjuntos de nós, a “subárvore” esquerda
e a “subárvore” direita.
Podemos numerar os nós de uma árvore binária
cheia da seguinte forma: começamos a partir da
raiz e "descemos" para o nível 1 depois o nível 2,
nível 3 etc. Os nós em qualquer nível são
numerados da esquerda para direita. A figura
abaixo apresenta uma árvore binária cheia com a
enumeração correspondente.

Inserindo em uma árvore binária balanceada.

package arvore;

10
class ArvoreBinaria{
public static void main(String[] args){
BArvore arvore1 = new BArvore ();
arvore1.inserirNo (14);
arvore1.inserirNo (16);
arvore1.inserirNo (12);
arvore1.inserirNo (11);
arvore1.inserirNo (17);
arvore1.inserirNo (15);
arvore1.inserirNo (10);
arvore1.inserirNo (13);
arvore1.exibirNo ();
arvore1.excluirNo (12);
System.out.println ("");
arvore1.exibirNo ();
}
}

package arvore;
class BArvore{
private BIntNo Raiz;

private BIntNo inserir (BIntNo arvore, int novoNo){

if (arvore == null)
return new BIntNo (novoNo);
else if (novoNo < arvore.valor)
arvore.esq = inserir (arvore.esq, novoNo);
else
arvore.dir = inserir (arvore.dir, novoNo);
return arvore;
}
public void inserirNo (int novoValor){
Raiz = inserir (Raiz, novoValor);
}
private void exibir (BIntNo arv){
if (arv != null){
exibir (arv.esq);
System.out.println (arv.valor);
exibir (arv.dir);
}
}

public void exibirNo (){

exibir (Raiz);
}

public void excluirNo (int item){

try{
BIntNo tempNo = Raiz, pai = null, filho = Raiz, temp;
while (tempNo != null && tempNo.valor != item){

11
 pai = tempNo;
if (item < tempNo.valor)
tempNo = tempNo.esq;
else
tempNo = tempNo.dir;
}
if (tempNo == null)
System.out.println ("Item nao localizado.");
if (pai == null){
if (tempNo.dir == null)
Raiz = tempNo.esq;
else if (tempNo.esq == null)
Raiz = tempNo.dir;
else{
for (temp = tempNo, filho = tempNo.esq;
filho.dir != null; temp = filho, filho = filho.dir);
if (filho != tempNo.esq){
temp.dir = filho.esq;
filho.esq = Raiz.esq;
}
filho.dir = Raiz.dir;
Raiz = filho;
}
}else if (tempNo.dir == null){
if (pai.esq == tempNo)
pai.esq = tempNo.esq;
else
pai.dir = tempNo.esq;
}else if (tempNo.esq == null){
if (pai.esq == tempNo)
pai.esq = tempNo.dir;
else
pai.dir = tempNo.dir;
}else{
for (temp = tempNo, filho = tempNo.esq;
filho.dir != null; temp = filho, filho = filho.dir);
if (filho != tempNo.esq){
temp.dir = filho.esq;
filho.esq = tempNo.esq;
}
filho.dir = tempNo.dir;
if (pai.esq == tempNo)
pai.esq = filho;
else
pai.dir = filho;
}
}catch (NullPointerException erro){
//Item nao encontrado
}
}
}

12
package arvore;

class BIntNo{
int valor;
BIntNo esq, dir;

BIntNo (int novoValor){

valor = novoValor;
}
}

Exercícios:
1) Altere o exemplo apresentado anteriormente, sobre a teoria de árvore binária,
para que tenha um Menu para Inserir, Excluir e Sair. As informações deverão ser
inseridas pelo usuário.
2) Estude e fale sobre os algoritmos de inclusão e alteração. Conceito raiz e folha. E
como funciona uma arvore binária balanceada.
3) Alterar o algoritmo para dependo da escolha do usuário exibir a árvore em pré-
ordem, pós-ordem e em ordem.

13