Árvores: O Começo de TUDO | Estruturas de Dados e Algoritmos

o Olá pessoal Fabio Akita no final eu acabei me empolgando um assunto de algoritmos e estruturas de dados eu não queria continuar porque dar bastante trabalho fazer esse tipo de Episódio mas já que cheguei até aqui me senti na obrigação de falar da estrutura de dados que eu considero a mais importante da matéria árvores outros os vídeos acabaram trazendo muita gente nova que eu acho que não entendeu a proposta do canal eu não tô fazendo um substituto para cursos oficiais de faculdades e eu nem tenho intenções de parecer que seja só tô discutindo assuntos que

acha que são importantes que iniciantes procurem estudar por conta própria E para isso ele precisa pelo menos saber que esses assuntos existem e por que são importantes para quem não sabe o canal não tem fins lucrativos eu não tenho peito uns nem patrocínios de nenhum tipo nem vendo nada e tudo que é arrecadado com Edson eu faço doação de 200 por cento quer dizer eu pego o que a recado e dobre do meu bolso para outros projetos de educação sem fins lucrativos vejam meu vídeo acima explicando e não é mais sugestões de projetos por e-mail

contato a roupa Cold malha 42.com como eu faço os vídeos nas minhas horas vagas e como desde o fim do ano passado meu volume de trabalho aumentou drasticamente tem sobrado bem menos tempo para me dedicar infelizmente não é porque tá jogando muito vídeogame meu pobre PS5 tá pegando pó desde que comprei e eu sou meio das ideias e decidir justo fazer vídeos de 1 hora de duração trabalhosos de editar e obviamente cometi erros para lá e para cá desculpem por isso mas lembre que o relato os principais nas erradas na descrição e até mesmo no

vídeo seguinte por outro lado acho bacana que vocês estão prestando atenção e notando esses erros e só para variar o comecinho o Episódio de hoje vai ser pro faladas erradas do episódio anterior apesar de para algumas pessoas Parece coisa pequena é importante eu explicar o jeito correto porque se você entender completamente essa minissérie de 3 episódios talvez começa a enxergar programação e código de uma forma diferente e mais do que isso que cometemos faz parte do processo Então vamos lá Oi [Música] é um erro besta mais importante é quando eu falo sobre a função de

hash para o nosso exemplo de hash table eu sou o primeiro a dizer que as pessoas não devem achar que tudo é uma distribuição gaussiana ou normal no mundo porque não são e eu mesmo cometi o erro de fazer isso vamos entender rapidamente porque isso é importante é aproveitar para fazer umas tangentes eu não vou explicar estatística porque eu não me acho pessoa mais adequada mas todo mundo já deve ter visto a distribuição gaussiana ou normal todo tipo de evento independente pode ser gaussiano por exemplo a altura média da população faz de conta que se

medirmos a altura de 100 pessoas 80 voltarmos 1,60 12 vontade mais perto de um metro e meio ou 1,88 entre o metro 41,90 se colocar isso no gráfico mesmo medindo poucas pessoas a gente começa a ver o tal formato de sino ou Bel Shape que caracteriza uma distribuição normal a média é onde costuma está a maioria das medições no meio e quanto mais para direita ou e vai indo as medições caem rápido essas distância a gente chama de Simas Se não me engano 65 por cento das medições vão estar em cima um noventa e cinco

porcento de cima dois e 99.7 por cento em cima três quem estudou coisa com o processo de controle de qualidade conhece Six Sigma ou sigma6 que é o famoso 99.999 66 ou 3.4 defeitos por milhão quando a gente fala 99.7 por cento parece muito bom porque nas nossas concepções mais casuais aparecem perto de cem porcento o suficiente mas não é um contrato de acelerar sigma3 99.7 por cento significa um dia inteiro fora do ar no ano por exemplo em uma indústria que produz milhões de itens por mês seria 3 mil defeitos por milhão um jeito

isopor mês infelizmente perfeição ou seja zero defeito é quase impossível no mundo real por períodos prolongados de tempo eventualmente vai ter erros humanos falhas mecânicas Six Sigma acostuma-se a meta a última coisa se lembrar a distribuições normais e médias é que ela só valem para eventos Independentes entre si quando você mensura a coisa onde um não afeta o outro como jogar dados peças fabricadas em massa altura de uma população mais um lugar onde todo mundo é errado é salários porque o salário de um em conheciam os demais não é um evento independente é o número

dinâmico que varia por diversos outros fatores outras distribuições estatísticas não se encaixa melhor como a lei de potência o Power mais não a gaussiana enfim essa tangente não tem nada a ver com a minha errada foi só algumas coisas que eu já queria compartilhar mesmo mas a errata é que na explicação sobre funções de hash eu disse que o ideal seria uma função que conseguisse devolver números que caracterizam a distribuição gaussiana mas tá errado pois significa que na média ia devolver o mesmo valor com alguns números diferentes próximos da Média por exemplo se fosse uma

função que devolve números de 1 a 10 ele poderia ficar só devolvendo o número 5 por exemplo que é exatamente o oposto do que a gente E na verdade a distribuição para esse tipo de função deve ser uniforme onde Aí sim na média ele devolve a mesma quantidade para cada número do Ranger e por isso minha confusão antes não exemplo se for uma função que devolve números de 1 a 10 e eu vou dar essa função 50 vezes cada um número de 1 a 10 DVD aparecer na média umas cinco vezes e assim balance ao

uso do meu resto e mesmo assim não deveria devolver cinco os números 15 números 2 e etc de forma fácil de prever determinístico E aí eu disse que deveria ser o mais próximo de aleatório quanto possível se mantendo numa distribuição uniforme e eu sei que isso que eu acabei de falar por si só é assunto para outro Episódio então pesquisem sobre números pseudo-aleatórios para mais detalhes depois continuando Eu usei o exemplo de função de hash djb2 e disse que não é necessariamente a melhor mas não tá correto também na realidade a djb2 é uma boa

função Se você não souber nenhuma outra como eu e o importante é os resultados caírem o mais perto possível de uma distribuição uniforme e evitar colisões ou seja evitar derrubei muito do mesmo resultado bem entre as funções de hash em mais conhecidas um exemplo de datico é o lose lose um dos piores muita colisão tem o super Fast hash que como o nome diz é rápido mas também muita colisão e tenho crc32 que é bom mas precisa de um capitalismo de um kilobyte então consome mais recursos que outros algoritmos o que pode fazer diferença no

ambiente limitado como embarcado Mas é bom para todo o resto não tenho certeza de cabeça mas acho que é usado em coisas como Protocolos de rede por exemplo eu venho explicando desde o episódio sobretudo em como tudo são números endereço de memória são números Strings é uma cadeia de bike tudo é um número um binário e hash é uma forma de conseguir números menores que representam um número maior como Extremis então um texto da Wikipédia é um linguição de bytes gigante um número usam enorme e com o resto poder é que tá esse textão com

