ÁRVORE BINÁRIA de BUSCA | Estruturas de Dados #13

[@thaisepessoa7173]

Meu professor passava seus vídeos nas aulas aqui da UFAM

[@pgdinamica]

Nossa, que prestígio! :O Obrigado por informar, fico feliz :) Bons estudos!

[@kizzy_terra]

Estava aguardando esse vídeo! 🙏🏾🙌🏾

[@pgdinamica]

👨🏾‍💻👩🏾‍💻

[@eric-6422]

Agradeço todos os dias pela existencia desse video.

[@pgdinamica]

Amém 🙏🏾

[@chupacabrasbr]

Excelente conteúdo !

[@pgdinamica]

Muito obrigado!

[@marciosousa7868]

Ótimo, gostei muito de suas explicações, muito obrigado. ^^

[@pgdinamica]

Valeu!

[@gustavorocha9774]

Que vídeos maravilhosos! Não esperava tanto dessa matéria até ver essa sequencia de vídeos! Obrigado por tornar programação mais empolgante do que já é.

[@pedroalmeida1681]

Obrigado irmao! Bela explicação, parabens...

[@pgdinamica]

Valeu!

[@danielmelo9064]

Aula maravilhosa!

[@pgdinamica]

Valeu!

[@anderssonalvesdasilva423]

Seus vídeos são incríveis, didáticos e fáceis de entender. Parabéns. Estou aprendendo muito.

[@pgdinamica]

Obrigado! Fico feliz em saber :) Bons estudos!

[@josineidesoares1402]

Muito bom, meu professor da facul selecionou seus videos como revisão para a prova.

[@pgdinamica]

Que legal! Fico feliz em saber :)

[@fonsekleandro]

Parabéns pelo vídeo! Assinei até a Alura pra me ajudar a aprender/entender esse conceito, e só depois descobri esse canal. A qualidade didática desse vídeo está anos-luz a frente dos outros materias que eu consultei.

[@pgdinamica]

Muito obrigado 😊

[@pedro.balbino]

Esse canal tá fazendo valer minha faculdade !!!

[@pgdinamica]

Sucessoo 🚀

[@tiagonascimento2232]

Excelente!!!!!!!!!!!!!!

[@pgdinamica]

😁

[@theredao]

Seus conteúdos são excelentes, parabéns! Já virem fã!

[@AndersonMarques-ik3tp]

Incrível essa aula! d+

[@pgdinamica]

Valeu Anderson!

[@gabrielprado6333]

Aguardo ansiosamente as arvores AVL e Rubro Negra. Já tem alguma previsão?

[@joaomaia2898]

mestre, que microfone ta usando? parabéns, excelente trabalho! obrigado pela iniciativa.

[@pgdinamica]

Microfone de lapela da Boya by-m1

[@jefferson-y9x]

boa noite professor, poderia me tirar uma duvida me ajudar a um critério de parada que poderia ser estipulado quando da realização de busca em árvores? .

[@NilsMendesTavares]

Mano, parabéns pelo vídeo! Explicação nota 10. Mano, tô tendo problema na execução do código, o meu só está retornando 3 números. Como faço para corrigir? Obs: estou usando o código que você disponibilizou no replit e estou testando ele replit também.

[@raniel0511]

Assistido ✔️ Árvores forever.

[@pgdinamica]

É uma das estruturas que mais gosto :D

[@vemprogramar]

Rapaz...vc salvou minha nota 🤣 Muito obrigado! Que canal fantástico e que maneira de ensinar! 👏👏👏👏👏👏👏👏

[@pgdinamica]

Muito obrigado! A nota é consequência do que você conseguiu expressar na prova. Eu contribuí com apenas uma parcela neste processo ;)

[@acfribe]

Muito Bom

[@pgdinamica]

Valeu, Augusto! 🙂

[@hiraokii]

Incrível

[@pgdinamica]

Obrigado!

[@brunno_gonzalez_dev]

Aula animal!!

[@pgdinamica]

Obrigado!

[@leandrosoares1663]

