Estruturas de Dados - Árvores (Conceitos)

Olá meus caros alunos estejam bem vindos aula de hoje hoje nós vamos falar sobre a estrutura de dados árvore o roteiro que eu vou seguir para aula de hoje será vamos começar um pouco com os conceitos básicos de árvore depois vamos falar sobre a árvore binária de busca onde eu estou mais interessado em fazer com que vocês entendam as operações de busca inserção e remoção e ao final Eu vou falar sobre percursos em árvore Bom primeiramente conceitos básicos de árvore uma árvore é um conjunto de nós em que existe uma raiz e contém 01 ou

mais sob a árvore de sinnott Raissa vou chamar de R e as raízes dessas subir árvores elas são ligadas diretamente a r essa subir árvores começam a anteriormente elas também estão a árvore ou seja essa definição que eu estou dando aqui para vocês ela é recursiva é uma árvore Ela não é uma estrutura linear Porque apesar de para Cada nó existir no máximo um predecessor o sucessor ele já viola a regra de estrutura linear Ou seja eu posso ter mais de um sucessor para cada ó essa de estruturas do modo como elas são definidas elas

são adequadas para representar hierarquia nos dados uma coisa que nós não conseguimos nas estruturas lineares e vamos dar um exemplo aqui de árvore em uma árvore como eu disse a definição existe um nó raiz chamado r&a esse nó raiz são ligadas às raízes da sub-árvores então eu tenho essa subir árvore da esquerda e essa subir a árvore da direita nessa sob a árvore da esquerda o nó a esse é o nosso 18 nada direto na raiz é o 58 e esses nós seguirão diretamente a raiz da árvore que é o nó R da forma como

eu disse na definição interior e eu disse também que as sob árvores elas são na verdade árvores Porque vou pegar essa sub-árvore aqui e vou aumentar essa sub-árvore nessa sub-árvore aqui nós temos um nó raiz chamado res9 a estão ligadas os 60 e 81 que são respectivamente as raízes da sub-árvore da esquerda e da direita Então esse daqui satisfaz a definição de árvore e vamos falar agora sobre alguns termos que eu vou usar com frequência eu preciso que vocês saibam o que significa por exemplo grau de um nó é o número de subir árvores de

sinnott se eu pegar por exemplo nos Sete nós vamos perceber que ele possui duas sub-árvores essa sob a árvore da esquerda e essa subir árvore da direita então o nó o grau de sinoc é dois utilizando o conceito de grau eu posso classificar todos os nossos em dois conjuntos primeiramente eu posso dizer que um uma folha é um nó de grau zero por exemplo o novo 29 eu não há 40 o nosso 65 eles possuem grau zero então eles são nós folhas enquanto que os nós internos são todos os nós que não são folhas em

outra palavra estão nós de grau maior do que zero como 30 que possui grau dois o 26 também possui grau dois o 15 é uma interna porque porque possui grau 1 e quando a usar o termo descendentes eu quero falar sobre todos os nós da baixa de umdeterminado nó por exemplo descendentes nós 18 São todos os nós que estão nesse polígono aqui que eu desenhei para vocês são nós que estão abaixo de um determinado nome e continuando aqui a nossa nomenclatura vamos falar sobre o que é uma altura altura de um Noel comprimento do caminho

mais Lon mas que são importantes entre o nó até uma folha então para essa árvore aqui eu já defini com essas cores todas as alturas dos Nós por exemplo esses nós marcados em amarelo são os nossos folhas eles são nós que possuem altura zero esses nós aqui um pouco mais avermelhado eles são nós que possuem altura um por exemplo no 30 o caminho mais distante entre s note 31 folha é um por exemplo possa escolha tanto 29 ao 40 aqui estão as folhas o caminho é de mesmo tamanho e o caminho o tamanho dele é

com esse 96 é de interessantes porque ele tem uma folha que com distância um mas para definição de altura eu preciso do caminho mais distantes o caminho mais distante seria por exemplo em relação ao 41 já está pintado de azul por quê Porque ele tem altura dois Observe 19 24 que ele à raíz ele tem altura quanto a altura do no Raiz é também a altura da árvore por definição então quando eu digo altura da árvore eu estou dizendo que é a altura do nó Raiz um outro conceito importante ao conceito de profundidade enquanto a