um número menor no caso de um sha-256 da vida seria como uma etiqueta numérica de 256 bits é como o número de série de Um item o ideal é seu número único mas não é garantia e por isso temos colisões onde dois itens diferentes tipo 2 3 tons diferentes de Wikipédia poderiam chegar no mesmo resto quem já programa poderia pensar mais porque não usamos coisas como o chato 512 eles são usados para segurança Então são melhores eles tem mais ou menos a mesma função devolver um número que representa uma cadeia de bits tipo stringhi como

a chave do nosso resto e esse número costuma ser mais único quanto possível nunca vai ser 100% sempre único mas quanto maior o valor do resultado estatisticamente menores as chances disso acontecer porém a categoria de funções de hash em Como sha512 foram desenhados para ter características de segurança se usados em conjunto com coisas como sócios como eu expliquei no episódio de criptografia são mais avançados e consome o curso e mais processamento para gerar esse número portanto não são necessariamente eficientes como geradores de Chaves no hash table senão a requerimentos de segurança junto remontando para errada

eu falei no vídeo que o cálculo djb2 faz Beach with shift de 5 bits para a esquerda quer um cálculo rápido e equivalente a multiplicar por 33 em decimal e o certo seria multiplicar por 32 eu ainda cometi dois erros sobre complexidade o primeiro foi quando eu falei QNP é tempo não polinomial mas o correto que até falo depois um vídeo é que MP não determinístico e polinomial time ou tempo polinomial não-determinístico outro erro foi quando eu falei que complexidade exponencial é big ou de 2 elevado a n mas na realidade N ^ N E

falando nisso eu disse que fatorial é a complexidade mais cara mas na realidade é a exponencial porque por exemplo 15 fatorial é 15 vezes 14 x 3 x 12 tá até um mais 15 elevado a 15 é 15x 15 x15 há 15 meses exemplo de trecho que eu tirei direto da cabeça e não revisei direito eu disse que um exemplo de complexidade fatorial e implementação do cálculo de fatorial recursivo está errado eu me lembro que eu falei isso mas na realidade é o óleo mineral e não fatorial o exemplo correto para o fatorial é outra

ruins e os meio que eu traduzir direto do inglês para vendedor viajante mais do Brasil povo tá acostumada a falar em problema do caixeiro-viajante a mesma coisa na real tanto faz se você procurar em português vai ser como caixeiro mesmo mas recomendo procurar como Travel em seus mesmo que vai achar artigos muito melhores sobre esse problema tudo isso dito vamos ver se nesse último episódio da série eu começo um pouco menos Dias sempre nem os comentários tem um pouco que tá prestando atenção e corretamente corrigindo E falando nisso eu fico surpreso que tem gente que

acha que pessoas como eu não é ruim homem o que é ruim não é pouca coisa no máximo eu diria que pessoas experientes no geral reconhecem o erro um pouco mais rápido e corrigem mais rápido o experiente por alguma razão insisti no erro por muito mais tempo do que deveriam e no final todo mundo é então não fique frustrado se vocês é o problema é a mesma coisa o tempo todo para você não se perder vamos recapitular ano passado eu adaptei dois vídeos de dois canais que eu gosto do bem e ter e do game

mechanics prende primeiro para mostrar no nível do transístor um protobord como bits são armazenados numa memória e como instruções de baixo nível são construídas com transistores a verdadeira linguagem de máquina Tudo começa com instruções simples como soma construído errado passando elétrons por transistors formando portas lógicas E com isso você chega no assembly depois de propósito resolvi contar a história de Turim e vão Norma para explicar como instruções e dados populam a mesma língua hispana de bits e o que isso significa os primórdios da Computação moderna na sequência eu quis falar sobre tipos de arquivos que

todo mundo usa e ninguém entende o texto executável tudo a mesma coisa tudo um linguição the beats todo o programa todo o arquivo é nada mais que um número usam gigante em binário a ordem que esses vídeos aparecem nessa fita determina seu formato cada bit tem o endereço que a posição na fita e quando você tem sequências especiais de blitz em determinados endereços vai começar a diferenciar entre uma imagem de alta pegue o executável de Nino por exemplo Aliás quando eu falei de memória virtual nos dois últimos episódios a divisão de segmentos como steck Pierre

O data-text é específica B Linux e executáveis elf Windows e Mac um layout do segmento é diferente Ou seja um Ranger de endereço de cada coisa vai ser diferente mesma coisa entre arquitetura de 32 ou 64 bits enfim daí Chegamos na trilogia de agora onde comecei com diferentes hello world para mostrar como essa fita é usada e como a memória começa a ser organizada em coisas como steck rip e no último episódio eu mostrei como existem diferentes tipos de listas a Reis listas ligadas hash tables eu não cheguei a mencionar Mas você pode implementar estéticos

que são pilhas e que os que são filas usando qualquer uma dessas estruturas números inteiros a rede de Charlie coisas assim são tipos primitivos coisas concretas pilhas ou filas são conceitos que podem ser implementados de vários jeitos e por isso chamamos de tipos abstratos pilhas podem ser a Reis um listas ligadas onde você só tem acesso ao último elemento no caso de pilha ou seja só operações de push para empurrar um elemento para o fim da lista e pop para tirar o elemento do começo da lista finas você também tem duas operações principais uma em

que o para colocar no fim da lista e uma de kill para tirar do começo da lista são casos de estruturas que chamamos de lineares então também existem estruturas não lineares e aqui entra o assunto de grafos eu não lembro se era correto dizer assim mas um caso particular de graça o Personal é uma árvore montando grafos você vai todos os dias toda a rede seja o local de internet é um grafo um conjunto de nós ou nudes como computadores ligados por é diz que são tipo o cabo ethernet do roteador ou mesmo a conexão

wi-fi que liga seu smartphone no roteador uma rede social é um grafo onde os nomes são as pessoas os Edis são os relacionamentos entre elas e você pode ter todo mundo ligado com todo mundo ou diversos grupos ligados por algumas poucas pessoas em comum entre esses grupos se quiser entender redes sociais você começa entendendo grafos mas grafos é um assunto muito grande para explicar em pouco tempo por hoje entendo que existe essa matéria para estudar Praticamente tudo que você chama de rede pode ser descrito com gráficos por exemplo o algoritmo de como encontrar o caminho

mais curto entre dois moldes no gráfico que é o short da espécie do da costura poderia ser o caminho mais curto entre duas localizações no Google Maps ou caminho mas o relacionamento de pessoas no Linkedin e na estatística existem vários estudos sobre as particularidades de distribuição de diferentes gráficos ou redes se quiser se aprofundar recomendo livros de rede do Steven strogatz edanca lotes que inclusive tem um modelo que leva o nome deles o modelo lotes strogatz entendendo redes de forma estatística você chega nos temas desmaiou World o mundo dos pequenos os famosos seis graus de

