Aula prática 08: árvores, relações e representações

Explicação

Um nó, também chamado nodo ou vértice, é um elemento da árvore que armazena dados. Uma aresta conecta dois nós e, nesta hierarquia, representa uma relação pai-filho. O conteúdo armazenado não determina a identidade do nó: elementos distintos podem conter o mesmo dado.

Objetivo de aprendizagem: distinguir os elementos da árvore, seus conteúdos e suas conexões, sem confundir igualdade de dados com identidade dos nós.

Resposta esperada

Nó: elemento da árvore. Dado: conteúdo armazenado no nó. Aresta: conexão entre dois nós. Sim, dois nós podem armazenar dados iguais, pois a igualdade do conteúdo não transforma elementos distintos em um único nó.

Explicação

E precisa ter o mesmo pai de D, portanto também é filho de A. Como F é pai de G e B é avô de G, B precisa ser pai de F. As relações determinam as sete ligações e conectam todos os oito nós à raiz R. Subir de G percorre F, B e R.

Objetivo de aprendizagem: reconstruir uma hierarquia por parentescos diretos e indiretos, identificando raiz, folhas e ancestrais.

Resposta esperada

flowchart TD
    r["R"] --> a["A"]
    r --> b["B"]
    r --> c["C: folha"]
    a --> d["D: folha"]
    a --> e["E: folha"]
    b --> f["F"]
    f --> g["G: folha"]

Folhas: C, D, E e G. Ancestrais de G, do mais próximo ao mais distante: F, B e R. Todos os nós diferentes de R possuem um único pai, e nenhuma ligação forma ciclo.

Explicação

Contamos somente os filhos, sem somar a ligação com o pai. Q tem três filhos e estabelece o maior grau. O limite ternário não exige que todos os nós tenham três filhos. Já o limite binário seria ultrapassado por Q.

Objetivo de aprendizagem: medir a ramificação de nós e da árvore para verificar um limite de filhos por nó.

Resposta esperada

Graus: P = 2, Q = 3, R = 0, S = 0, T = 0 e U = 0. Grau da árvore: 3. Ela respeita o limite ternário porque nenhum nó possui mais de três filhos. Não respeita o limite binário, pois Q possui três filhos.

Explicação

R recebe uma ligação de S, embora seja a raiz proposta. S recebe ligações de P e Q, portanto possui dois pais. Há ciclos como R → P → S → R. Remover S → R elimina o retorno à raiz, mas ainda precisamos retirar uma das duas ligações que chegam a S.

Objetivo de aprendizagem: corrigir uma hierarquia verificando conjuntamente ausência de ciclos, raiz sem pai, pai único e conexão de todos os nós.

Resposta esperada

Violações: R tem pai, S tem dois pais e existem caminhos fechados, como R → P → S → R.

Uma correção: remover S → R e Q → S. Restam R → P, R → Q e P → S. R fica sem pai, os outros nós têm um pai cada, todos são alcançáveis a partir de R e não há ciclos. Também é válida a remoção de S → R e P → S.

Explicação

Para chegar a G, precisamos passar por seu pai E, cujo pai é C. Há quatro nós na sequência correta, mas apenas três ligações. O caminho começa na raiz A e termina em G, que não possui filhos.

Objetivo de aprendizagem: reconstruir um caminho, medir seu comprimento em arestas e reconhecer um ramo completo pelos seus extremos.

Resposta esperada

Caminho: A → C → E → G. Comprimento: 3 arestas. É um ramo completo, pois começa na raiz A e termina na folha G.

Explicação

Partir de C e acompanhar todos os filhos inclui D, E, F e G. A está acima de C e B pertence a outro ramo. Nenhum dos dois é descendente de C.

Objetivo de aprendizagem: extrair uma subárvore sem remover descendentes obrigatórios nem incluir ancestrais ou ramos externos.

Resposta esperada

flowchart TD
    c["C"] --> d["D"]
    c --> e["E"]
    d --> f["F"]
    e --> g["G"]

A subárvore contém C, D, E, F e G. Ficam fora A e B.

Explicação

Cada descida acrescenta um nível e uma aresta percorrida. P está três arestas abaixo de K e ocupa o nível 4, porque a contagem de níveis começou em 1. A altura de L conta no sentido oposto: de L até sua folha mais distante, N, há uma aresta.

Objetivo de aprendizagem: distinguir nível, altura e profundidade pelo ponto de referência, pelo sentido do caminho e pela unidade de contagem.

Resposta esperada

Níveis: K = 1, L = 2, M = 2, N = 3, O = 3 e P = 4. Altura da árvore pela aula: 4 níveis. Altura de L: 1 aresta. Profundidade de P: 3 arestas.

Explicação

Cada filho direto de R inicia uma árvore independente quando a ligação com R desaparece. Remover R não remove os descendentes dos filhos. C permanece como árvore de um único nó.

Objetivo de aprendizagem: reconhecer os componentes de uma floresta e separar remoção de um nó de remoção de sua subárvore inteira.

Resposta esperada

flowchart TD
    a["A"] --> d["D"]
    b["B"] --> e["E"]
    e --> f["F"]
    c["C"]

