ALGORITMOS AVANÇADOS UNIDADE V - luizleao.comluizleao.com/Docencia/FAP/ALGAVANC/ALGORITMO_AVANC_UND_05.pdf · UNIDADE V - Estruturas de dados dos tipos Árvore Binária e Árvore

ALGORITMOS AVANÇADOS

Luiz Leão – [email protected] http://www.luizleao.com

UNIDADE V – Estruturas de dados dos tipos Árvore Binária e Árvore AVL

mailto:[email protected]

http://www.luizleao.com/

UNIDADE V - Estruturas de dados dos tipos Árvore Binária e Árvore AVL


Conteúdo Programático• 5.1 - Árvores, Árvores Binárias e Árvores Binárias de Busca

• 5.2 - Percorrendo uma Árvore Binária de Busca

• 5.3 - Implementando as Árvores Binária

• 5.4 - Percurso em Árvore

• 5.5 - Inserção

• 5.6 - Remoção

• 5.7 - Balanceando uma Árvore

• 5.7.1 - O Algoritmo DSW

• 5.7.2 - Árvores AVL



• É uma estrutura de dados formada por um conjunto finito de elementos ou nós.

• Uma árvore pode estar vazia ou pode ser formada por um nó chamado raiz e dois sub-conjuntos de elementos chamados sub-árvore esquerda e sub-árvore direita.

• As sub-árvores esquerda e direita são também árvores binárias e podem estar vazias.

Árvore Binária



Árvore Binária



Árvore Binária

• O nó raiz A tem duas sub-árvores B e C; • O nó B tem duas sub-árvores D e E; • O nó C tem apenas a sub-árvore da

direita F; • O nó E tem apenas a sub-árvore da

esquerda G; • O nó F tem duas sub-árvores H e I; • Os nós D, G, H e I não tem sub-árvores,

portanto, são chamados folhas.



Árvore Binária

• O nó raiz A tem duas sub-árvores B e C; • O nó B tem duas sub-árvores D e E; • O nó C tem apenas a sub-árvore da

direita F; • O nó E tem apenas a sub-árvore da

esquerda G; • O nó F tem duas sub-árvores H e I; • Os nós D, G, H e I não tem sub-árvores,

portanto, são chamados folhas.

Se A tem duas sub-árvores B e C, diz-se que:

• A é pai de B e C; • B é filho esquerdo de A; • C é filho direito de A. • B é irmão de C.



• Estritamente Binária

• Completa

• Quase Completa

Tipos de Árvores



• Cada nó (vértice) possui 0 ou 2 sub-árvores

• Nenhum nó tem “Filho Único”

• Nós internos (não folha) sempre têm 2 filhos

Árvore Estritamente Binária



Árvore Estritamente Binária



• É uma Árvore Estritamente Binária • Todos os seus nós-folha estão no mesmo nível • O número de nós de uma Árvore Binária Completa é:2h - 1

• Sendo h a altura da árvore

Árvore Completa



Árvore Completa



• A diferença de altura entre as sub-árvores de qualquer nó é no máximo 1

• Se a altura da árvore for D, cada nó folha está no nível “D” ou “D-1”

Árvore Quase Completa



Árvore Quase Completa



Exemplo de aplicação das árvores binárias• As árvores binárias são uma estrutura de dados útil quando

precisam ser tomadas decisões bi-direcionais em cada ponto do processo.

• Por exemplo, suponha que queiramos encontrar repetições em uma lista de números. Uma maneira de fazer isto é comparar cada número com todos os que o precedem. Entretanto, isto pode envolver muitas comparações.

• Outra maneira é utilizar uma árvore binária.



Exemplo de aplicação das árvores binárias• Suponha que temos a seguinte lista de números para verificar

repetições:

• 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5



Exemplo de aplicação das árvores binárias• Neste caso, iniciamos a árvore com o primeiro número da lista

como sendo o nó raiz.

• Na sequência, comparamos o próximo número com o número da raiz, se for igual é uma repetição.

• Se for menor, comparamos com a sub-árvore da esquerda.

• Se for maior, comparamos com a sub-árvore da direita.

• Se a sub-árvore estiver vazia, incluímos o número como filho desta sub-árvore, a esquerda ou direita, caso seja menor ou maior que o conteúdo do nó, respectivamente.



Exemplo de aplicação das árvores binárias



Percorrendo uma Árvore Binária de Busca• Uma operação importante em uma árvore binária é percorrer

todos os seus nós.

• Diferentemente de uma lista, na qual os nós são percorridos de maneira linear, numa árvore, existem diferentes ordens para poder percorrê-la.