altura ela referencial nó em relação a folha mais distantes a profundidade ela faz referência à distância entre um nó e a raiz como só tem um caminho do até a raiz então basta dizer que a distância desse nó até o nosso aí sou da raiz até sinnott então por exemplo a profundidade do na raiz é zero a profundidade de todo mundo que está ligado ao nosso raiz é um e assim sucessivamente se a gente tem um nó de profundidade ir e ele possui filhos então Speed serão por eu e mais um em alguns casos eu

posso usar o termo nível ao invés de profundidade significa a mesma coisa e o que que é uma árvore binária é uma árvore que abaixo de Cada nó existem no máximo duas sob a cruz em outras palavras uma árvore binária aquela entre todos os nossos tem grau 0 1 ou 2 e é agora que temos esses conceitos vamos falar sobre árvores binárias de busca que que é uma árvore binária de busca inicialmente a uma árvore binária em que a cada nós todos os registros confiáveis menores que a de sinnott estão na sob a árvore da

esquerda enquanto que os registros com Chaves maiores estão na subir a árvore da direita em outras palavras uma árvore binária de busca cria algumas descrições sobre o conteúdo das chaves dos nós e o posicionamento desses nós na árvore exceções remoções e buscas possuem número de comparação proporcional à altura da árvore Vamos tentar entender isso vendo como são essas operações vamos supor que eu tenho essa árvore e nessa árvore eu quero fazer uma busca pelo elemento 35 para buscar treinamento 35 nós começamos pesquisando a raiz da mais tempo e vamos vamos começar pela raiz da e

vamos verificar hora na raiz da árvore eu tenho nove 2411 14 é o elemento que eu estou buscando Não não é mas ele me dá uma indicação como eu sei que os nossos maiores do que eu 24 questão do lado direito eu sei que o próximo passa buscar na direita da Harpa nessa árvore aqui eu pintei alguns nós de verde em alguns nós de amarelo que que significa um essas cores significa o quê que esse nós tá me dando de informação nessa busca específica por exemplo 9/24 me diz busque na direito eu pinto ele de

ver o nosso 58 pintei de amarelo porque porque ele está me dizendo busque na esquerda então cheguei no 24 mas eu quero 35 ele me disse busque na direita você é maior do que eu daí eu chego no 58 ele me diz hoje que nós esquerda você é menor do que eu o 26 me diz olha 35 é maior do que eu então que tem que buscar na direito Ah tá o 30 também me diz a mesma coisa ele diz 35 é maior do que eu então você deve buscar na direita o 40 vai me

dizer busque na esquerda mas acho que ela está vazia e isso quer dizer é que eu não achei o elemento 35 tá então perceba uma coisa para fazer a busca Eu comecei no nó Raiz e me aprofundei na árvore como eu me aprofundei na Árvore até não encontrar o nó que é o meu pior caso Isso significa que para fazer uma busca no pior caso eu percorro a altura da árvore o número de comparações que eu faço é proporcional à altura da árvore da mesma forma que eu falei no slide anterior e vamos falar agora

sobre inserções aqui tem a inserção de vários nós por exemplo existe uma árvore vazia e ao exterior 19 24 para inserir 9/24 basta dizer que ele é raiz já que ela estava vazia ao inserir o nós 18 eu comecei pela raiz que era 19 24 e ela me disse olha você vai ter que ir para o lado esquerdo porque você é menor do que eu eu pintei de amarelo dizendo por isso que aqui uma posição para você na Mesquita como estava no eu coloquei o 18 o set da mesma forma o 24 me disse para

ir para direita para esquerda e o 18 me disse para ir para a esquerda eu coloquei os apps aqui ao exterior 5824 me disse olha coloca do lado direito porque porque você é maior do que o 26 o 24 Acabou me dizendo Olha lá para o meu lado direito e os 58 me diz que vai para o meu lado esquerdo então o que que eu estou fazendo na verdade na hora de inserir Eu estou fazendo uma busca pela posição aí eu o cara que elemento tá então isso é importante porque porque da mesma forma como