separação acho que na faculdade o povo ensina até o modelo de Hermes e reine o tema de mundos pequenos explodiu por conta do aparecimento das redes sociais uma sílabas no começo do século 21 porque agora temos dados reais máximos para analisar o tal B deita que foi material de pesquisa para um danka um ótimo quando trabalhou no Yahoo e hoje não Microsoft daí você chega no modelos de What's strogatz ou barabasi-albert e se você acha que entende redes sociais e nunca ouviu falar deles você ainda não sabe o que são redes sociais isso tudo dito

deixa eu dar um e para trás depois de aprender a Reis listas ligadas e #bus acho que é importante fechar com árvores que por si só é um assunto bem grande também podemos ir para Beatriz que sendo honesta não lembro mais tudo de cabeça e Beatriz é o que está por trás de índices de bancos de dados por exemplo mais falando genericamente de árvores você vai ver essa estrutura em tudo que é lugar exemplo simples Basta ver se o Windows Explorer Mac Finder Hugh nominations seu files System o sistema de arquivos é inteiro baseado em

árvores diretórios e arquivos são nudes nessa árvore a raiz pode ser o seu ser: vejam um documento HTML qualquer página da web sua representação ao famoso Dom o document Object Model uma árvore onde cada nude ou entidades são elementos como parágrafos formas imagens e tudo mais E falando em objetos veja um Java da vida cuja biblioteca e toda herdada a partir da classe Object toda herança de classes e interfaces é representada numa árvore e sem árvore você não a seguir para as próximas matérias na Ciência da Computação como sistemas operacionais ou compiladores todo seu código-fonte

sejam a linguagem compilada como ser o interpretada como o pai tão o Java script passa por etapas como análise léxica depois análise sintática que gera coisas como a SP o abstract syntax Tree que a representação do seu código texto no formato de uma árvore e mesmo para entender sistemas operacionais Você vai precisar de árvores quando eu falei de memória virtual vi uns dois exemplos de segmentos importantes primeiro a i-tec que controla o estado da execução do programa A cada instrução e que é implementado como uma estrutura de dados linear de pilha já o segmento hip

pode ser gerenciado com uma árvore na realidade o chip usa uma estrutura de dados baseado em árvore chamada hip um hip pode ser uma implementação de um tipo de dados abstratos chamado fila de prioridade ou priority kill são mais tipos abstratos como a pilha ou fila que podem ser implementadas com as estruturas de o motivo como explica aí antes Se for uma Bayern jipe então é implementado usando uma binary Tree ou árvore binária a distinção é importante porque nos exemplos de faces tem o dom de html as árvores não são binárias porque cada não deu

não tem só dois elementos eles podem ter múltiplos filhos ou até múltiplos pais então são grafos mas não árvores binárias provavelmente Beatriz que eu vou explicar o que são mais para o final a estrutura de jipe é usada no algoritmo de ordenação e sempre sorte Lembra quando eu falei de clique sorte no episódio anterior tem outras nos livros de algoritmos com o merge sorte hein Serjão sorte hip sorte costuma aparecer junto mas o importante é saber que sua memória tá organizada numa árvore de procura binária uma árvore tem como característica começar de um nó de

raiz um Rute Rute para quem não sabe a tradução para raiz o primeiro nude e o primeiro usuário um livro que se chama Rute por isso quando você digita caminhos de diretórios a primeira barra ao contrário backslash a gente chama de rum o seu system no Windows você: barra é a raiz do seu primeiro HD que o Windows sempre chuva descer e para quem não sabia é porque a e b eram reservados para drive de disquete Mas enfim você vai ver esse nome Ruth ou raiz em vários lugares lembram da lista ligada é uma Street

que tem um valor qualquer que queremos guardar e um ponteiro para outro nude o prévio sou next no nosso exemplo numa árvore cada node vai apontar para mais de um load numa árvore binária em particular aponta para dois outros nudes que comumente chamamos de Left e White ou esquerda e direita uma árvore pode ser balanceada ou não balanceada numa árvore binária não balanceada Onde vamos incluindo elementos digamos tudo para a direita da árvore mas comportar basicamente com uma lista ligada com complexidade ou linear para procura Apesar do nome árvore apesar da imagem na cabeça se

algo como diretórios e arquivos numerar que pensa em árvores binárias como se fosse uma lista mesmo aqui vem um negócio que se faz e Abstrações objetivo é o seguinte tem uma lista ordenada que no geral é mais barato de procurarem mais barato de inserir ou apagar elementos do que uma Rei um lista ligada árvores aparecem Porque como expliquei no vídeo anterior se temos um problema que podemos ir particionando tipo Quebrando uma lista ao meio depois quebrando essa metade ao meio isso é característica de algum logarítmico pense numa árvore visualmente como se fosse uma lista particionada

e a raiz poderia ser o elemento mais do meio da lista e cada um dos seus filhos tem metade da lista e assim sucessivamente até o fim dessa lista mas só particionar não tem muita vantagem se ali se tiver bagunçada tudo fora de ordem e O Grande Truque é ter essa árvore com os itens ordenados porém o que significa nudes ordenados numa árvore que não parece ter uma única direção Quem é o primeiro elemento que é o segundo vão pegar essa sequência de 14 números aleatórios e organizaram uma árvore binária ordenada veja como o número

zero tá mais pa a 34 virou a raiz e mais para direita tem números maiores que 1 99 único código que eu vou mostrar minha linha hoje é da binary search Tree ou árvore de procura binária vamos começar criando abstract node parecido com o da lista ligada e do hash table é muito simples tem um campo para o número que Vamos guardar daí os ponteiros the left-hand pros nossos filhos e agora vamos direto fazer uma função nem que vai Popular essa árvore Note que eu declarei a variável Rute só com o tipo node em vez

de street node como eu venho fazendo antes isso porque eu declarei como um novo tipo com typedef então longe é a mesma coisa que se transmite node fica mais curta de escrever e agora vocês já viram no outro jeito para ver a vantagem de usar assim começamos com a rede 14 elementos números aleatórios em um novo de chamado Ruth para ser a raiz fazemos um loop para inserir todos os elementos desse Array na árvore e agora já sabemos que vão precisar de uma função chamada insert só pra ficar mais fácil de explicar e não precisa

o pênis um teres a primeira variável vai ser o endereço para raiz que começa a Lula EA função devolve o endereço da raiz de volta quando Popular tem jeito melhor de fazer isso mas por exemplo isso é suficiente chegou a hora de tentar procurar um elemento dentro da árvore criando outra função a sorte mesma coisa dos outros episódios vão passar o endereço da Raiz e o número que estamos procurando e agora vamos voltar lá para o começo do arquivo e criamos Essas funções começando pela insert que vai receber um ponteiro para a raiz e o

