Embed Size (px)
Citation preview
Árvores São estruturas de dados adequadas para a representação de
hierarquias.
Uma árvore é composta por um conjunto de nós.
Existe um nó r, denominado raiz, que contém zero ou mais subárvores, cujas raízes são ligadas diretamente a r.
A raiz se liga a um ou mais elementos, e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.
Árvores Fundamentos básicos
GRAU – número de subárvores de um nó.
FOLHA – um nó que possui grau zero, ou seja, não possui
subárvores.
FILHOS – são as raízes das subárvores de um nó.
Nó não terminal é um nó que não é uma folha e é diferente da
raiz.
Árvores Fundamentos básicos
A altura de uma árvore é o comprimento do caminho mais
longo da raiz até uma das folhas.
Uma árvore nula tem altura 0.
Todos os nós são acessíveis a partir da raiz.
Existe um único caminho entre a raiz e qualquer outro nó.
Árvores Formas de representação gráfica
Árvores Binárias Árvore Binária: Uma árvore binária é uma árvore que
pode ser nula, ou então tem as seguintes características:
Existe um nó especial denominado raiz;
Nenhum nó tem grau superior a 2 (dois), isto é, nenhum nó
tem mais de dois filhos;
Existe um “senso de posição”, ou seja, distingue-se entre uma
subárvore esquerda e uma subárvore direita.
Árvores Binárias Atravessamento (ou caminhamento) de árvore é a passagem
de forma sistemática por cada um de seus nós;
Diferentes formas de percorrer os nós de uma árvore:
Pré-ordem ou prefixa (busca em profundidade)
Em ordem ou infixa (ordem central)
Pós-ordem ou posfixa
Em nível
Árvores Binárias Pré-ordem (prefixa)
visitar a raiz;
caminhar na subárvore à esquerda, segundo este caminhamento;
caminhar na subárvore à direita, segundo este caminhamento.
Árvores Binárias Atravessamento em ordem (infixa)
caminhar na subárvore à esquerda, segundo este caminhamento;
visitar a raiz;
caminhar na subárvore à direita, segundo este caminhamento.
Árvores Binárias Atravessamento pós-ordem (posfixa)
a) caminhar na subárvore à esquerda, segundo este
caminhamento;
b) caminhar na subárvore à direita, segundo este
caminhamento;
c) visitar a raiz.
Árvores Binárias Atravessamento em nível
Percorre-se a árvore de cima para baixo e da esquerda para a
direita.
Árvores Binárias Árvore Estritamente Binária:
É uma árvore binária na qual todo nó tem 0 ou 2 subárvores, ou
seja, nenhum nó tem “filho único”.
Árvores Binárias Árvore Binária Cheia
Todos os nós, exceto os do último nível, possuem exatamente
duas subárvores.
Uma árvore binária cheia de altura h tem 2h – 1 nós.
Árvores Binárias Árvore Degenerada
Cada nó possui exatamente um filho, e a árvore tem o mesmo
número de níveis que de nós
Árvore Binária de Busca Uma árvore é denominada árvore binária de busca se:
Todo elemento da subárvore esquerda é menor que o elemento
raiz;
Nenhum elemento da subárvore direita é menor que o
elemento raiz;
As subárvores direita e esquerda também são árvores de busca
binária.
Árvore Binária de Busca Busca
Se o valor for igual à raiz, o valor existe na árvore.
Se o valor for menor do que a raiz, então deve buscar-se na
subárvore da esquerda, e assim recursivamente, em todos os nós
da subárvore.
Se o valor for maior que a raiz, deve-se buscar na subárvore da
direita, até alcançar-se o nó folha da árvore, encontrando ou não
o valor requerido.
Árvore Binária de Busca Inserção
Se a árvore estiver vazia, cria um novo no e insere as
informações do novo nó.
Compara a chave a ser inserida com a chave do nó analisado:
o Se menor, insere a chave na subárvore esquerda;
o Se maior, insere a chave na subárvore direita.
Árvore Binária de Busca
Inserção
Exemplo:
Inserir os seguintes elementos: 7, 13, 20, 4, 1, 18, 5, 11 .
Árvore Binária de Busca Remoção
A remoção de um nó é um processo mais complexo. Para
excluir um nó de uma árvore binária de busca, há de se
considerar três casos distintos:
Remoção na folha
Remoção de um nó com um filho
Remoção de um nó com dois filhos
Árvore Binária de Busca Remoção na folha
A exclusão na folha é a mais simples, basta removê-lo da árvore.
Árvore Binária de Busca Remoção de um nó com um filho
Excluindo-o, o filho sobe para a posição do pai.
Árvore Binária de Busca Remoção de um nó com dois filhos
Neste caso, pode-se operar de duas maneiras diferentes:
1. Substitui-se o valor do nó a ser retirado pelo valor sucessor (o nó mais
à esquerda da subárvore direita);
2. Substitui-se o valor do nó a ser retirado pelo valor antecessor (o nó
mais à direita da subárvore esquerda)
Árvore Binária de Busca Remoção de um nó com dois filhos
Exemplo de remoção substituindo o nó pelo seu antecessor.
Árvore Binária de Busca Remoção de um nó com dois filhos
Exemplo de remoção substituindo o nó pelo seu sucessor.