ocorreu na busca aqui eu me aprofundo na Árvore até encontrar a posição do elemento então isso quer dizer que no pior caso eu vou percorrer toda a altura da árvore então assim como era na busca na inserção o número de comparações é proporcional à altura da árvore porque porque o coloco o elemento na posição em que ele estaria se fosse buscar E no caso da remoção o algoritmo é de um pouquinho mais complexo vamos supor que eu quero remover o nó 20 dessa árvore daqui primeira coisa que eu vou olhar isso aqui é o caso

com o nó 20 não possui filhos como não atende não possui filhos eu simplesmente removo novinhos e a árvore já ficou do jeito que eu gostaria que ela ficasse sem o nozinhos se eu quiser então em vez de remover o nó 20 remover o nós 19 daqui eu vejo nós 19 ela ele possui um filho que é o vídeo eu não posso perder 15 20 ao removeram 19 tá não vou perder não vou remover a subir a árvore inteira É só remover o nó que que eu faço nesse caso eu pego 90 e substitua no

lugar do 19 por quê Porque tem apenas um filho então quando tem um filho eu substitui o filho no lugar do nosso ser removido e quando eu tenho dois filhos o que que eu preciso fazer tem duas opções aqui de algoritmo a primeira delas é em o sucessor lógico e a segunda delas envolve usar o predecessor lote primeiramente o que que é o sucessor lógico sucessor Lógico é o nó é o elemento que vem logo depois um determinado elemento na sequência ordenada se a gente tivesse uma sequência ordenada desses nós ou 25 viria logo após

do 24 então nós sabemos que o 25 ao sucessor lógico como eu acho 25 eu vou na qualidade direita e procura o filho mais à esquerda Ele sempre vai estar nessa posição então na árvore da esquerda da direita eu tenho esses nós tem um elemento mais à esquerda não é o 58 por que existe alguém à esquerda do 58 não é o 26 Porque existe alguém na esquerda do 26 é o 25 porque não existe ninguém à esquerda do 25 então 25 é ideal sucessor voz o que que eu faço eu pego conteúdo do sucessor

lógico e substituto o nosso Eu quero remover bom então aqui o quanto eu uso que era 24 virou 25 só que aí você vai ver tem duas vezes o novo 25 o que que eu faço eu removo 25 da árvore da direita eu sei que esse 25 ele possui no máximo um filho então ele vai cair ou no caso um ou no caso dos que a gente viu nos slides anteriores e nesses casos Ele simplesmente ou removo ou simplesmente remova um nó ou é o substituto pelo único filho que ele tem eu sei que esse

algoritmo ele não vai entrar em loop infinito qual seria a opção dois teriam utilizar o predecessor Lógico predecessor eu aquele que vem antes de umdeterminado nó na sequência ordenada nesse caso seria um vírus Ele é o note vem antes do 24 como eu acho ele ele é o nome mais à direita da árvore das cartas então procuro na árvore da esquerda e veja Quem é que tá está mais à direita é esse não porque tem alguém na direita dele é esse não porquê a receita dele é esse é porque porque não tem ninguém na direita

dele tá então o que que eu faço os mesmos Passos primeiro substituto conteúdo depois que substituem o conteúdo vão ter dois nós iguais e eu removo 20 tá qualidade esquerdo então removeu 20 nesse caso cairia no caso um ele não tem filhos significa só remover o nome bom Então nesse nosso algoritmo de nesse nossos algoritmos depois que se ação e emoção o número de comparações é proporcional à altura da árvore o que que acontece em árvores degenerados que são aquelas árvores muito não-balanceadas você já tem pouquíssimo balanceamento como essa daqui que é basicamente uma estrutura

linear só tem um sucessor um perder sensor nesse caso o número máximo de comparações vai ser a quantidade de nós porque tem apenas cinco nós eu vou fazer cinco comparações isso quer dizer que eu perdi aí algumas das vantagens de se utilizar uma árvore então em aulas posteriores eu vou falar sobre Como eu posso fazer para manter uma árvore balanceada para garantir que eu não vou perder Aí a eficiência nas buscas e se ações e remoções e vamos agora falar sobre percursos e muitos algoritmos que nós vamos estudar nós vamos precisar percorrer os nós de