número que queremos inserir e retorna de volta o endereço da tal raiz começamos criando uma Instância de noite no hip com malloc associando o endereço na variável tempo de temporário daí preenchemos a estrutura com o número que passamos no campo data e inicializamos os ponteiros de leftwich para cerullo aliás importante isso é uma coisa que eu esqueci mesmo os episódios de lista ligada e resto stable se eu não inicializar os ponteiros com no explicitamente nada garante que não espaço alocado não havia bits de outra coisa e os campos podem começar já preenchidos com lixo apontando

para algum lugar aleatório bizarro Das duas uma ou ele inicializa inicializo na mão como física agora gravando Num ou em vez de maloc eu posso usar ser ok que já vai fazer essa limpeza voltando o começo é simples se a raiz ou root for nula como é o caso na primeira vez ele passa a apontar para o mesmo lugar que a variável tempo e daí termina o wi-fi e da ritani do novo multi caso contrário vamos fazer uma cláusula Elsa E começamos criando um novo ponteiro temporário chamado corrente que aponta para um longe do root

e outro ponteiro chamado perte de pai ou mãe tanto faz que começa a Lulu começamos fazendo um Loop Infinito com o raio um se a gente não fizer nada dentro desse look para sair vai ficar repetindo dentro do loop para sempre dentro começamos fazendo a variável permite apontar para qo gente tem na primeira passada do lucro é o primeiro nude que já está inserido E outro que começa aqui em dois casos se o número que queremos receber agora for menor que o número do Perry se não for cai no Elzi que é o caso oposto

se o número que estamos inseridos for maior ou igual ao dono diferente no nosso exemplo a raiz é o número 34 e o próximo da lista é 84 então ele cai no bloco de Elzi nesse bloco fazemos a variável corrente apontar para a direita dono onde atual do 34 e agora podemos ter dois casos se o nome de cuide for nulo ou se já tiver outro node nesse caso não segundo item ele ainda é nulo então Fazemos o ponteiro para a direita do nó de perde apontar para o temporário e saímos do loop dando Brittany

da raiz de novo como completar o código com o próximo item da lista que é o 15 vai ser um novo insert Passamos um root e o número 15 daí criamos um novo load tempo e para acomodar esse valor 15 Rute não é nulo então entramos no primeiro bloco Elzi variável corrente aponta para o Oi gente prá nulo entramos no ao infinito agora fazemos a variável perto de ser igual ao convite porque vamos usar para navegar pela árvore e o parents sempre vai estar apontando para o node imediatamente acima dela fica mais fácil de entender

tem deste diagrama na cabeça agora chegamos P15 é menor que o valor no nude perde que é a raiz 34 então o corrente vai ser o espaço para a esquerda Donald atual por acaso esse espaço ainda está vazio ainda vai passar seu noite 15 que acabamos de criar e tornamos o Ruth de novo e quebramos um Loop Infinito e nesse estágio temos uma lista com 34 no topo 15 na esquerda 84 na direita e o código de inserção tá completo Como testar mais uma vez com o próximo número da lista o zero começamos no topo

da função insert passando a raiz e número zero queremos um novo temporário que vai conter o zero Cut não Elo então seguimos criando o ponteiro corrente apontando para o nó de 34 e permite nulo entra no loop infinito o Comperj igual ao corrente que é a raiz como zero é menor que o permite que é o 34 ainda Fazemos o cuide-se o node à sua esquerda que é o 15 sendo corrente não nulo Então sai desse bloco e chega ao fim do guaiú como o loop infinito repetimos e agora o Perry gente vai ser o

corrente 15 de novo zero é menor que o atual permite que é 15 então fazendo conheceu node left à esquerda agora não tem ninguém lá é nulo e aonde vamos colocar o número de 0 e pronto atribuímos um left do pert 15 para ser um node temporário zero e damos return para sair do Loop Infinito eu vou acelerar aqui do lado para inserir os elementos que faltam EA árvore vai ficando dessa forma obviamente não fica bonitinho assim na memória mais cada node tem ponteiros apontando para até dois outros nudes e podemos rearranjar num diagrama para

ficar visualmente assim o importante é o seguinte começa a lendo do node mais à esquerda E vai um a direita começa até 10 depois dois 9:15 1831 E chegamos na raiz 34 continua por 39/79 vai indo até o 99 Lutaram com a lista está ordenada Antes de mostrar como fica a função Cert acho que vale mostrar como pegar de volta a lista ordenada e mostrar na tela temos três formas de Navegar por essa lista pre-order post Order em Order pre-order começa da Raiz e vai para a esquerda primeiro depois pela direita indo de cima para

baixo post Order começa do primeiro load mais à direita no caso o nome e vai subindo de baixo para cima em ordem como o nome diz é na ordem e qualquer um desses casos é simples usando recursão Primeiro vamos colocar na Man a chamada para a função em órgão traverso passando o load raiz precisamos criar essa função ela começa checando se o load passado é nulo E se for não faz nada e retorna caso contrário chamar ela mesma passando unload aí e com os nossos valores de exemplo se a gente pensar como ficaria a i-tec

do programa vamos começar chamando em ordem para o nó de 34 ela não é lula então chamar ela mesma de novo passando no de 15 acumula no topo da steck porque não retornamos ainda agora o nude continua não sendo nulo então chamar ela de novo com o próximo no olho esquerdo aqui é o do zero em pilha não está aqui de novo e quando chamarmos outra vez o nó de zero não é num então Passamos um longe a esquerda dela aqui agora é nulo e empilhamos agora a função vai receber nessa variável root um nulo

então o wi-fi vai ser verdadeiro não faz nada e retorna desempenho é da steck Voltamos para chamada anterior que vai continuar dono de zero e da Print efe na tela vai imprimir 0 e agora vamos chamar a função de novo passando quem tá a direita do luge zero e tem um novo de 2 em empilhamos a mesma coisa node não é lindo chamamos a função para o nude à esquerda do nove que é nulo já sabemos que vai empilhar entrar e desempilhar porque nulo Então vamos pular e na sequência vai dar preenche fd19 agora Tenta

achar uma função por onde a direita do 9 que anula de novo vai empilhar chegar que é num não faz nada e desempilha e acaba função Pro 9 retorna e diz empilha função do 2 também termina desempilha a chamada para o zero também acabem desempilha Voltamos para o nó de 15 Agora continua dando print F para ele imprimir 15 na sequência do 9 e chama a função para o node à direita do 15 que vai ser o 18 empilha nude não é num então chama a função para o nude a esquerda que é nulo podemos