• Todos os métodos para percorrer uma árvore são definidos recursivamente, de modo que percorrer uma árvore envolve visitar a raiz e depois a sub-árvore direita e a esquerda.

• O que difere cada método é a ordem em que estas operações são realizadas.



• Três métodos são conhecidos para percorrer uma árvore binária:

• Em ordem, ou esquerda-raiz-direita; • Pré-ordem ou percurso em profundidade ou raiz-esquerda-

direita; • Pós-ordem ou esquerda-direita-raiz.

Percorrendo uma Árvore Binária de Busca



• Percorre-se primeiro a sub-árvore esquerda, na ordem esquerda-raiz-direita, depois a raiz e depois a sub-árvore direita, também na ordem esquerda-raiz-direita.

Em Ordem



Em Ordem• Percorre-se primeiro a sub-árvore esquerda, na ordem

esquerda-raiz-direita, depois a raiz e depois a sub-árvore direita, também na ordem esquerda-raiz-direita.



• Percorre-se primeiro a raiz. Depois a sub-árvore esquerda, na ordem raiz-esquerda-direita. E depois a sub-árvore direita, também na ordem raiz-esquerda-direita:

Pré-Ordem



• Percorre-se primeiro a raiz. Depois a sub-árvore esquerda, na ordem raiz-esquerda-direita. E depois a sub-árvore direita, também na ordem raiz-esquerda-direita:

Pré-Ordem



• Percorre-se primeiro a sub-árvore esquerda, na ordem esquerda-direita-raiz. Depois a sub-árvore direita, também na ordem esquerda-direita-raiz. E depois a raiz.

Pós-Ordem



• Percorre-se primeiro a sub-árvore esquerda, na ordem esquerda-direita-raiz. Depois a sub-árvore direita, também na ordem esquerda-direita-raiz. E depois a raiz.

Pós-Ordem



• Vários algoritmos que trabalham com árvores trabalham em duas fases. Primeiro inserem elementos na árvore e depois percorrem a árvore.

• Veja um exemplo de classificação de números em ordem ascendente.

• A medida que os números forem sendo lidos os mesmos vão sendo inseridos na árvore.

Inserção de Elementos em Árvores Binárias



• Entretanto, ao contrário do algoritmo usado para achar repetições, aqui os números repetidos também são inseridos na árvore.

• Quando um novo número é comparado com a raiz da árvore, a sub-árvore esquerda é utilizada para inserir se o número for menor que o conteúdo do nó e a sub-árvore direita é usada se o número for maior ou igual ao conteúdo do nó.




• Para a lista de números:

• 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

• A árvore resultante será:







Remoção de nós de uma árvore• Numa árvore binária todos os elementos à esquerda do nó

raiz são menores que os elementos à direita, valendo o mesmo para cada sub-árvore.

• Assim, se um nó for removido, esta característica da árvore binária deve ser respeitada.

• Algumas regras para remover nós de uma árvore binária:



Remoção de nós de uma árvore



Regras de Remoção de nós de uma árvore• Se o nó é uma folha, isto é, não tem sub-árvores, o mesmo

pode ser removido sem problemas. Em seguida deve-se fazer o ponteiro de seu pai apontar para NULL.



Regras de Remoção de nós de uma árvore• Se o nó é uma folha, isto é, não tem sub-árvores, o mesmo

pode ser removido sem problemas. Em seguida deve-se fazer o ponteiro de seu pai apontar para NULL.

• Caso do nó G



Regras de Remoção de nós de uma árvore• Se o nó tem somente uma sub-árvore (direita ou esquerda),

podemos eliminar o nó "puxar" o nó filho para seu lugar.



Regras de Remoção de nós de uma árvore• Se o nó tem somente uma sub-árvore (direita ou esquerda),

podemos eliminar o nó "puxar" o nó filho para seu lugar.

• Caso do nó D



Regras de Remoção de nós de uma árvore• Se o nó tem as duas sub-árvores há duas possibilidades:

podemos "puxar" para seu lugar o maior elemento da sub-árvore esquerda ou o menor elemento da sub-árvore direita.



Regras de Remoção de nós de uma árvore• Caso do nó A da figura, podemos substitui-lo pelo maior

elemento da sub-árvore esquerda, no caso o nó E, ou pelo menor elemento da sub-árvore direita, no caso o nó F.



Exercício• Criar algoritmo de indexação de dados, utilizando árvore

binária, onde o No armazena a além do índice para comparação, um atributo de valor. Baseado nisso, desenvolva:a) Criar estrutura de alimentação através da lista de índices 5,1,3,8,10 e de valores A, B, C, D e E.b) Implemente as funções Pre-Ordem e Pos-Ordem de leitura

Árvore AVL