Prezado Hallison, obrigado pelo vídeo, está salvando meu mestrado! Eu fiquei com duas duvidas que provavelmente são básicas. Como a altura é calculada abaixo se você não usa nenhuma função do tipo de Len e etc. Você define a função height e depois simplesmente itera, confesso que fiquei perdido. def height(self, node=None): if node is None: node = self.root hleft = 0 hright = 0 if node.left: hleft = self.height(node.left) if node.right: hright = self.height(node.right) if hright > hleft: return hright + 1 else: return hleft + 1 Da mesma forma não consegui visualizar a logica do código abaixo e como conseguimos printar todos os nós, sendo que uso a função print apenas para o nó principal. def simetric_traversal(self,node=None): if node is None: node = self.root if node.left: print('(', end = '') self.simetric_traversal(node.left) print(node, end = '') if node.right: self.simetric_traversal(node.right) print(')', end ='') Se puder tentar me ajudar eu agradeço. Abraço!

[@pgdinamica]

Oi, Leandro, seu problema está em entender procedimentos recursivos. Você pode estudar problemas mais básicos como Fatorial, Fibonacci e a Torre de Hanoi pra revisar/praticar. Repare que nos dois casos, as funções chamam a si mesmas. Neste momento, a execução é “pausada” naquela linha da chamada anterior e inicia do começo com um novo valor. Você precisa seguir a execução do código (com papel e caneta) pra entender. Vou tentar digitar um exemplo do primeiro caso pra te ajudar. Pensa numa árvore que tem apenas a raiz (A) e um filho à direita (B). Você já sabe que a altura tem que ser 2. Vamos seguir o código *height* passando a raiz A: Como A só tem filho à direita, não entramos no primeiro if e o valor de hleft se mantém 0 como foi inicializado. No segundo if, hright vai receber um valor que ainda não sabemos qual; será o resultado da chamada recursiva passando o valor B (filho à direita de A). Nesse momento, verificamos tudo de novo… B não é None; hleft (outro hleft, diferente do primeiro, pois é outro escopo) é 0; hright é 0. B não tem filho à esquerda e nem à direita, então hleft e hright se mantém 0. É falso que hright > hleft (são iguais), então entramos no else e retornamos hleft + 1 (ou seja 0+1) = 1. Agora, que retornamos, continuamos a primeira execução, que estava parada. O hright da execução da raiz recebe o valor 1. É verdade que hright > hleft (pois 1 > 0) então entramos no if e, finalmente, retornamos o valor da altura hright + 1 = 2 👏🏾👏🏾👏🏾👏🏾 Você tem que aprender a seguir a execução da função pra entender. Este o tipo de coisa que o professor tenta ensinar pro aluno na faculdade com programação no papel, mas muita gente menospreza falando que nunca vai programar no papel na vida real. Só que o valor deste exercício está no raciocínio que deve ser desenvolvido, não na solução do problema real 🙂. Recursão é uma boa ideia de vídeo, vou avança-la na lista de prioridades de conteúdo. Quem sabe não rola mês que vem 🤔

[@jacksonburnley4686]

Hey, primeiramente obrigado pelos seus videos, tem me ajudado muito! Tem a possibilidade de você falar sobre b-tree? Tô adorando sua didática em binária e gostaria de aprender sobre árvores-B.

[@pgdinamica]

Obrigado! Tem, sim, mas provavelmente só no próximo mês...vou ver o que consigo fazer pra agilizar!

[@srdiegorodrigues]

Como posso implementar a busca na árvore binária, para que ela possa retornar cada nó visitado, dentro de uma lista, até encontrar o nó alvo?

[@linkopaladino]

Poderia me mandar o link do primeiro video, não estou conseguindo ver a ordem dos videos

[@pgdinamica]

Aqui está a playlist: kzbin.info/aero/PL5TJqBvpXQv5Bb71AE5Cd_kB5rNsfU4Cp&si=DF7lLJV6PSprgnN8

[@linkopaladino]

@@pgdinamica MUITO obrigado, parabéns pelas aulas, você é muito inteligente, que Deus te abençoe muito.

[@ulissesargileu4664]

Aí Hallison, posso dizer que a ideia da árvore binária de busca é poder ordenar sem ter que passar pelos algoritmos de ordenação com o percurso simétrico, economizando processamento ?

[@pgdinamica]