pular porque sabemos que vai empilhar e desempilhar continua dando print A4 18 agora chama a função para o nó de 31 a direita pausa agora olha só já imprimi o 02 9.518 próximo vai ser 31 Tudo na ordem crescente ordem Nadinho esse continuar é a mesma coisa vai imprimir até o 99 na ordem se você nunca viu isso antes deve ter dado um nó na cabeça mas é justamente isso que precisa acontecer porque essa estrutura e esse jeito de operar não é intuitivo se você nunca estudou estruturas de dados por intuição você vai parar nas

listas lineares e nunca vai entender o que vem depois que são grafos ao final só de ter inserido um monte de números aleatórios na árvore de procura binária conseguimos pegar os elementos já ordenados e o mesmo resultado poderia ser obtido inserindo os números um Array e passando um quicksort da vida neles mas entenda a diferença se for considerar puramente só inserção de Novos Valores é mais rápido colocar no final de um Array porque a complexidade é o constante já na árvore vai ser o logaritmo Ou seja a inserção na árvore é um pouco mais lento

mas a comparação é injusta a complexidade de inserir elementos numa árvore de procura binária é o logarítmico porque ele já insere os elementos ordenados é uma rei é o constante para inserir no fim porque não estamos ordenando-se também quisermos o Array ordenado precisar nem alguma dar um kit sorte no mínimo uma vez no final daí vai ficar mais caro que é log-linear quando a rede estiver todo ordenado podemos pesquisar usando procura binária eu não vou mostrar código mas é assim o jeito ingênuo de procurar numa rei é fazer um loop e como padrão de elemento

elemento da esquerda para a direita até achar 88 Você vai precisar de umas dez operações comparação nessa lista para chegar lá mas tem um jeito mais rápido que só funciona se a lista já tivesse sido ordenada antes você pega o tamanho do Array e dividir por dois no caso vai ser sete daí Pega o endereço do primeiro elemento e soma pelo tamanho de cada elemento x 7 que é o elemento 39 mais ou menos no meio da lista agora com para 88 é menor que 39 não é então já sabemos que não tá na metade

à esquerda dos 39 não precisamos olhar nenhum deles só de fazer isso já eliminamos metade da lista que não precisamos nos o recursivamente fazemos a mesma coisa a direita do 39 temos seis elementos sobrando dividido por dois são três somado a posição 7 Chegamos na posição 10 que é o meio da metade da direita e vai ser o elemento 88 por acaso comparamos com o valor procurado 88 e já chegamos nele ou seja com duas operações de endereço para chegar do meio do meio e duas operações de comparação Chegamos no 88 quatro operações no total

contra os dez do jeito ingênua e menos da metade do processamento e isso porque essa lista é muito pequena quanto maior a lista mas vai ser a economia por isso tem vantagens trabalhar com listas ordenadas porém Como eu disse antes custa o n vezes logo higiene log-linear para ordenar um Array e dependendo do algoritmo pode custar espaço na memória para fazer essa ordenação um nerd sorte por exemplo acho que era um que custava mais caro em espaço extra para conseguir ordenar lembram da animação que mostrei de merd o episódio anterior vamos ver de novo tão

vendo que ele vai guardando valores aqui embaixo isso é o espaço temporário que o verde Esporte gasta para conseguir ordenar a lista de cima Então não é só velocidade de processamento para se preocupar como também espaço temporada de memória que se gasta Agora pensa na árvore ela não custa muito espaço adicional para ordenar e custa literalmente ou logarítmico tudo bem que é para cada elemento mas a complexidade é uma ordem de grandeza mais rápida que qualquer ordenação de Array e uma vez tendo árvore ordenada a procura é parecida com o que acabamos de fazer um

procura binária diarreia vamos ver voltando ao exemplo precisamos implementar a função surte que vai começar a recebendo como argumento load raiz da árvore e o valor que estamos procurando no caso 88 criamos uma variável temporária chamado corrente apontando para o root de novo queremos um look com a eu que vai quebrar se um load current for nulo e isso só vai acontecer se a gente navegar pela árvore um dos moldes tiver o valor que é procurado agora é a mesma coisa que na busca binária diarreia inserção garante que nossa árvore binária já tá ordenada como

acabei de mostrar vamos comparar o número 88 com o valor do corrente que é a raiz 34 como não é menor pula pro Elsa if como é maior faz o correntes e um novo de 84 repete o loop 88 ainda não é menor que 84 pula pro Elsa de novo e faz correntes eu longe a direita White que é o 99 repete o look e agora assim 88 é menor que 99 então vamos fazer o quê em te pegar o molde a esquerda dele o ponteiro left repete o loop agora o node que achamos não

é menor não é maior Então finalmente cai no último Elsa e pronto achamos 88 tem quantidade de comparações é equiparável a busca binária de Array ordenado ordem de grandeza Big o logaritmo porque ambos os casos estamos particionando entenda a relação inserir elementos no fim de uma é rápido o caso tem espaços vazios sobrando no final se não tiver precisa criar um novo Array maior e copiar os elementos da anterior para ela como toxicidade unilinear se quiser que a lista esteja ordenada para conseguir procurar via busca binária vai custar o log-linear de um quicksort da vida

no hashtag ou não se ordena porque a posição depende do resto da chave e a procura vai ser ó linear também então a pesquisa numa árvore binária vai ser melhor do que não há Rei lista ligada o resto tribo tudo depende de para que você vai usar a lista para guardar os campos que vem no formulário simples de cadastro qualquer está serve são poucos elementos mesmo na força bruta ingênua diferença é pouca agora para gerenciar coisas como um teste de banco de dados você vai escolher alguma coisa melhor que um hash table uma árvore binária

não chegamos no fim da história essa nossa árvore binária rudimentar é só a base o caso ruim para árvore binária da forma como implementamos e tentar adicionar uma lista de números consecutivos por exemplo Oi de novo a partir de 99 tentar inserissem como é maior que 99 vai para a direita agora 101 como é maior que 99 Vai para os ensino Marques em vai para a direita vamos lá 102 mesma coisa quando chegar no 101 para trás direita isso continuar adicionando Olha como ficou nossa árvore parece um galho seco esperando para cair ficou basicamente com

uma lista ligada que é o pior caso pior caso Porque sendo praticamente uma lista ligada à complexidade para procurar deixou de ser o logaritmo e voltou a ser linear ou seja para achar um último elemento vai precisar comparar com todos os outros anteriores uma árvore assim é desbalanceada a gente precisa rebalancear e distribuir em outros Galhos dessa árvore o que vimos até aqui é chamado de árvore de procura binária o Bayern Street 3 cujo acrônimo é bs.to que costuma ensinar depois é como Balancear essas BS texto e uma das formas de fazer isso é o