uma maneira sistemática de visitando cada ló apenas uma vez aí só que a gente vai chamar de percurso Existem três tipos de percursos mais comuns em árvores binárias estão percurso em pré-ordem o percurso em pós-ordem e o percurso em yordi ou em ordem vamos falar sobre cada um deles Oi tá primeiramente vai entender Um percurso saiba que o Nossa esquerda pelo menos esses percursos canônicos filho da esquerda umdeterminado nó Ele sempre vai ser visitado antes do filho da direita tão esquerda sempre antes da direita e o que os termos pré pós e in significam é

um de uma raiz vai ter visitado no percurso pré-ordem nós vamos visitar a partir da raiz primeiramente o próprio na raiz depois a gente olha a esquerda EA direita então isso quer dizer um pré significa raiz vem antes da esquerda e da direita no poste de novo esquenta vai vir vai vir sempre antes da direito o que que eu posso vai significar que a raiz vai ser visitada depois de todo mundo em outras palavras a partir da raiz Nós visitamos primeiramente nós da esquerda E depois o nota direito e nós concluímos visitando na raiz então

a raiz ela visitada depois e o o Sporting em ordem ou em ordem Nós visitamos primeiramente o nome da esquerda depois Visitamos o nó Raiz e nós concluímos visitando o nó da direita o percurso sem ordem então ele vai retornar para gente Qual é a sequência ordenada dos elementos dado que os menores estão na esquerda você visitar os primeiros depois o nosso raiz que é maior do que os nós da direito vamos Verificar como são os percursos nessa árvore pequena aqui vamos começar com percurso pré ordem no percurso pré-ordem A partir da raiz Nós visitamos

primeiramente a raiz então aqui o 20 eu coloquei diretamente na saída porque porque eu estou visitando imediatamente o jeans e daí eu subo para o lado esquerdo ao seguir para o lado esquerdo eu chego nessa árvore aqui e nessa árvore quem o visita o primeiro a raiz porque porque o pré-ordem então o 18 veio para saída porque eu Visitei primeiro a raiz e depois é osso e para essa árvore aqui tem apenas o nosso esse como tem apenas o nosso sex é ele que eu estou visitando como não tem mais filhos aqui a gente volta

para esse 18 e nesse 18 a gente já visitou ele já visitou a esquerda então a gente precisa visitar a direita e seria o nosso 19 então Visitamos o nosso é nosso dito isto visitamos essa árvore aqui inteira Visitamos o nó Raiz e agora nós passamos para a árvore da direita então está aqui abri da direita quem eu visito o primeiro a raiz que é o 58 Então vem aqui o 58 e assim sucessivamente visito essa árvore aqui os arrays ao 26 e depois essa árvore aqui com os arrays ao 25 e essa última subir

abre aqui para os arrays é o 30 e isso conclui o percurso pré-corte e no percurso pós-ordem o que é que eu faço eu visito primeiramente a por esquerda depois da direita e depois da raiz então eu cheguei na raiz não visito ela visito aaaaaa sob a verdade Querida cheguei no 18 não visito Ele visita ao subir a árvore das quinta cheguei no 7 ele é folha tá ótimo êxito ele daí eu volto aqui para essa árvore aqui que é o 18719 só que eu não visito a raiz eu visito a subir a vida à

direita ou seja o 19 bom e depois eu visito 18 por quê Porque eu já Visitei a esquerda direita só falta a raiz e daí eu não não visito ainda novinhos sigo para árvore da direita e faça os mesmos Passos e no percurso em ordem em ordem no começo da raiz mas não visito a raiz visito a subir árvore da esquerda que é o 18 é uma raiz da sub aba esquerda mas não visito ele porque porque tem filho a esquerda enquanto os sete que é folha então coloca o sexo depois de visitar o set

eu não passo para a direita com meu filho anteriormente não pós-ordem eu visito a raiz e depois de visitar a raiz aí sim eu visito 19 pe Então isso que eu quero dizer quando eu digo olha existe a esquerda depois da Raiz e depois à direita Acredito que tenha ficado Claro que tem esses percursos significam e essa ideia de percurso é o que conclui a aula de hoje espero que tenha que vocês tenham entendido se não tiver entendido alguma coisa Eu recomendo que deem uma olhada nessa vídeo aula novamente antes de prosseguir para a próxima

um forte abraço e até a próxima ao e o E aí [Música]