Sim, pode. Repara, no entanto, que se você só precisa ordenar uns dados uma vez, provavelmente, vai usar um algoritmo de ordenação. Agora, se você precisa manter seus dados sempre ordenados, daí vale a pena construir uma árvore e fazer as operações de busca, inserção e remoção nela.

[@matheusfelipe1107]

Muito legal, Hallison. Tenho uma dúvida: sempre quando assisto alguma aula sobre esse tipo de estrutura/algoritmo de busca vejo que em grande parte é usado somente valores númericos inteiros ou fracionados - suponho que seja para facilitar o entendimento. Com valores do tipo string acredito que esse mesmo trabalho seja feito com base na ordem alfabética, correto? E em outros tipos de dados (binário, hexadecimal etc), que não amazene dados inteiros ou fracionados na conversão binario->decimal/float, como funcionaria essa estrutura e a busca? ou ela não é própria para isso?

[@pgdinamica]

Essa estrutura de dados, assim como os algoritmos que você está habituado a ver não dependem do tipo de dado. O que você precisa é de tipos em que seja possível definir uma ordem, ou seja, comparar quaisquer dois elementos. Essa é uma questão matemática. Do ponto de vista de implementação, basta que seja possível usar o operador "

[@matheusfelipe1107]

@@pgdinamica Perfeito! Muito obrigado pelo esclarecimento ;)

[@pgdinamica]

🤙🏾

[@adriellibarboza5320]

Ainda não entendi ,como isso se aplica no dia a dia da programação ? Tipo...cadastros ? Busca de ID's ? Estou confusa em visualizaar as aplicações do dia a dia ,se alguém puder me explicar ou exemplificar ,por favor

[@pgdinamica]

Bancos de dados, sistemas operacionais, HTML... em quase tudo você vai encontrar uma estrutura de árvore (nem sempre binária) para organizar informação. Acabei de buscar "matemática" no Google e ele informou no topo: "Aproximadamente 491.000.000 resultados (0,33 segundos)" como fazer isso tão rápido sem estruturas de dados eficientes? Qualquer pessoa que tente projetar um sistema complexo pra resolver problemas e lidar com grandes quantidades de dados vai se deparar com a necessidade de estruturas de dados eficientes como uma árvore binária de busca. Você consegue imaginar a quantidade de operações envolvidas pra gerar cada quadro de uma animação da Pixar ou um jogo de vídeo game, por exemplo? Tem vídeo aqui no canal implementando um visualizador por Ray Tracing (kzbin.infoLlNaI6upK94?feature=share) e já levou um tempo razoável para fazer uma cena simples, imagina ter que calcular interseções de raios 3840x2160 raios (resolução 4K) contra bilhões de polígonos em uma cena! Você tem que fazer uma divisão da cena que segue um modelo inspirado na árvore binária. Um dos algoritmos mais usados para compressão (medium.com/programacaodinamica/desvendando-os-arquivos-de-imagens-17f1f95dc4b0) é baseado na árvore de Huffman.

[@adriellibarboza5320]

@@pgdinamica Valeeeeuuu , entendi agora , obrigada !!!!

[@baumths]

Ótimo vídeo! Gostei do tema do vs code, lembra o nome?

[@pgdinamica]

Cobalt2. Cobalt era um tema do TextMate, que eu amava! Sempre tento encontrar um parecido quando mudo de editor, este é o mais próximo que consegui, mas o original é ainda mais bonito.

[@baumths]

@@pgdinamica Nice! Muito obrigado!

[@homejonny9326]

professor nato

[@pgdinamica]

Valeu! ✌🏾

[@juliocesarjuvenal4912]

Poderia fazer um video em arvore mas na linguagem c estrutura de dados

[@pgdinamica]

Se você focar em *entender* a ideia por trás dos algoritmos e estruturas de dados, será capaz de implementar em *qualquer* outra linguagem :)

[@rubemalvesfigueredo9143]

Prezado, gostei muito de sua aula, porém eu tenho uma dúvida, que é mais um desafio. Como seria o tratamento dado para a entrada que um usuário fizer de uma árvore? Exemplo: Entre com uma árvore [ ex:(5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) ], como o usuário poderá entrar com uma árvore como esta e tratarmos cada valor? Como verificar se esta é uma árvore binaria de busca verdadeira, através de um script em C?