que se chama de árbitros ou Red Black Tree antes e com ele os comentários eu vou falar sobre a velhos já já calma aí uma das razões de eu querer pular esse assunto é porque realmente não tô com vontade de explicar nem a linha de como se faz inserções de uma árvore Red Black é muito detalhezinho vai dar um puto a tampa editar indo linha linha num vídeo vai ser maçante para caramba então recomendo que vocês procurem o código em qualquer linguagem teste nem a linha na máquina de vocês em vez disso eu vou fazer

diferente aqui o que muda numa árvore binária normal e numa Red Black para começar o nome da árvore vai conter um campo extra de um bit que pode ser 0 ou 1 tanto faz se você chama de 0 the Red Sun The Black ou vice-versa mais uma regra Inviolável aqui um nome de raiz é sempre preto por padrão todo no de novo que fomos criando vai começar sendo da cor vermelha mas depois de inserido na árvore precisamos chegar a cor do pai e dos filhos porque a regra é que um nome de vermelho só pode

ter Pais e Filhos pretos se depois de se não tiver assim precisamos repintar os nudes para encaixar na regra parece estranho mas você vai entender Além disso todo longe no fim da árvore que você pode chamar de folhas ou Unix e terminaria com os ponteiros leftwich sendo luz vão apontar para um load de serviço que muitos no meio ali hã como nude um pernil você pode chamar como quiser mas é um longe que serve só para os ponteiros left-right dos últimos nudes não serem nulos e seguir a regra das cores como é todo ponteiro todo

mundo no final vai só apontar para esse noite mas no diagrama para ficar mais bonito vai aparecer aqui cada um tá apontando para um load extra só lembre que é tudo o mesmo node tenho no final uma das razões de ter esses novos no final é a regra que se contarmos todos os novos entre a raiz esse nulo deve sempre ter o mesmo número de nudes pretos e na prática Isso só vai acontecer se árvore tiver altura balanceada para entender isso de balanço considere nossa árvore binária de exemplo conseguem ver como alguns Galhos pendem mais

é só os 90 ou 15 Pena em tudo para a direita dono de 84 tem de tudo para a esquerda para a árvore fica balanceada precisamos fazer uma manutenção movendo o ponteiro de lugar durante a inserção lembra aquela ideia de fazer Swap de ponteiro que eu falei no episódio anterior é parecido aqui suaves ou troca são operações rápidas só muda uns 2 ou 3 ponteiros de lugar independente da quantidade total de nudes então operação de complexidade ou um constante essa operação em árvores não é exatamente um Swap mas sem uma rotação e isso tudo dito

Vamos dar um exemplo visual com a mesma lista de números do exemplo mas agora inserindo com o algoritmo de inserção de uma árvore Red Black o 34 é ais por isso ela é preta por padrão e seus ponteiros the left-right vão apontar para criminoso denu lutenil o próximo número é 84 que por padrão entra vermelho igual na árvore binária vai para a direita porque é maior que 34 o próximo número é 15 é menor que 34 a esquerda e também é vermelho por padrão até aqui tudo bem mas agora vamos inserir o número zero pelas

mesmas regras é menor que 34 menor que 15 Então vai indo para esquerda e inserir um número de 0 vermelho mas a regra é que um nude vermelho não pode ter um pai vermelho como de 15 em cima dele aqui começa o trabalho de zeladoria recolorindo no de 15 e o molde 84 para preto e agora a regra foi satisfeita sobre o caminho mais curto que eu falei olha só quantos números pretos tem entre 34 e uniu embaixo do zero 34 é preto um 15 é preto 20 vermelho continua dois e mil é preto três

conseguem ver que qualquer outro caminho continua sendo três nudes Preto Então as regras continuam insatisfeitas vamos continuar tentando inserir um número 2 e aqui a coisa ficou diferente olha o que aconteceu tentamos inserir o número dois pela regra da árvore binária é menor que 34 Então vai para esquerda é maior que zero Então vai para a direita agora a árvore ficou de E aí porque vai começar a temos dois nudes vermelhos um atrás do outro e o irmão do nolo de zero que é o ponteiro para a direita do nome de 15 tá vazio Isso

não pode acontecer a ideia é que os moldes mais para cima tem um left e White preenchidos imitando ponteiros números antes de chegar nas folhas precisamos fazer a tal votação primeiro rotacionamos para esquerda subir unload dois na árvore descemos no de zero para a esquerda depois quando achamos para direita Subimos o nó de dois para o mesmo andar da 15 descemos o 15 para a direita finalmente repitamos o node 2 em 1 nude 15 e pronto voltamos a cumprir todas as regras do jogo nenhum load vermelho tem pai ou filhos vermelhos e todos os caminhos

longe 34 até os números continuar tendo o mesmo número de noites preto no caso três vamos continuar os números 99 79 80 e 81 ser inserido do mesmo jeito que na árvore binária Mas agora vamos ver 1/89 mesma coisa é maior que 34 vai para a direita é maior que E tu vai para a direita é menor que 89 vai para a esquerda e sendo o maior que 88 vai para a sua direita e Alerta temos dois nudes vermelhos um atrás do outro e o irmão do 88 ou seja o ponteiro para a direita do

89 está vazio hora de rotacionar começa a rotacionado para a esquerda daí 89 passa seu pai de 88 e filho de 99 outro acionamos para a direita e 99 passa a ser filho de 89 irmão do 88 agora vamos ver pintar 88 89 e estamos cumprindo todas as regras de novo consegue ver que se compararmos com árvore binária de antes agora aparece visualmente mais balanceada Ou seja todos os moldes antes do andar mais baixo tem ambos os ponteiros leftwich preenchidos sem buracos sobrando vamos continuar os outros números até o fim da lista sem parar mais

continuamos com 1831 e 39 daí escondemos os moldes no final para ficar mais fácil de comparar olhem como a árvore Red Black e árvore de procura binária um layout bem diferente é assim que uma árvore binária balanceada se parece usando o método de Marge Black em termos de espaço Extra sendo usado é barato só um bit a mais para cada node fora os ponteiros para o nó de no no final de cada folha e mesmo esse espaço tem como economizar E eu vou falar disso já já o tempo de inserção é definitivamente mais caro mas

ainda assim é na ordem de grandeza divulgar lítico ou seja em comparação com a árvore desbalanceada um pouco mais lento mas a ordem de grandeza de complexidade não ficou muito mais caro procurar por itens nessa árvore é a mesma coisa da árvore de procura binária uma busca binária e para pagar vai ser um pouco mais lento também assim como na inserção precisa manter a árvore balanceada então toda vez precisa checar se precisar rotacionar e colorir como eu prometi Ainda temos árvores avl para comentar que chama assim por causa dos autores Emerson velski e yealands de

