Árvores em Computação: estruturas, representações e algoritmos de percurso

Texto original

O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.

Texto extraído do video Fundamentos Matemáticos para Computação - Árvores e suas representações

Olá, alunas e alunas no Procudo Fundamentos Matemáticos para a Computação.
Nesta videoaulo eu vou falar de árvores e suas representações.
Vou começar com as terminologias, depois de escrever a representação computacional para a árvores apresentar alguns algoritmos de percurso e, em seguida, resultaram os matemáticos.
Bom, árvore, ela é um gravo que não tem ciclo e completamente conectado.
Então você não vai identificar dos conexões, você não vai ter ciclos dentro de uma estrutura em árvores.
E ela tem sempre, você consegue identificar um nome especial chamado raiz.
O raiz de uma estrutura bastante interessante, que, por exemplo, representa de uma forma muito trivial uma expressão como essa.
Essa expressão nós temos com mais, quando o operador principal, que seria, então, a raiz, em seguida o primeiro termo, que é o 3 vezes a, e o segundo termo que é composto por uma subtração com o primeiro termo sendo a soma bem, mas sempre, o segundo termo é a divisão quátil por a.
Então você vê que essa expressão fica bem representada aqui através dessa estrutura ramificada.
Além disso, sistemas operacionais utilizam essa estrutura em árvore para organizar diretores.
Então, nós temos um diretório raiz e os diretores filhos.
Além disso, nessas ramificações, nós podemos identificar diretores pais que também vão ser, vão ter filhos relacionados a eles.
A partir do momento que temos essa constante ramificação das árvores, nós podemos identificar então sua profundidade.
Um ar que tem uma abre que tem apenas a raiz é dita com profundidade zero.
Se ramificamos, passa a ter profundidade 1, e se continuamos a ramificávamos ter profundidade 2 por profundidade 3 e profundidade 4.
Se quisermos descobrir a altura de uma árvore, nós contamos a quantidade de arcos que nos leva até o seu a sua profundidade máxima.
Então nesse caso, a árvore, para a apresentação, é doutura 4.
Além disso, os nós que não namificam, eles são chamados nós folhas ou terminais.
Enquanto os demais nós são chamados nós internos a árvore.
A árvore, então, ela é uma estrutura conéxa e a cíclica.
Aqui nós temos uma árvore, outra árvore que, em conjunto, essa estrutura é o que se chama uma floresta.
Ela é composta, então, por três árvores.
Uma árvore binária é uma árvore que ramifica, no mais, no máximo, dois filhos.
Agora, vamos poder identificar nesse caso um filho à esquerda e um filho à direita.
Observem aqui que esse filho à esquerda ramificou, certo? Enquanto esse filho à direita, ramificou, inicialmente, só para um filho à direita também e depois já me ficou para um filho à esquerda e outra direita.
Uma árvore binária, ela vai ser considerada cheia, quando até a sua profundidade máxima, você tem todas as ramificações possíveis.
Então ela está cheia.
Uma árvore binária completa, ela vai estar ramificada até a sua sua sua máxima, porém, no último nível, você pode não ter esse último nível cheio.
Então, da esquerda para a direita, você pode ter as ramificações, mas essas ramificações não completam esse, podem não necessariamente completar esse último nível da árvore.
Então, nesse caso, nós temos uma árvore binária completa, mas que não é cheia.
Temos de representação computacional.
Aquelas representações, considerando uma frigide de gestência e listos que nós vimos gravo, podem ser utilizadas para árvores, porém, podemos tirar vantagem nesse processo de representação de árvore, considerando principalmente, no caso de árvore binária, os filhos à esquerda e à direita.
Então, por exemplo, uma representação em tabela para uma árvore binária, com a ilustrada que nos permite identificar, considerando cada linha, um nó da árvore, e cada colôna, o filho à esquerda e o filho à direita, nós temos aqui que, por não, nós vamos ter o 2, como filho à esquerda e o 3, como filho à direita.
No no 2, nós vamos ter o 4, como filho à esquerda e o 5, como filho à direita.
No no 3, nós não vamos ter filho à esquerda e vamos ter 6, como filho à direita.
Enquanto, no 4, 5, 6 ficam bem caracterizados aqui, como no folha, já que não tem filho à esquerda e à direita.
Não, rompificam.
Quando pensamos em uma lista de adjacência para fazer esse tipo de representação, então, nós temos que ter em mente a necessidade de apontar o filho à esquerda e o filho à direita.
Então, nesse caso, nós temos o 9 apontando para o 2, que para o 3, que, por sua vez, nós temos o 2 aponta para o 9, 4 e o 5 aponta à esquerda para o 9, 4 à direita para o 5.
E o 9, 3 tem um apontamento apenas à esquerda para o 6.
No estrutura em árbaro, uma vez que você consegue modelar um problema usando uma árbaro e você consegue representar esse problema através de uma estrutura de darado, seja ela ou uma tabela, seja ela ou uma lista, você agora consegue executar o gorítimo para obter informações de que estão armazenadas nessa árbaro.
E para isso, temos os algoritmos de percussos onde mais comuns são, preorden, ordem simétrica e pós-ordem.
Para ter uma ideia de como funciona esses algoritmos de percussos, vamos, em carada, a seguinte maneira abre, ela tem ramificações.
Então nós vamos olhar sempre para um 9 e depois vamos explorar as ramificações desse 9.
Que no caso de um árbaro binária como essa, pode estar à esquerda ou à direita do 9 considerado naquele momento pelo algoritmo de percurso.
A partir do momento que decidimos um rano a ser explorada, suponha o rano aqui a esquerda.
Identificamos um 9, avaliamos esses 9 processanos, a informação desse 9, e em seguida podemos avaliar a ramificação à esquerda e a direita.
Então a gente sempre vai tendo essa visão por ramos nesses algoritmos.
E é isso que a gente vai ver agora com o algoritmo de preorden.
No caso do algoritmo de preorden, o que acontece? Uma vez que você receba um morraís de um rano dessa árbaro, ele vai ser processado, aquele 9, se considerado como um 9 raiz, em relação ao rano que está sendo avaliado.
E aí o que acontece nesse caso? Primeira coisa é escrever esse 9.
Então você identificou um 9 raiz original da minha árbaro 1.
Vou escrever.
Agora eu vou avaliar o rano à esquerda dele, nesse caso 2.
Por que que vai acontecer? Eu entro agora com 2 como sendo meu 9 raiz aqui.
Então eu vou escrever.
E vou a esquerda dele.
Observe que daqui, quando eu partir para a esquerda do 9, eu deixei um suspenso à execução da parte à direita.
Então eu fui a esquerda do 2.
E formei esse rano com 2 como raiz, escrevo 2.
E agora eu vou a esquerda do 2, deixando com o suspenso à execução à direita para quando finalizar a execução à esquerda.
Bom, uma vez a esquerda eu tenho esse termo como 9 raiz.
E aí eu vou escrever o 4.
E vou a esquerda do 4, que não tem nada.
E a direita do 4 não vai ter nada.
Então agora eu vou a esquerda do 2, que é o que estava à direita do 2, que é o que estava em suspenso, porque eu já fiz a exploração à esquerda.
Então eu vou a direita do 2.
Nesse caso eu tenho o nosso passo, o nosso 5.
Vou escrever o nosso 5.
Vou olhar a esquerda do nosso 5.
Não tem nada, a direita do nosso 5 não tem nada.
Volta agora para cá, já explorei a direita do nosso 5.
E qual era o código do 2? Qual era o código que estava em suspenso? Bom, estava guardando a execução o no, a direita do 1.
E aí o que que eu vou fazer? Recebo esse rango.
Nesse caso, printo o no 3 e vou a esquerda do no 3.
Printo o no 6, explora a esquerda do no 6.
Não tem nada, a direita do no 6 não vai ter nada.
A direita do no 3 não vai ter nada.
E com isso, quando eu estava executando a direita do no 1, eu termino o meu código.
Então na pré-ordem, a gente pensa raiz, a esquerda e a direita.
Para executar esse percurso.
Essa seria então a listagem de print, que ocorre considerando esse algoritmo que, como vocês perceberem aqui, trata-se de um algoritmo recorcivo.
Na pré-ordem, tem também uma adaptação dessa abordagem recorciva da seguinte forma.
Nós vamos avaliar a esquerda, a direita, e depois a raiz.
Então, como isso é feito? Eu começo de cena.
Eu vou simplesmente descendo a esquerda, a esquerda, porque eu vejo que está primeiro essa recorcividade aqui.
Esquerda, esquerda, esquerda.
Aí o que vai acontecer? Quando eu estou, vou a esquerda desse no, eu caio em Nulo.
Aí, eu vou a direita desse no, caio em Nulo.
Uma vez que eu já executei a direita, o meu próximo passo, então escreveu no, que eu estou.
4.
A sua isso pela primeira vez.
Agora, o que que eu faço? Eu estou, eu já executei a esquerda do 2.
Então, agora, eu vou para a direita do 2.
Quando eu chego a direita do 2, eu vou entrar aqui de novo, vou a esquerda do 5, que seria Nulo, a direita do 5, Nulo.
Então, eu imprimo agora o 5, e imprimo agora o 2, porque eu já vou escolher a esquerda e a direita do 2.
Agora, a mesma coisa, eu vou para a direita do 1, que estava em suspens, certo? E aí, nesse caso, o que eu vou fazer? Eu vou descer a esquerda até o último nível, vou olhar a esquerda do 6, a direita do 6, não tem nada, pinto 6.
Aí, eu volto aqui para o 3, porque, já vou escolher aqui, já prentei o 6, a direita do 3, não vai ter nada, vou brinhar o 3.
E agora, como eu já terminei de vasculiais, que é a direita do 1, eu printo 1.
E tenho essa sequência de resultados.
Então, novamente, na voz ordem, esquerda direita, raiz.
Quando eu penso na ordem cinétrica, o que vai acontecer? Eu vou a esquerda raiz e direita.
É uma esquerda raiz e direita.
De que forma? Bom, nós vamos começar entrando lembre-se que tem um código recorcivo, eu vou começar caindo sempre a esquerda.
Então, isso vai fazer com que eu desça aqui até o 4.
Certo? Vai ser da hora que eu vou descer a esquerda do 4.
Vai estar nulo.
O que vai acontecer? Eu acho que é da duro 4, nulo.
Eu termino de executar.
Então, vou encerrar execução, porque deu nulo.
E aí, o que eu faço? O próximo passo é ir primir.
4.
Beleza.
Agora, que eu janei primir o 4, o que eu vou fazer? Eu vou direita do 4.
Que, nesse caso, não tem nada.
Então, beleza? Eu vou funcionar.
Vou agora, por código, o que estava no suspenso, que era.
.
.
imprimir o que estava esperando a execução do a esquerda do 2.
Uma vez encerrada a execução da esquerda do 2, eu escrevo esse 2.
E agora, eu desço a direita do 2.
Quando eu desço a direita do 2, eu vou a esquerda do 2, é nulo.
Quando eu desço a direita do 2, eu vou para o número 5, a esquerda do 5 é nulo.
E aí, quando eu retorno a nulo aqui, eu vou imprimir agora o 5.
Vou a direita do 5 é nulo, então, não vou fazer nada.
E aí, eu volto agora para imprimir o que estava esperando depois que eu vasculhar essa esquerda do 1, que é imprimir 1.
Agora, eu vou para a direita do 1.
E aí, a mesma coisa, uma vez a direita do 1, eu retorno para cá e começo a cair a esquerda.
Cair a esquerda do 6, não vai ter nada.
Pinto 6, a direita do 6, não vai ter nada.
Aí, eu trinto 1, 3, porque eu já percorri a esquerda dele.
A direita do 3, não vai ter nada.
E aí, eu termino a minha execução.
Nesse caso, a lista deande de valores seria 4, 2, 5, 1, 6, e 3.
O algoritmo de ordem seméptrica, ele é utilizado quando estamos trabalhando com uma notação para a operação de matemáticas do tipo notação em fixa.
Onde, aí, nós precisamos de deixar claro os parentes para determinar a ordem de precedência, porque podemos interpretar desse jeito ou desse que o resultado do percurso.
Já no algoritmo de pre-ordem, nós temos a chamada notação polonisa, que aquela em que as operações vem antes dos termos.
O interessante aqui é que não deixa dúvida.
Se a gente executa o algoritmo de pre-ordem, aqui nós vamos evitar esse resultado, a notação polonisa.
E o bom disso é que a questão dos parentes já fica em pristo.
Por quê? Vamos ver aqui.
Quando eu vou executar as operações, olhando mais internamente, eu tenho a primeira operação binária se aplicada, é uma mais aqui que vai atuar, então, os dois termos de sucede, em 2x.
Então, eu vou somar 2x.
Então, eu já tenho aqui que a ordem de precedência é essa operação.
vezes o 4.
Então, agora, para a operação de produto, eu tenho o primeiro termo do produto, é o 2x e o segundo termo 4.
Na poisor de nós obtemos a chamada notação polonisa, inessa, ou seja, os operadores aparecem depois.
Então, o que acontece nesse caso? A mesma coisa, quando eu executo a poisor de aqui, eu vou obter esse tipo de resultado no algoritmo de impós ordem sobre essa árvore.
E aí, para eu verificar isso, interpretar isso, interrompendo de notação polonisa, emversa, o que acontece? Eu penso assim, eu tenho aqui a operação de mais que vai atuar sobre esses dois operadores.
Então, 2x.
Eu soubesse os dois termos, 2x.
Depois, o produto que vai atuar sobre esses dois termos, 4 e 2x, obtendo a operação, a representação adequada, correta, porque o que está armazenado na árvore.
Bom, alguns resultados matemáticos interessantes considerando árvores.
O primeiro é que uma árvore como NN tem N-1 arcos.
Vamos verificar isso por indução.
Então, se o supo passo base para N-1, onde vamos ter zero arcos, beleza? Aí, eu suponho por indução que eu vou ter para N igual a cá, nós caminamos um arcos.
Então, vamos agora provar para N igual a cá mais 1 arcos.
Como fica isso? Bom, se eu tenho por indução, a hipótese de que para N igual a cá, nós, nós temos caminos 1 arcos, eu posso considerar uma árvore com cá mais 1 nós, e vamos pensar na estrutura da árvore.
A árvore tem uma folha, já que ela vai ter um número limitado de nós, ela vai ter nós folhas.
Então, eu posso, perfeitamente, bem, escolher 1 no folha e o arco que o ligar a árvore e remover da árvore.
Então, eu faria algo desse tipo que tirei 1 no folha e o seu respectivo arco.
Ao remover 1 no folha, não criamos desconexar o por isso que eu escolhi 1 no folha para fazer essa remoção.
Então, eu continuo tendo uma árvore com menos 1 novo e menos 1 arco.
Só que, como eu tenho? Eu estava trabalhando no arvore com cá mais 1 nós.
Agora, eu tenho uma árvore com cá novo, o que, por hipótese de indução, diz que eu vou ter caminos 1 arcos.
Perfeito.
Agora, ao voltarmos 1 arco e 1 novo, novamente, como o novo é.
.
.
A folha dessa árvore, o que vai acontecer? Eu vou ter cá mais 1 nós e cá menos 1 mais 1 arcos, o que faz com que eu tenho uma árvore com cá mais 1 nós e cá arcos demonstrando a validade de que com N nós teremos 1 menos 1 arcos.
Agora, eu vou provar que, em qualquer árvore com N nós, o número total de extremidades de arcos é 2N menos 2.
Só para mostrar o mesmo raciocínio, está usando a infissão, empregado nesse contexto de extremidades.
Eu vou ver que é muito anual.
Para N igual a 1, eu vou ter 0 extremidades, certo? Para N igual a cá, eu suponho vale do que eu tenha 2 cá menos 2 extremidades, é 1,5 potes de indução.
Para N igual a cá mais 1, eu vou removê 1 folha e o seu arco.
Você já vindo para estratégia mesmo.
Então, temos um árvore com cá nós e, por impotes de indução, ela vai ter 2 cá menos 2 arcos.
Então, o que isso significa? Isso significa que é o adicional ou noio arco que eu havia removido, adicionalando noico como um nofólio e o arco que foi removido, eu volto a ter um árvore com cá mais 1 nós e mais 2 extremidades daquele arco que eu estava devolvendo.
Então, eu vou ter 2 cá menos 2 pela hipótese de indução, extremidades, mas as duas extremidades que eu retornei, o que me leva 2 vezes cá mais 1 menos 2 extremidades, provando que a acessão de que se eu tenha N nós vou ter 2 N menos 2 extremidades, está correpo.
Bom, espero que os conceitos sobre árvores têm ficado claro, recomendam a leitura da acessão 6.
2 do nosso material base e nos vemos no próximo.
Obrigado.