Introdução a ÁrvoresIntrodução a Árvores

Prof. Ernesto LindstaedtProf. Ernesto Lindstaedt

IntroduçãoIntrodução Estrutura de dados adequada para representar e manipular Estrutura de dados adequada para representar e manipular

informação hierárquicainformação hierárquica Exemplos de aplicaçãoExemplos de aplicação::

• Estrutura de diretórios (pastas) em um sistema de Estrutura de diretórios (pastas) em um sistema de arquivosarquivos

• Organograma de uma empresa/instituiçãoOrganograma de uma empresa/instituição• Expressão aritméticaExpressão aritmética• Estrutura de classes de uma API Estrutura de classes de uma API

DefiniçãoDefinição

Uma árvore T é um conjunto finito de elementos denominados nós Uma árvore T é um conjunto finito de elementos denominados nós ou vértices tais que:ou vértices tais que:

• TT = 0 é a árvore dita vazia ou = 0 é a árvore dita vazia ou

• Existe um nó Existe um nó rr, chamado raiz de , chamado raiz de TT; os nós restantes ; os nós restantes constituem um único conjunto vazio ou são divididos em constituem um único conjunto vazio ou são divididos em mm11 conjuntos distintos não vazios que são as sub- conjuntos distintos não vazios que são as sub-árvores de árvores de rr, cada sub-árvore a qual é, por sua vez, uma , cada sub-árvore a qual é, por sua vez, uma árvore.árvore.

Sub-árvores: definiçõesSub-árvores: definições Notação: Notação: SSe e vv é um nó de é um nó de TT,então a notação ,então a notação TTvv indica a sub-árvore indica a sub-árvore

de de TT com raiz em com raiz em vv

Seja a árvoreSeja a árvore TTAA = {A, B, ...} = {A, B, ...}

• A árvore TA árvore TAA possui duas sub-árvores: possui duas sub-árvores: TTbb e e TTcc onde onde TTbb = { = { BB } e } e TTcc = { = {C, DC, D, ...} , ...}

• A sub-árvore Tc possui 3 subárvores: A sub-árvore Tc possui 3 subárvores: TTd d , , TTf f e e TTee onde onde TTdd = {D, G, H} = {D, G, H} TTff = {F, I} Te = {E} = {F, I} Te = {E}

As sub-árvores As sub-árvores TTbb, , TTee, , TTgg, , TThh, , TTii possuem apenas o nó raiz e possuem apenas o nó raiz e nenhuma sub-árvore.nenhuma sub-árvore.

Outro exemploOutro exemplo::

Mais definições...Mais definições...Seja v o nó raiz da subárvore TSeja v o nó raiz da subárvore Tvv de T de T

Nós filhosNós filhos• os nós w1, w2, ... Wj, raízes das subárvores de Tv, são os nós w1, w2, ... Wj, raízes das subárvores de Tv, são

chamados filhos de v. chamados filhos de v. Pais, tios, irmãos e avôPais, tios, irmãos e avô

• O nó v é chamado pai de w1, w2, ... wj. Os nós w1, w2, ...wj O nó v é chamado pai de w1, w2, ... wj. Os nós w1, w2, ...wj são irmãos. Se z é filho de w1 então w2 é tio de z e v é avô são irmãos. Se z é filho de w1 então w2 é tio de z e v é avô de z. de z.

Nó descendente e ancestralNó descendente e ancestral• Se x pertence à subárvore Tv, então x é descendente de v e Se x pertence à subárvore Tv, então x é descendente de v e

v é ancestral, ou antecessor, de x. v é ancestral, ou antecessor, de x.

Exemplo:Exemplo:

Mais definições...Mais definições... Grau de saídaGrau de saída

• Grau de saída: número de filhos de um nó;Grau de saída: número de filhos de um nó; Nó folhaNó folha

• Nó que não possui descendentes, ou seja, um nó folha é Nó que não possui descendentes, ou seja, um nó folha é aquele com grau de saída nulo. aquele com grau de saída nulo.