1962 em resumo diferente do sistema de a cor do Red Black cada longe não haverá ele tem um número de balanço que pode ser - 101 árvores e balanceada se for menor que menos dois ou uma orc 2 árvore tá desbalanceada E precisa rotacionar e recalcular o balanço embora ambos a Vl e Red Black tenha operações como complexidade na ordem de grandeza ou logarítmico a procura numa árvore a velha é um pouco mais rápido porque o Red Black ainda pode acabar menos balanceado aqui avl a avl é mais agressiva e manter a árvore estritamente balanceada

a inserção da velha acaba sendo um pouco mais cara que a Red Black para atingir isso é o sempre um trade-off se você fizer mais inserções do que procuras um red Black é melhor se o tempo de inserção não foi importante mas para você o tempo de procura por muito importante então talvez a Vl sejam melhores mais do que isso diferente dos moldes de uma rede Black são só um bit os moldes dia Vl prisão de dois Beats Extra se preocupar um pouco mais de espaço na memória Além disso os prédios Black tem Outra vantagem

dependendo da implementação lembram quando eu falei sobre números inteiros com sinal e sem sinal se a gente soubesse os números que vão ser armazenados na árvore sempre A positivo podemos usar o primeiro bit que normalmente seria para o sinal para ser acordo longe daí economizamos esse Beach a mais na estrutura de nude e só para piorar o caso do HL eu disse antes que as votações de red Black são simples complexidade ou um constante mas as inserções de avl podem ter mais rotações mais complicadas daí o tempo Varia Mais por tudo isso na dúvida a

escolha padrão acaba sendo Red Black EA velha em casos especiais que você sabe que precisa das propriedades específicas dele eu vou deixar ali em caso na descrição abaixo um documento do site da Kernel do Linux que explica mais sobre como árvores Red Black são usados no terno para fazendo os esquerdo luz de ai o deadline ecf a fusão arbitres para rastrear requisições arbitre Você lembra que são red Black Tree o pacote de CD e DVD faz o mesmo o código de timer de alta resolução usa arbitres ifilesystem ext3 as três diretores em uma arbitre via

mais o áreas de memória virtual usam arbitrais seu node.js todo servidor com aí ó síncrono por baixo usa um Apple do Linux rastreamento de descritores de arquivos Chaves criptográficas instalador de pacotes de rede usam árbitros só para comparar lembro o nosso código de exemplo de procura no árvore binária vamos ver como essa documentação do site da Carne sugere fazer e olha só é bem parecido né as mesmas comparações para esquerda para a direita o quando encontra um node meu exemplo foi rudimentar mas a estrutura básica é a mesma nos casos mais complexos não sei porque

as linguagens mais populares interpretadas não tem árvores braid black que vem por padrão nas suas bibliotecas Bom dia causa de verdinho porque a cinco multas estruturas de dados seria o melhor implementadas em C ou C plus plus do que em Alto Nível como javscript o Python a classe STD map do seu rosto implementa árvores redblack Assim como as classes 371 trimep do Java se for uma linguagem compilada como Gol Rust Você pode baixar do que tiver alguma implementação que funciona igual velocidade porque são compiladas Mas tirando já vem se pôs não seja nenhuma outra que

já vem embutida se alguém souber mande nos comentários mas lembrem-se árvores Red Black eavl tem como objetivo chegar numa árvore de procura binária como no nosso exemplo anterior Só que balanceadas os algoritmos de inserção que usam o sistema de cores o balanço e votação servem para nos dar uma árvore balanceada que vai oferecer o menor tempo médio de procura binária mas o que vimos até agora continua sendo uma árvore de procura binária com o novo disse que só tem um valor e 2 a compra esquerda e outro para a direita depois disso ainda existe abitri

que é uma estrutura de árvore que também é alto balanceada ou seja durante a inserção e remoção de nudes ela faz a zeladoria desse rebalancear Mas em vez de nudes que só tem dois filhos no bitri os nossos podem ter x filhos mais que 2 e mais coisas que não vou detalhar aqui a definição vem do livro do que no fio e todo mundo usa a mesma então pesquise sobre bikes como lição de casa visualmente é algo como nessa imagem do lado ainda uma árvore idealmente o balanceada mas com mais filhos por nudes e indo

mais longe Chegamos na Bíblia os trens que você pode pensar como Beatriz Mas onde os nudes não contém os valores em si em vez disso aponta para folhas e esses nudes folha é que vão ter os valores que você quer armazenar os nudes pais vão ter só as chaves que identificam esses valores e essa árvore que você vai ver em tudo o armazenamento orientado a blocos eu tô pensando em fazer um episódio falando sobre blocos de armazenamento é por isso que se você já brincou com a WS o Google Cloud ou azure já deve ter

visto termo Block Storage para identificar HDs virtuais por agora só entenda que é isso que faz biplas trens serem ideais para coisas como files System e bancos de dados tudo que você imaginar que armazena dados em discos provavelmente é uma Bíblia esfriou derivação exemplos os pais assistem de Linus como Raiz zfs e este quatro o ntfs do Windows a PFS dos médicos a maioria dos bancos de dados relacionais como db2 ficou server Oracle se com Light E por aí vai é tudo bíblico lustres falando em bancos de dados para entender como os dados são armazenados

em disco você precisa entender bipp lustres se você já usou qualquer mais 51 possuímos da vida vai lembrar que tem a boa prática de sempre criar índices para melhorar o tempo das suas pesquisas e se você leu está aqui o suficiente também vai lembrar que o povo fala para não sair criando isso para tudo que é lado como se não houvesse amanhã se não vai acabar com a performance Aí você fica sem saber o que fazer então cria ou não cria índices se você entendeu a ideia de pegar uma lista e colocar numa árvore de

procura a binária balanceada EA ideia de regem darrechi table do episódio anterior meio que já entendeu uma parte da charada O que são registros de um banco Pense como se fosse uma strict de ser como as que usamos em todos os exemplos até agora Agora pensa em gravar uns Beats de instâncias district no disco em vez da memória uma tabela de banco de dados grande pode ter milhares ou milhões de registros seria bem lento sair procurando registrar registrar como numa árvore ligada mesmo se for uma árvore diferente de dentro da memória pensa que não disco

mecânico você precisa sair caçando bits em trilhas no disco e ficar caçando endereços assim ia ser bem demorado mas se não tem nenhum índice é isso que vai acontecer mesmo pelo menos fazendo uma busca binária ou Tô dando uma boa parte de registro que não precisa vasculhar mas em Milhões de registros mesmo com busca binária mas ser bem devagar é o que muitos já devem ter visto nos seus bancos de dados favoritos quando a pesquisa cai não tem bolskan quando você procura por chave primária ou por um campo indexado é bem mais rápido pense no