Permanecem 3 árvores, com raízes A, B e C.

Explicação

R continua sendo pai de P e Q, e Q continua sendo pai de S. A mudança está somente nas posições de P e Q. O termo orientada está sendo usado conforme a aula, para comparação sem ordem dos irmãos. Ele não serve aqui para classificar a presença de setas no desenho.

Objetivo de aprendizagem: separar ordem de apresentação e relação pai-filho ao comparar duas árvores.

Resposta esperada

• Como árvores ordenadas: são diferentes, porque X tem filhos de R na ordem P, Q e Y na ordem Q, P.
• Como árvores orientadas no sentido da aula: são iguais, porque todas as relações pai-filho foram preservadas.

Explicação

Dentro do par externo está H. Seus dois grupos imediatos começam em J e K. L pertence ao grupo de J, enquanto M e N pertencem ao grupo de K. Estar dentro do grupo de H não torna todos esses nós filhos diretos de H.

Objetivo de aprendizagem: recuperar parentescos diretos a partir de grupos aninhados, distinguindo filhos de descendentes mais distantes.

Resposta esperada

flowchart TD
    h["H"] -->|1| j["J"]
    h -->|2| k["K"]
    j -->|1| l["L"]
    k -->|1| m["M"]
    k -->|2| n["N"]

Explicação

R possui dois filhos diretos, então sua linha tem dois valores 1. C é descendente de R, mas não seu filho: a célula da linha R e coluna C recebe 0. Não espelhamos os valores para representar filho → pai, pois a convenção desta matriz é direcional.

Objetivo de aprendizagem: codificar somente a adjacência direta, preservando o sentido pai-filho e a ordem dos índices.

Resposta esperada

As linhas identificam os pais e as colunas identificam os filhos.

Explicação

A matriz possui $6\times6=36$ células. Como cada célula ocupa 1 byte, ela reserva 36 bytes. Há dois valores 1 na linha de R, dois na de A e um na de B. Assim, cinco células registram ligações e as outras $36-5=31$ contêm 0.

Esses 31 bytes também estão ocupados pela matriz. O valor 0 informa que não existe aquela ligação, mas não libera a memória da célula. Para uma árvore não vazia com $N$ nós, a matriz reserva $N^2$ células, mas existem somente $N-1$ ligações pai-filho: cada nó, exceto a raiz, possui exatamente um pai. Por isso, a proporção de células sem ligação aumenta com o total de nós.

O limite de filhos permitido por nó, $n$, não é o total de nós, $N$. Uma árvore binária tem $n=2$ e pode ter milhares de nós. A escolha da representação precisa distinguir essas duas quantidades.

Quando $n$ é grande: uma lista encadeada de filhos por nó evita reservar muitas posições vazias. Cada elemento referencia um filho existente e o próximo elemento. Folhas têm listas vazias. No conjunto, há $N$ referências de início de lista e $N-1$ elementos para as ligações. O armazenamento cresce proporcionalmente ao total de nós, enquanto a matriz cresce com seu quadrado. Essa é a vantagem para árvores grandes, mesmo considerando as referências de encadeamento.

Quando $n$ é pequeno e fixo: um vetor de $n$ índices de filhos por nó pode ser mais adequado. Ele reserva $N\times n$ posições, não $N^2$, e dispensa a referência ao próximo elemento que cada célula de lista precisaria guardar. Ainda há posições vazias, mas sua quantidade por nó fica limitada ao pequeno valor de $n$. Essa é a alternativa trabalhada no exercício 13. A comparação exata em bytes depende do tamanho dos campos de cada representação.

Objetivo de aprendizagem: quantificar o espaço reservado e perceber por que uma matriz pode conter muitas posições sem ligação registrada.

Resposta esperada

1. 36 células e 36 bytes, pois $6\times6=36$.
2. 31 células com 0, ocupando 31 bytes. Esses bytes não estão livres: continuam reservados para registrar a ausência de ligações na matriz.
3. Limite grande: listas encadeadas de filhos guardam somente os filhos existentes, evitando reservar muitas posições vazias por nó. Limite pequeno e fixo: um vetor de $n$ índices por nó reserva poucas posições e dispensa as referências de encadeamento. A matriz reserva $N^2$ células. As listas usam $N$ referências de início e $N-1$ elementos, e os vetores reservam $N\times n$ posições. Aqui, $N$ é o total de nós e $n$ é o limite de filhos por nó.

Explicação

A linha de L armazena os índices de M, N e O. M e N usam uma posição cada, e as folhas não usam nenhuma. O valor −1 distingue posição livre de uma referência válida ao nó de índice 0.

Objetivo de aprendizagem: representar filhos por índices e preencher posições livres sem confundir índice com marca de adjacência.

Resposta esperada

Cada linha informa o nó e as três posições reservadas para filhos.

Explicação

O lugar disponível para H resolve o armazenamento do registro, mas não cria uma terceira posição na linha de E. Colocar H na linha de F mudaria seu pai e não atenderia ao pedido. O limite de filhos precisa acompanhar o maior grau permitido.

