o Olá bem-vindos a mais uma aula de estrutura de dados e hoje a gente vai dar sequência na aula sobre árvores vamos falar específica que são as árvores binárias e bom então aqui a gente tem definição parecida com que a gente apresentou anteriormente com relação as árvores porém Observe que agora a gente continua uma vinagre um conjunto finito de elementos né do nada os pés tá aqui a pode ser vazia né então ela pode ser um conjunto vazio só que agora a gente tem uma raiz União coma sob a vo esquerda no TRE e uma subárvore direita sendo que assobiava esquerdo e direito também são alvos binárias Então pode acontecer de ter ou te de também ser vazia né então nessa definição R é o nosso especial chamado Raiz e os demais nós são conjuntos vazio ou são conjuntos de juntos né de ala esquerda direita chamado sobre as esquerdas de tempo sob a asa direita de tempo cada Qual é uma árvore binária então todas as propriedades e também vale e observe novamente a definição recursiva aqui e com que a gente poderia implementar uma árvore binária em Python né então novamente a gente vai utilizar classes né Então você já estão um pouco mais pormenorizada com a linguagem Então temos aqui um Construtor né então quando crie uma árvore eu vou passar o dado essa informação que vai ser armazenado a subárvore esquerda e a subir a direita né sendo que qualquer uma dessas pode ser vazio né então por isso que a gente já atribuiu a kinoni aqui por exemplo eu tenho aqui uma uma árvore na criado né e a gente você deve lembrar daquela representação baseada em grafos né você consegue visualizar a representação dessa árvore né então a gente tem que uma árvore ua a ela vai ter uma raiz 10 nós temos aqui na subir a vou colocar a soberba esquerda dela sobre a esquerda dela tem uma raiz é aquele 30 né Então essa quer subir Av esquerda dela bom então tudo se quer saber a esquerda e essa quer subir arco direita então sobre a direita tem aqui o 20 mas da sub-árvore esquerda ela tem também uma sob a árvore né Olha tem subir aqui que tem o a 40 esse 40 o lado esquerdo dele é vazio a gente pode apresentar aqui desta maneira e assobiado direita dela eu tenho um elemento 60 então aqui eu tô esquecendo né um objeto não estão sendo uma árvore que graficamente a gente poderia representar com esse desenho aqui que eu fiz ao lado e G1 bom então é com relação a gente pode olhar algumas características né Por exemplo conceito de estritamente binária estritamente binária né cada nota em grau 0 ou 2 ou seja todo Nossa em 0 ou dois filhos né Por exemplo nessas duas árvores aqui né Qual a árvore que é estritamente binária né a gente for olhar para fazer esse primeiro nó né Tem apenas tem dois filhos e sinnott que tem zero outro tem dois filhos e aqui tem dois filhos fizeram então essa aqui é uma árvore em você também tem binária Ok e a b a b a gente foi lá já para este Nokia Observe esse nó e ele tem apenas um filho né então você tem aqui um nó que não obedece essa regra logo essa que ela não é estritamente binária então a única que é essa deixa que eu não vou outro conceito que é árvore binária completa né é uma árvore estritamente binária então Observe que a gente está adicionando a nova propriedade né então ela tem que obedecer a propriedade ser estritamente binária na qual todos nós que apresenta algumas sobre a vazia está localizado no último ou no penúltimo nível né bom então aqui por exemplo Observe que eu tenho que 3 a nossa a base Isso você já tem três folhas essas três folhas estão no último ou no penúltimo agora nesta Otávio ao tenho que uma duas três quatro folhas né mas Observe que eu tenho aqui no último no penúltimo e tem aqui uma mais acima né no antepenúltimo Então essa água que não é uma árvore binária completa Oi e para finalizar que os conceitos interessantes com relação a luminária tem esse outro conceito que a binária cheia né nesse caso né todas as folhas estão no mesmo nível né então deixa para você claramente KB é a única que pensa propriedade né então você tem por exemplo uma binária desta né é cheia na ela só acontece em algumas situações específicas representa Observe que a quantidade de nós que eu tenho aqui ó uma dois três quatro cinco seis sete se eu adicionar aqui mais um nó que que vai acontecer nessa adicionar mais um nó como é uma binária né eu não tem como eu vou ter que adicionar mais um elemento aqui ela ela vai deixar de estar todas no mesmo nível então ela vai deixar de ser uma luminária cheia porém ela vai ser mas binária completa quais são as melhores se ela tem essa propriedade que quer bastante interessante né então quando Todos Nós entramos tem grau dois todas as coisas estão no mesmo nível da ORM nasher propriedade é que o número de nós no nível ir é sempre dois elevado aí ó bom então aqui eu tenho presente quantos nós que eu tenho aqui no nível zero é 2 elevado a zero 2 elevado a um tem dois nós dois elevado a 2 Eu tenho quatro nós aqui né então se eu continuo ter uma minaria cheia né No próximo nível eu teria completado esse aqui né então cada um daqui teria que ter dois filhos e aqui vai ser 2 elevado a 3 Então tem que ser oito um dois três quatro cinco seis sete oito né então é uma propriedade em interessante E aí G1 E aí e agora vamos falar um pouquinho sobre percurso né em árvore binária eu percorri amarrado binária né é diferente do que percorreu uma lista né uma lista uma estrutura de dado linear sequencial então você pode falar no primeiro segundo terceiro elemento já não a binária ela tem hierarquia então quê que tem primeiro a esquerda ou direita né então você que tem definir qual o caminho que você vai seguir então quando está falando percorrer né esse processo de visitar não pode ser por exemplo ao quero imprimir Eu quero alterar o valor do nó eu quero pegar esse valor para fazer alguma operação né E aí a gente pode definir seus caminhos possíveis como é uma binária a gente vai ver que estamos três percursos básicos né que eu pré-ordem em ordem e pós ordem Hoje a gente vai falar agora sobre esses 31 o pão coloquei uma árvore binária aqui tá representando uma expressão aritmética né então vamos ver agora pé hora para ordem Qual que é o caminho que ele faz Ele visita na raiz percorre a subárvore esquerda percorre a sobre a direita Então como é que ficarei aqui a gente vai começar aqui pela Então vou visitar o nosso raiz né então visitando a raiz vamos aqui em imprimir e mais depois que eu disse treino raiz eu vou para subir arco esquerda né e eu vou visitar também a raiz e essa sobre a esquerda ela não tem filhos terminou por aqui depois eu vou visitar o nó da direita né o seu plano nós da direita eu vou visitar a raiz multiplicação e aí eu vou visitar a subir água esquerda que eu sei se eu vou visitar o sobre as direita que é o 21 bom então essa aqui é o pré-ordem né e aqui a gente olha que a gente já falou sobre isso nem outra ao sobre a forma de representar expressões né então você quer forma pré-fixa né os operadores vem antes dos operandos bom então exatamente que a gente fez aqui agora o algoritmo né novo ritmo repulsivo né Vocês lembro que eu falei com vocês que quando a gente trabalha com árvores dado que abre são estruturas recursivas são mais fáceis de ser implementado por exemplo funções recursivas do que a gente possa implementar uma função interativa aqui o código interativo Então pré-ordem observa Ele é bem simples se abre não é vazia né o que que eu faço imprimo o Nó e chamo para ordem para subir aba esquerda e para ordem para sobre a direita depois vocês prestam também esse código e lá no refletir e também no Python tutor Eita acabei passando aqui no caminho inverso aqui então aqui é em ordem então em ordem que quer objetivo da gente a gente vai percorrer a subárvore esquerda visitar o nosso Raiz e percorrer a subárvore direita né então quando eu começo aqui na minha minha árvore eu não vou logo primiro mais na verdade eu vou para subir árvore esquerda e na sobre a esquerda também não vou para raiz né eu vou para superar o esquerda dela porém essa esse nó aqui tem um ele é e não tem filho da esquerda Então agora eu posso visitar a Raíssa o povo de para subir a direita também não tem né então encerrei ou volto para cá e vou imprimir agora ou a raiz vou para subir a direita indo que passou bem à direita o que que eu faço só que eu já imprimo a multiplicação não né o algoritmo saber que da mesma maneira então eu vou para sobre a esquerda dele eu vou imprimir os seis e Imprima raiz ó e vou para Sobral direita né bom então é essa minha expressão essa expressão é familiar para vocês parece que essa expressão em ordem né Observe Então esse caminhar aqui em ordem vai gerar esse formato de expressão em ordem E aí a vara o pozzoli o pozone eu vou percorrer a subárvore esquerda à direita e só depois que eu visitar uma raiz né então quando eu começo aqui imprimir nossa árvore eu vou para subir árvore esquerda Então vou quando eu for para subir a esquerda essa que ela não tem filhos né Então eu vou lá é um E aí depois eu vou para onde eu vou para a raiz não né eu vou para a subárvore direita eu já vou imprimir aplicação não eu vou ter que passou bravo direita e esquerda né Desculpa Imprima aqui os seis e depois eu vou para onde Para eu vou cumprir minha raiz ainda não né vou ter que ir para subir aba esquerda direita né só tô confundindo aqui esquerda direita Desculpa então eu vou aqui em primo ou dois agora eu vou voltar né então agora eu posso imprimir raiz aqui que a multiplicação e posso imprimir a raiz que faltou que é a soma então que tipo de expressão é essa a posso fixa né então é esse caminho ordem que já era essa pós-fixa bom então algoritmo dela também é simples é Observe que a gente vai chamar aqui pós órgão para sobre a esquerda após ordem para subir a direita e imprimi árvore novamente você depois podem testar Ah pois aqui temos poder falar sobre as binária de busca desculpa né sobre algo de binária e modo geral né que são essas árvores que tem no máximo dois filhos só que e a gente vai ver agora um outro tipo de árvore né dê uma olhada aqui nessas duas árvores aqui elas que elas têm em comum aqui então eu tenho que ir com letras se eu pegar aqui o Caio olhar para a esquerda Uai menor que cá né o Pia maior que Car em menor que p r mal que pelo essas novas também tem 13 dez 2012 são todos menores que 13 2520 31 e 29 todos eles são maiores do que 13 né Então essas duas árvores aqui né Elas têm em comum que dado nenhum norte né em todas as armazenadas em suas sob a aba esquerda são menores que o valor mais e nada nesse nora então por exemplo se eu pego três aqui todos os nós da Silverado esquerda são menores que ele e todos os nossos da sobre a direita são maiores que ele e essa propriedade ela tem que se manter para toda a água ela tem que fazer para 13 aqui para nós lá isso mas se eu pegasse essa sub-árvore aqui viu que tem como raiz aqui 25 tem que valer a mesma coisa então os nossos a sub-aba esquerda 20 é menor tem apenas um e os da direita são maiores 31 e 29 bom então é que eu vou ligar para essa alta definição aqui mas simples tem outras palavras né em uma bebê tem esse aqui ela é uma binária Então tem que ter todas as propriedades de uma árvore na área vai qualquer nó ver os nossos Uberaba esquerda possui valores menores que o associado vai qualquer 9 os nossos sobre a ver direito possuem valores maiores do que valor associado e a subir aves a esquerda EA direita também são alguns binária de busca então todos tem que manter a mesma propriedade é a que a gente tem exemplo duas árvores aqui né só as luminárias né Mas será que ambas são alvos binária de busca Vamos começar com R1 né só tenho de óleo de dentro B A e C são menores né FRG Então são maiores então se eu pegar também o f é menor do que F é maior aí menor ser é maior então ela é uma bebê esr2 será que ela é uma bebê se olhar para o dei Olha a b e c são menores Ok seu olhar aqui para o dedo também FRG são maiores mas se olhar agora para essa outra sob a árvore é que tem um raio zoar a esquerda dela tem um bebê Então esta que ela não é uma bebê porque o b é maior deveria estar à direita né então por causa dessa e aqui essa R2 não é é uma amizade busca né bom então onde que a gente utiliza a homenagem de busca né com próprio nome diz esta pousada em Extrema para melhorar a eficiência na busca Você deve lembrar do algoritmo de busca binária né então quando a gente tem uma binária de busca e ela precisa ter uma condição né mas não vou entrar em detalhe agora ela garante a eficiência que a gente tem por exemplo com a busca binária é bom então por exemplo aqui a gente coloca uma situação né imagina o sistema de votação por telefone cada número só pode votar uma vez né e os termos de armazenar todos os mundos que já votaram então a cada ligação deve-se verificar se o número já voltou a votação deve ter resultado em tempo real Então ela tem que ter eficiência aqui né então você vai adicionando toda vez que eu alguém ligar você adiciona esse número uma mênade de busca e aí com dá daquela que precisava vinagre busco você é muito mais fácil você encontrar esse elemento verificar se as elemento existe ou não dentro da árvore do que a gente tivesse por exemplo usando uma lista e fazendo toda vez tenho que fazer uma busca sequencial dezembro com a busca sequencial no pior caso né a gente pode ter que fazer em operações só tem lá já 1 milhão de as ligações eu vou ter que percorrer um milhão para saber se existe ou não G1 bom então aqui abordagem né então quando a gente vai usar beber né Cada não é Rosa nada Eu nada bebê Oi e aí quando você pode ter milhões de telefones né fica bem mais rápido né mas eficiente a expectativa né de uma árvore que aquela que lhe mostrou por exemplo com relação a busca binária a que logo 2D e no final tinha mostrado para vocês que para um milhão e Na pior das hipóteses das hipóteses necessitam contando com sorte você tem um milhão de elementos eu vou gastar no máximo 20 operações Mas eu posso gastar menos eu posso gastar 10 posso gastar oito né despertar uma operação mas na pior da situação vou gastar 20 que é o valor muito melhor do que 1 milhão né Ah tá que está mostrando isso né então por exemplo Qual é a quantidade aqui de um de nós aqui para cada coisa lá era 19 alguma coisa né só para dois milhões é 2016 dessa então isso considerando né mas binária cheia que é isso essa binária o que a gente vai não pode usar também tempo que ela é balanceada ou seja não tenho mais nós as criadas ou mais nossa direita né então a gente comprar e direita e esquerda observa Que ela segue o mesmo padrão né tem a mesma altura então a gente diz que era uma vi nada me balanceada a gente vai ver que infelizmente né E isso depende da inserção e às vezes a gente não vai conseguir essa perfeição aqui por isso que existe outros tipos de árvores que são as árvores balanceadas né exemplo são as árvores avl e tem a árvore rubro-negra né ou do inglês Red Black Tree São dois algoritmos que busca garantir que a árvore se mantenha balanceada e aqui temos exemplo aqui de algumas buscas né Por exemplo assumindo né que eu sei que uma árvore é uma bebê é como é que seria a busca aqui eu tô buscando por exemplo elemento é eu começo aqui no eu sei que o É tem que estar direita né Então vem aqui para a direita consulta que o efe aí eu sei que ele tem que tá esquerda agora três operações né aqui agora eu não sei né Então vai depender né de qual caminho que eu vou seguir nessa eu vou para fazer um o pré-ordem pós-ordem ordem né mas vamos ver aqui e os algoritmos aqui para gente caminhando para encerrar esta aula vamos as operações para mim te buscar em inserir e remover um elemento e a busca né então como é que seria a busca a gente vai comparar na chave porta o caso que a árvore vazia né Olha estamos aqui novamente usando recursividade Então é só que ser o caso base né a vazia eu posso retornar Noni não encontrei nada né e noutro caso base aqui né se essa informação né É que eu tô procurando eu já retorno esse nó e se não aí eu vou ter que verificar por exemplo se x for maior do que a informação que eu tô procurando Então eu tenho que procurar nosso ganhava direita se caso contrário eu vou procurar na sobre a esquerda aí vem aqui para a recursão aqui bom então por exemplo ao 28 armazenado né eu vou começar a comparando com 23 gente vai ter maior que o 23 então eu sei que tá na assobiado direito 28 é menor que 35 então tentar nosso goiaba esquerda e aqui nesse caso encontrou e agora vamos dizer que esse pão da inserção né então exceção a gente tem algumas situações também se abre for vazia né Ou seja você é igual None basta criar um nó retorna O nome os sushis já está lá né Vocês isso x é igual ao da raiz eu retorno R eu não adiciono ninguém não precisa não posso adicionar dois elementos que o mesmo valor e se x é maior do que é rico eu vou estaria aonde eu vou inserir na direita se x é menor eu vou inserir na sob a árvore esquerda bom então aqui vamos ver o caso aqui de sessão aí a remoção a gente ver depois É tão bom saber que o 23 Então abre a vazia só creio nov23 tá dando somente sobre a esquerda e direita são vazias gostaria 1515 eu vou estaria aonde na direita ou na esquerda na esquerda né Aí eu faço uma ligação há 35 eu vou estar aonde na direita do 23 né e agora vou estaria 2828 entrar onde eu vou olhar aqui 23 também tem que tá aonde eu tenho que dar direita né a direito do 23 só que a esquerda 35 né um negócio que a gente pode ir mostrar rapidamente o algoritmo de remoção ou de remoção Grande Desafio dele a manter a propriedade das binária de busca após a remoção existe alguns casos né fazendo o nosso removido não tem filho ou nosso removido tem um único filho ou nó passem removido tem dois filhos né o caso o nosso Novidade tem filho é o caso mais simples né basta você remover ele seja apontar aí para mim tá Boa problema então aqui eu quero remover o 1515 não tem filho né eu vou gerar essa árvore aqui onde que tem apenas o controle apenas agora um filho 15 Foi removido o ponto caso né Você tem um único filho né então a gente pode dizer quem vai puxar o filho para o lugar do Pai então eu tenho aqui os cinco né os cinco vai ser removido Então quem vai ser o pai aqui seria 6 ou seja ou o filho de três Passa seus seis então é tranquilo o que é um pouquinho mais complicado é o terceiro caso né quando eu tenho dois filhos né porque elas vão ver que o 11 como é que eu faço para remover 11 aí eu posso o importante é manter a propriedade né Então observa aqui seu olhar dá para perceber a esquerda né eu posso pegar por exemplo quem eu posso pegar o antecessor né ou seja o nome mais é direita da sub aba esquerda seria o 10 né há dez anos pessoa a gente foi lá antes do ônibus vem quem daí né ou sucessor o sucesso é quem é o nome mas a esquerda da Sobral direita né o normais esquerda sobre a direito ao 12 aí aqui contar na sequência né Realmente é o sucessor de 11 é o 12 né Então vamos usar como exemplo mover o sucessor no o saco sucessor tem filho né mas é aplicar mesma regra vou remover ele né então ele tem apenas um filho que que vai acontecer então desse lado aqui eu tenho 14 ou remover o 12 né então só que o doce só tem um filho né então fico três aqui ó e aqui fico 15 e aqui sim eu quero 11 né que eu tô tentando remover eu vou colocar o 12 no lugar do 11 e o restante se mantém 9 e 10 ok bom então é isso né 12 9 10 aqui eu tenho 14 13 e 15 o último exercício pessoal faça esse exercício aqui na nossa encontra a gente pode trabalhar ele então começa com a vazia insira esses valores e depois da resultante remova é o 10 o 5:52 depois agora insira os em 80 70 e depois eu morro 1549 35 depois a gente pode no encontro a gente trabalhar esse exercício aqui e assim a gente encerra a nossa aula até o próximo encontro e bons estudos