índice como uma segunda árvore uma between que a tal árvore onde cada noite pode ter vários filhos e é alto balanceada ou seja inserções de lições rebalancer em uma árvore via operações como votação ela fica mais compacta porque é como se fosse uma cópia da sua tabela só que só com os campos indexados imagina num exemplo simples de árvore de procura binária se eu fizer uma pesquisa para achar todos os salários maiores que 10.000 depois de eliminar a metade esquerda da árvore agora temos AIDS dos endereços de onde esses registros estão na outra árvore no

disco e podemos buscar só elas E por que não é bom criar um montão de índices pense em inserindo uma tabela como em a árvore Red Black para manter a árvore balanceada para ser a pesquisa você precisa repintar eu vou estacionar toda hora cada em si da sua tabela é como se fosse uma árvore dessas quanto mais índice estiver mais caro fica inserir em várias delas porque você precisa inserir na tabela própria mente Dita e depois atualizar cada um dos índices que você criou E esses são bons para ser as pesquisas mas o custo é

aumentar o preço de operações de insert update e delete this de qualquer forma o objetivo de hoje não é detalhar como bancos de dados funcionam mesmo porque eu mesmo sei tudo de cabeça mas só de saber que seu sistema de arquivos Seu banco de dados usam uma implementação de Bíblias triste e que os índices que tornam suas pesquisas mais rápidas suas inserções mais lentas provavelmente é uma implementação de bitrens já vai ajudar você a procura mais material para estudar uma última coisa é não confundir Beatriz combinar 3 ou árvores binárias SB the balance between e

balanceadas e balancear árvores tem um custo as Tais operações de votação por exemplo mas no fim do dia embora você pense visualmente numa árvore como uma hierarquia na verdade é uma lista ordenada como um Array ou uma lista ligada mas estruturada de forma diferente de forma não linear a complexidade de cada tipo de algorítimo em cada tipo de estrutura de dados tem complexidades diferentes de processamento e uso de recursos Alguns são rápidos mas consome mais memória outros são mais devagar na inserção mais mais rápidos na procura casos excepcionais podem fazer um algoritmo ou logarítmico cair

para o linear ou até mesmo o log-linear outras coisas que você deve prestar atenção se você partir do zero descer sozinho é possível que talvez compreendo um pouco sobre as complexidades de manipular e procurar elemento no Array com um pouco de prática mas naturalmente chegar numa lista ligada acho difícil chegar num resort sozinho mas se por acaso e a rainha algum texto sobre particionamento e logarítimos talvez chega em algo parecido para ordenação e busca binária de um bom ânimo chegou número de sorte sozinho se você se esforçar bastante Talvez consiga evoluído a lista ligada e

a rei para hashtag bui árvore de procura binária desbalanceada que vimos hoje mas eu acho muito Improvável você sozinho sem ajuda de nenhum livro chegar na ideia de árvore balanceada e mecanismos como o hard Black a Vl o mesmo Beatriz para isso você precisa de mais literatura Especialmente porque conceito como colonização e votação não são intuitivos mesmo se você já tiver a ideia de Swap de variáveis na cabeça a ideia de colonização não é usada só em árvores redblack um dos mecanismos de garbage collector se chama tricolor marketing onde a fase de marcação de objetos

categorias a quem pode ou quem não pode ser descartado usando um sistema de três cores preto branco e cinza se você entendeu a ideia o preto já tem uma noção de tricolor marketing Talvez eu fale sobre isso depois explicar como funciona os Garbo de colectores em Alto Nível Mas por hoje eu fica a dica eu espero que pelo menos tenha conseguido fazer Vocês que são iniciantes e enxergar em um pouco mais de como as coisas funcionam por baixo do seu JavaScript Python mesmo que não usem diretamente no trabalho reserve um tempinho para estudar o básico

de ser Especialmente porque se vocês se empolgaram em seis e posto vão ser úteis caso um dia que irão usar uma biblioteca descer dentro do JavaScript e sim isso é possível e e como muitas bibliotecas são realmente feitas o nosso linguição de bits sozinho é só isso bits um atrás do outro mas quando definimos estruturas de dados começamos a dar forma a pedaços de Bis delimitamos essas estruturas pelo tamanho de cada primitiva como inteiro de 32 ou 64 bits e os endereços em que ela se localizam nesse linguição os bico sozinhos não significam nada só

quando o nosso programadores de fim a cada pedaço é que ela começa a ter sentido Por exemplo uma sequência de inteiros um atrás do outro pode ser um arrepio só de números mesmo ou de letras por humano stringhi e quem decide qual é qual sou eu o programador um pacote de bits que tem codificado o número que é outra posição no linguição é um node esses nomes podem ser organizados comunistas ligados hash table o árvores Daí vem o problema de Navegar por esses pacotinhos de Bis e o jeito simples é sequencialmente como não há regra

mas logo a gente vê que isso é limitado daí saímos pulando de endereço para endereço de nudes Mas isso é lento e complexo Aí temos que inventar formas de Minimizar esse trabalho e Chegamos em algoritmos como de ordenação e procura E à medida que evoluímos o conceito uma árvore desbalanceada se torna balanceado uma procura que levava tempo linear virar logaritmo que uma estrutura que era simples vai ficando mais sofisticada Saímos de chips de memória atendentes de bancos de dados com a mesma categoria de estrutura o importante é mesmo se você treinasse por anos a fio

sem estudar a fundação nunca ia chegar no que vimos nesses últimos 3 episódios sozinho minha continuar fazendo programa errado sem saber porque o famoso meu programa talento deve ser meu CPU que é velho esquece que anos atrás se fazia programas que rodam mais rápido que o seu em CPU ainda mais velho então o problema não é o hardware não ser suficiente mas se você não sabe usar o máximo que ele pode oferecer e se limitasse conformar com a pelo menos roda tudo que falei até aqui é o básico cada assunto que falei tem bem mais

detalhes por trás e mesmo quando você tiver estudado tudo ainda assim não vai fazer programas bom mas ao longo do seu treino e Estudos as peças vão começar a se encaixa mais rápido e você vai começar a dar saltos maiores do que tem começou junto com você mas preferiu pular toda essa teoria pegue o livro do kormann tannenbaum em estúdio é chato para caramba mas quanto mais cedo fizer isso melhor vai ser depois E com isso finalmente Cheguei ao final desse assunto como eu disse no começo assistam essa série múltiplas vezes se você é iniciante

não vai entender vendo só uma vez e nem tem tudo aqui precisa Pesquisar mais sobre os assuntos que eu falei fazer você mesmo Esses códigos como exercício e só assim começar apreciar como as coisas funcionam se acharam algum erro no vídeo Não deixe de mandar nos comentários abaixo se curtir o vídeo deixa o joinha e assine o canal e clique no Sininho para não perder os próximos episódios Compartilhe o vídeo com seus amigos para ajudar o canal a gente se vê até mais