Objetivo de aprendizagem: distinguir capacidade total de nós de capacidade local de filhos para diagnosticar uma limitação da representação.

Resposta esperada

Não cabe na tabela atual. E passaria a ter grau 3, mas sua linha comporta apenas dois filhos. São necessárias pelo menos 3 posições por linha nessa representação uniforme.

Explicação

A subárvore movida contém D e E. B precisa deixar de apontar para D, C precisa passar a apontar para D e o pai registrado em D precisa mudar. O campo liberado em B recebe NULL. Alterar somente os filhos deixaria parent de D inconsistente. As referências de pai são dados auxiliares: não acrescentam novas relações de filho à hierarquia.

Objetivo de aprendizagem: representar uma mudança de hierarquia com ponteiros diretos, mantendo coerência entre pai, filhos e referências nulas.

Resposta esperada

flowchart TD
    a["A"] --> b["B"]
    a --> c["C"]
    c --> d["D"]
    d --> e["E"]

• B: child_1 passa de D para NULL.
• C: child_1 passa de NULL para D.
• D: parent passa de B para C.

root continua apontando para A. child_1 de D continua apontando para E, e parent de E continua apontando para D. Os demais campos permanecem iguais.

Explicação

A representação A mostra os parentescos. A representação B mostra os registros e as listas que codificam esses parentescos. Na lista de U, a seta próximo encadeia dois elementos: um referencia V e outro referencia W. Essa ligação organiza a lista, enquanto a presença das duas referências na lista de U indica que V e W são filhos de U.

Mudar a ordem dos registros, preservando as referências aos mesmos nós, não altera nenhum parentesco. X e Y continuam registrados, mas suas listas de filhos estão vazias. Por isso, suas referências de início recebem NULL.

Objetivo de aprendizagem: separar a organização dos registros da organização hierárquica codificada pelas listas de filhos.

Resposta esperada

1. Não. A seta próximo conecta elementos da lista de filhos de U. V e W são filhos de U, como mostra a representação A.
2. Não. A ordem dos registros não determina os parentescos. Mantidas as referências aos mesmos nós, U continua sendo pai de V e W, V de X e W de Y.
3. X e Y são folhas. Seus registros existem na coleção principal, mas suas listas de filhos estão vazias. NULL indica ausência de filhos, não ausência desses nós na árvore.

Explicação

X reserva $6\times3=18$ campos, dos quais cinco referenciam filhos e treze são nulos. Y reserva seis inícios de lista e cinco células com dois campos cada: $6+5\times2=16$. A lista evita posições fixas para filhos inexistentes, mas também precisa guardar seu próprio encadeamento.

Objetivo de aprendizagem: comparar armazenamento pelo modelo completo de referências, incluindo o custo necessário para organizar listas de filhos.

Resposta esperada

X: 18 campos de referência. Y: 16 campos de referência. Contar apenas as cinco relações pai-filho não basta para medir Y: também há seis referências de início e cinco de próxima célula. Neste modelo simplificado, Y usa dois campos a menos. Isso não prova economia em toda implementação, pois o custo do alocador e outros dados foram excluídos.

Explicação

Nas pastas, as relações descrevem contenção. Na pesquisa em inteligência artificial, representam alternativas para procurar um resultado. No compilador, descrevem a estrutura da expressão. Uma árvore pode apoiar mais de uma finalidade, mas a questão pede a finalidade principal de cada descrição.

Objetivo de aprendizagem: relacionar os modelos de árvore às aplicações citadas sem atribuir propriedades ou algoritmos que a aula não ensinou.

Resposta esperada

• Pastas de um sistema operacional: organização hierárquica.
• Árvore de pesquisa em inteligência artificial: busca.
• Compilador: representação de expressão para análise sintática.

Explicação

A divisão reúne o numerador inteiro e o denominador inteiro, por isso é a raiz. O numerador é uma multiplicação cujos operandos são duas expressões. No denominador, a soma reúne t e u. Trocar os operandos da subtração ou da divisão alteraria a expressão.

Objetivo de aprendizagem: modelar a estrutura de uma expressão preservando agrupamento e ordem dos operandos.

Resposta esperada

flowchart TD
    divide["/"] -->|esquerdo| multiply["*"]
    divide -->|direito| denominator["+"]
    multiply -->|esquerdo| subtract["-"]
    multiply -->|direito| add["+"]
    subtract -->|esquerdo| p["p"]
    subtract -->|direito| q["q"]
    add -->|esquerdo| r["r"]
    add -->|direito| s["s"]
    denominator -->|esquerdo| t["t"]
    denominator -->|direito| u["u"]

Explicação

A raiz divide os resultados das duas subárvores. Primeiro obtemos o valor da soma e o da subtração. O denominador é 4, portanto a divisão está definida. Não basta ler os rótulos da esquerda para a direita sem considerar o agrupamento.

Objetivo de aprendizagem: recuperar e calcular uma expressão a partir da hierarquia de seus operadores e operandos.

Resposta esperada

Expressão: $(a+b)/(c-d)$. Soma: $3+5=8$. Subtração: $10-6=4$. Resultado final: $8/4=2$.