• Criada pelos soviéticos Adelson Velsky e Landis em 1962, na publicação "Algoritmos para organização da informação" de 1962.

• Uma árvore é considerada AVL se, e somente se, para cada um de seus nós, as alturas das sub-árvores à direita e à esquerda forem iguais, ou difiram em apenas uma unidade.

Equilíbrio



• if ((Hd – He) < 2) { É AVL }

Uma Árvore AVL



• if ((Hd – He) >= 2) { NÃO É AVL }

Uma Árvore Não AVL



• Foi a primeira estrutura de dados a oferecer operações de inserção, remoção e busca em tempo logaritmo, ou seja, é um algoritmo muito rápido.

• Em uma árvore desbalanceada de 10.000 nós, são necessárias 5.000 comparações para efetuar uma busca, já numa árvore AVL, com o mesmo número de nós, essa média baixa para 14 comparações.

• Devemos sempre tentar manter o custo de acesso o menor possível, e o algoritmo da árvore AVL busca exatamente isso, deixando a árvore sempre com a menor altura possível.

Por que usar esta Estrutura?



• Para cada nó, defini-se um fator de balanceamento (FatBal), que deve ser -1, 0 ou 1. Ele é o responsável por avisar que a árvore está desbalanceada.

• FatBal = altura (sub-árvore direita) – altura (sub-árvore esquerda)

• FatBal = -1, quando a sub-árvore da esquerda é um nível mais alto que a direita.

• FatBal = 0, quando as duas sub-árvores tem a mesma altura.

• FatBal = 1, quando a sub-árvore da direita é um nível mais alto que a esquerda.

Fator de Balanceamento

! Toda folha tem FB = 0



• Quando inserimos um novo registro na árvore, ou removemos um registro já existente.

• Esta inserção/remoção pode ou não alterar as propriedades de balanceamento.

• Caso a inserção/remoção desse novo registro não viole nenhuma propriedade de balanceamento, podemos continuar inserindo/removendo registros.

• Se a inserção/remoção afetar as propriedades de balanceamento, devemos restaurar o balanço da árvore. Esta restauração é efetuada através de Rotações na árvore.

Quando é usado o FatBal?



• Rotação simples à esquerda

Rotações



• Rotação simples à direita

Rotações



• Rotação dupla à esquerda

Rotações

(rotação simples à direita + rotação simples à esquerda)



• Rotação dupla à direita

Rotações

(rotação simples à esquerda + rotação simples à direita)



• Dicasa) Para identificar quando uma rotação é simples ou dupla deve-se observar os sinais do FB: - Se o sinal for igual, a rotação é simples - Se o sinal for diferente, a rotação é duplab) Se FB for positivo (+), a rotação é para à esquerdac) Se FB for negativo (-), a rotação é para à direita

Rotações



• Suponha que inserimos os números 50, 40 e 30 em uma árvore. Obteremos então:

Rotação Simples

! A inserção produziu um desbalanceamento.

! Neste caso, como os sinais dos FB são os mesmos, significa que precisamos fazer apenas uma ROTAÇÃO SIMPLES à direita no nó com FB -2.

! No caso simétrico (nó com FB 2) faríamos uma rotação simples à esquerda.



• Após a rotação simples teremos:

• Agora a árvore está balanceada.

Rotação Simples



• Como podemos observar, a árvore está balanceada pelos FB de cada nó.

• São dois os possíveis casos de desbalanceamento.

Considere a árvore abaixo:



• Ao inserir o número 5 na árvore, teremos a seguinte árvore:

Rotação Dupla

! O nó 8 fica com o FB -2 e tem um filho com FB +1. Neste caso para manter o balanceamento devemos aplicar duas rotações, também denominada ROTAÇÃO DUPLA.

! Primeiro rotaciona-se o nó com FB 1 para a esquerda.



! Logo rotaciona-se o nó que possuía FB -2 na direção oposta, nesse caso a direita.

Rotação Dupla



! Os FB dos nós voltaram a ficar dentro do esperado das árvores AVL.

! O caso simétrico ao explicado acima acontece com os sinais de FB trocados, ou seja, um nó com FB +2 com um filho com FB -1. Também utilizaríamos uma rotação dupla, mas nos sentidos contrários, ou seja, o nó com FB -1 seria rotacionado para a direita e o nó com FB +2 seria rotacionado para a esquerda.

Rotação Dupla

Documents

ALGORITMOS AVANÇADOS UNIDADE V - luizleao.comluizleao.com/Docencia/FAP/ALGAVANC/ALGORITMO_AVANC_UND_05.pdf · UNIDADE V - Estruturas de dados dos tipos Árvore Binária e Árvore