[@pgdinamica]

Oi, Rubem, não sei se entendi a sua primeira pergunta. Pra recuperar uma árvore a partir da entrada, você tem que saber qual foi o tipo de percurso que gerou essa sequência. Você pode percorrer a árvore em pré-ordem, pós-ordem, ordem simétrica ou em níveis, ao longo desta série sobre árvores, eu mostro cada um dos percursos (os vídeos geralmente não tem o nome do percurso no título, pois os percursos são um recurso para algum outro objetivo; por exemplo, no vídeo sobre altura da árvore ensino o percurso em pós ordem para calcular a altura). Se você não souber como a árvore foi percorrida, não tem como garantir que vai reconstruí-la na ordem correta. Sabendo o percurso, o usuário entra com uma lista normal de números. Quanto à segunda pergunta, você precisa pensar na propriedade de uma árvore binária de busca: *para cada nó, o filho a esquerda é menor e o a direita, maior*. Como tem que valer para todo nó da árvore, você tem que percorrer a árvore, por exemplo em pós-ordem, e toda vez que você visitar um nó, basta verificar se o filho à esquerda é menor (ou igual) a ele e se o filho a direita é maior que ele.

[@rubemalvesfigueredo9143]

@@pgdinamica Prezado Hallison, acho que realmente você não entendeu o que perguntei. Tentarei ser um pouco mais direto. A questão é: Desenvolva um script em C no qual o usuário entre com uma árvore [exemplo de entrada: (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) ] e tenha como saída, se a árvore é uma árvore binária de busca VERDADEIRA ou FALSA. Ou seja, a árvore apresentada na entrada, se for uma árvore binária de busca, VERDADEIRO, se não, a resposta será FALSO. O problema maior é: como entramos com uma árvore, conforme o exemplo, e tratamos cada um dos valores dos nós para sabermos qual seria a árvore binária de busca verdadeira e assim poder comprar com a árvore que foi dada como entrada?

[@MichelLedig]

@@rubemalvesfigueredo9143 essa entrada é só pra voce montar a árvore, depois é só você verificar se em algum momento o No pai aponta pra um valor maior na sua esquerda ou menor na sua direita. Caso entre em uma dessas condições é FALSO (não eh arvore binaria de busca) se não entrar em nenhuma é VERDADEIRO(é uma arvore binaria de busca) Me parece que seu maior problema vai ser tratar esse input e criar a arvore em C do que de fato responder o conceito da questao, boa sorte!

[@marcusoliveira2522]

2024 e eu aqui

[@pgdinamica]

Bons estudos! Traz mais gente pra me incentivar a terminar a playlist 😅

[@fernandodmedeiros603]

Mestre, muito bons os vídeos mas neste #13 a partir dos 22 min ficou muito corrido... Fica a sugestão de editar e regravar na mesma vibe que vinha sendo apresentado o conteúdo. Abs

[@pgdinamica]

O que ficou prejudicado de entender? Como posso te ajudar com a sua dúvida agora?

[@fernandodmedeiros603]

Nada muito! Mas ficou meio corridas as alterações e correções dos erros… Mas tudo certo. Obrigado pelo retorno

[@kuririnOffc]

QQ ué critério posso elencar como parada?

[@pgdinamica]

Oi, Diego, se você puder ser mais específico como: "Quando quero fazer TAL COISA, qual seria um bom critério de parada?" ou "No minuto TAL, qual seria um bom critério de parada?" Me ajuda a entender para responder :)

[@kuririnOffc]

@@pgdinamica sim :) Bom emna busca Binaria tem critérios que fazer com que a busca se encerre, me diz um critério...

[@pgdinamica]

kzbin.info/www/bejne/e5ivdmh-rLesla8

[@Hilow3]

essa arvore no começo não tem altura 5 e sim 4

[@pgdinamica]

Tem altura 5, sim.

[@Hilow3]

​@@pgdinamicaué sério? Altura não é a maior distância da raiz até a folha mais longe? 61 até 89 um passo, 89 a 66 dois, 66 a 79 três e 79 a 82 quatro