Nó interior ou internoNó interior ou interno• Nó que não é folha (isto é, possui grau de saída diferente de Nó que não é folha (isto é, possui grau de saída diferente de

zero). zero). Grau de uma árvore Grau de uma árvore

• Valor máximo entre os graus de seus nós. Valor máximo entre os graus de seus nós.

Exemplo:Exemplo:

Mais definições...Mais definições... Floresta Floresta

• Conjunto de zero ou mais árvoresConjunto de zero ou mais árvores Caminho na árvoreCaminho na árvore

• Seqüência de nós distintos vSeqüência de nós distintos v11, v, v22, ..., v, ..., vkk, tal que existe , tal que existe sempre entre nós consecutivos (isto é, entre vsempre entre nós consecutivos (isto é, entre v11 e v e v22, entre v, entre v22 e ve v33, ... , v, ... , v(k-1)(k-1) e v e vkk) a relação "é filho de“ ou "é pai de" ) a relação "é filho de“ ou "é pai de"

Comprimento do caminho Comprimento do caminho

• Um caminho que passa por vUm caminho que passa por vkk vértices é obtido pela vértices é obtido pela seqüência de seqüência de k-1k-1 pares. O valor pares. O valor k-1k-1 é o comprimento do é o comprimento do

caminho.caminho.

Exemplo de floresta:Exemplo de floresta:

Exemplo de caminho:Exemplo de caminho:

Mais definições...Mais definições... Nível (ou profundidade) de um nó Nível (ou profundidade) de um nó

• O nível ou profundidade de um nó é o número de nós do O nível ou profundidade de um nó é o número de nós do caminho da raiz até o nó (caminho da raiz até o nó (raiz tem nível 1raiz tem nível 1))

Altura de um nó vAltura de um nó v• Número de nós no maior caminho de v até um de seus Número de nós no maior caminho de v até um de seus

descendentes (descendentes (folhas têm altura 1folhas têm altura 1) ) Altura de uma árvore T ou h(T)Altura de uma árvore T ou h(T)

• Máximo nível de seus nós (a altura da sub-árvore de raiz v é Máximo nível de seus nós (a altura da sub-árvore de raiz v é representada por h(v) ) representada por h(v) )

Exemplo de nExemplo de níveisíveis::

Caminhamento em Árvores - AmplitudeCaminhamento em Árvores - Amplitude Visitar cada nó começando no de menor nível e mover-se Visitar cada nó começando no de menor nível e mover-se

para os níveis mais altos, nível após nível, visitando cada para os níveis mais altos, nível após nível, visitando cada nó da esquerda para a direita:nó da esquerda para a direita:

• Breadth - First Search (BFS)

13

10 25

20 31

29

2 12

Fila: 13

Fila: 10, 25

Fila: 25, 2, 12

Fila: 2, 12, 20, 31

Fila: 12, 20, 31

Fila: 20, 31

Fila: 31

Fila: 29

Percurso: 13, 10, 25, 2, 12, 20, 31, 29

Caminhamento em Árvores - Caminhamento em Árvores - ProfundidadeProfundidade

O caminhamento em profundidade prossegue tanto quanto O caminhamento em profundidade prossegue tanto quanto possível à esquerda (ou direita), então se move para trás possível à esquerda (ou direita), então se move para trás até a primeira encruzilhada, vai um passo para a direita (ou até a primeira encruzilhada, vai um passo para a direita (ou esquerda) e novamente, tanto quanto possível, para a esquerda) e novamente, tanto quanto possível, para a esquerda (ou direita).esquerda (ou direita).

Percurso: 2, 12, 10, 20, 29, 31, 25, 13

• Deapth - First Search (DFS)

13

10 25

20 31

29

2 12

V – Visitar um nóL – Percorrer à esquerdaR – Percorrer à direita

VLR VRLLVR RVLLRV RLV