Árvores: O Começo de TUDO | Estruturas de Dados e Algoritmos
ฝัง
- เผยแพร่เมื่อ 7 ก.ค. 2024
- Este é o final da minha Trilogia de Estruturas de Dados e Algoritmos e finalmente vou conseguir falar sobre o mais importante na matéria: árvores! Vamos de BSTs a AVLs, passando por Red Black Trees e muito mais! Se você nunca estudou sobre isso, ou não tinha entendido quando estudou, esta é sua chance!
Conteúdo:
00:00 - Intro
02:27 - Distribuição Gaussiana
05:53 - Hashing
09:43 - Todo mundo erra
10:18 - Recapitulando
12:34 - Pilhas e Filas
12:57 - Grafos
13:25 - Entendendo Redes
15:05 - Entendendo Árvores
16:34 - Heap/Memória
18:21 - Construindo Árvores
19:31 - Vantagem da Partição (log)
20:18 - Árvore de Procura Binária
22:24 - Visualizando Inserção na Árvore
26:19 - Imprimindo a Árvore Ordenada
30:24 - Procura Binária
32:01 - Complexidade de Recursos
34:52 - Pior Caso
35:47 - Red Black Trees
38:33 - Cor e Rotação
42:52 - AVL Trees
44:51 - Red Black no Mundo Real
47:06 - B-Tree e B+ Tree
48:47 - Bancos de Dados
52:46 - Intuição em Algoritmos
54:13 - Por que estudar tudo isso?
57:04 - Conclusão
Errata:
- em 12:45 eu inverto a explicação de pop e push
- em 18:03 eu falo "backslash" que é "\" mas isso é no Windows, em Linux é só "slash" que é "/" a barra normal mesmo.
- em 21:30 no código o loop vai até menor que 13 mas isso não pegaria o último elemento da lista de 14. O certo é ou ser "menor ou igual" a 13 ou "menor" que 14 pra pegar tudo.
Meus Vídeos Mencionados:
- Monetizar? Bloquear ADs? O que Fazer? ( • Monetizar? Bloquear AD... )
- Entendendo Conceitos Básicos de CRIPTOGRAFIA | Parte 1/2 ( • Entendendo Conceitos B... )
- O Guia +Hardcore de Introdução à COMPUTAÇÃO ( • O Guia +Hardcore de In... )
- O Computador de Turing e Von Neumann | Por que calculadoras não são computadores? ( • O Computador de Turing... )
- Turing Complete, Emuladores e o Chip ARM M1 ( • Turing Complete, Emula... )
- Qual a REAL diferença entre Arquivos Binário e Texto?? 🤔 ( • Qual a REAL diferença ... )
- Hello World Como Você Nunca Viu! | Entendendo C ( • Hello World Como Você ... )
- O que vem DEPOIS do Hello World | Consertando meu C ( • O que vem DEPOIS do He... )
Links:
* Red-black Trees (rbtree) in Linux (www.kernel.org/doc/Documentat...)
* Red-black Trees Animated (www.cs.usfca.edu/~galles/visu...)
Me siga nas redes sociais:
* Twitter ( / akitaonrails )
* Instagram ( / akitaonrails )
* Facebook ( / akitaonrails )
* Podcasts (anchor.fm/akitando)
Transcript: www.akitaonrails.com/2021/04/...
Podcast: anchor.fm/akitando/episodes/A... - วิทยาศาสตร์และเทคโนโลยี
Todo vídeo do Akita é aquela máxima: Se eu quiser criar uma torta de maçã do zero, primeiro eu preciso criar o universo.
Caramba, sim! 🥰
"Eu não estou fazendo um substituto pra cursos oficiais" mas a explicação é tão boa que acaba sendo o melhor substituto, kkkkkkkk
Sei de nada, sei que eu só jogo no grupo da faculdade e todo mundo diz que é MUITO melhor que o oficial, hahaha.
Com toda certeza, a didática dele é excelente, me lembra meu colega falando sobre cálculo 1, que não entendeu nada, ele me mostrou um vídeo mas a didática do professor era péssima enquanto com 10minutos de outro professor dava para entender muito melhor
Quando o Akita fala isso eu começo a rir kkkkkk. A didática dele é muito diferenciada, por mais que nao seja a intençao dele
Supletivo Acadêmico haha
Bom dia amigo, poderia me passar o links dos episódios anteriores...eu não encontrei...obrigado
Saber que o Akita doa 200% do lucro dos vídeos aumentou drasticamente meu respeito a admiração por tal ser humano.
Isso mostra que o dinheiro não está em primeiro lugar para todas as pessoas. Parabéns pelo iniciativa Akita.
akita é sensacional um cara muito admirável!
além de compartilhar esse conteudo conosco e doar monetização + 100%
cara é brabo d+++++
pois é, ele no linkedin é mó agressivo mas faz mais bem que muita gente kk
doa sim, confia
@@osdeving Eu nem ligo se é para alimentar o ego ou não. Eu quero é aproveitar o conhecimento do cara e entender algo que tive dificuldade.
baita vídeo Akita! mensagem final do vídeo merece até mesmo um novo vídeo 😀. A importância de saber o que está por baixo do .sort() no JS, por exemplo, talvez seja até mais relevante que aprender C/C++ pra quem tá trabalhando na web. O algoritmo por baixo vai variar de acordo com N fatores, como tipo de array e se estamos falando de Mozilla ou V8...
Como eu sou da velha guarda, primeiro era ensinado o funcionamento interno ( chato na época ), depois como utilizar.
até aqui? kkk
Na faculdade foram 2 anos vendo lógica, algoritmos e estrutura de dados em C/C++. Minha prova de ED foi sobre árvore AVL, e todas as provas eram no papel e caneta. Metade da sala já ficou pra trás aí kkkkkk é foda
spam é alma do negócio
Sempre gostei de C/C++ desde "criançinha piquena", gosto de saber como a máquina funciona.
Eu estudei árvores a pouco tem na faculdade e tinha entendido o conceito, mas nesse vídeo, a cada 5 minutos eu ficava pensando: " ahhh, então é por isso!", " ah... então é pra isso!". Excelente conteúdo!
Como você está trabalhando muito encima da parte técnica da produção do vídeo aqui vão meus pontos.
1- O microfone está capturando muito vibração da sua garganta. Se ouvir num bom fone, perceberá que existe um som espremido e grave junto a sua voz clara.
2- Não sei se foi proposital, mas as cores estão bem saturadas (e tenho pouquíssima saturação no meu monitor), talvez passou do ponto para ser chamativo. O que é vermelho (talvez por conta da luz vermelha que incide da direita pra esquerda de quem assiste) estão quase neon, como a capa do livro de Java.
3- Antigamente vc usava um outro enquadramento, me parecia um mid close-up com desvio para a direita (de quem assiste) e usava o seu lado direito para sobreposição de algo que gostaria de mostrar. Agora está em mid shot centralizado usando todos os cantos da tela. Era mais legal como antes rsrsrsr.
O conteúdo é padrão akita. Sempre excelente.
1. isso eu bobeei, deveria ter comprimido um pouco mais. vou rechecar o que eu esqueci no Fairlight
2. não foi proposital, tava menos saturado e menos escuro, mas quando subi no TH-cam o re-encode ele fez isso com as cores twitter.com/AkitaOnRails/status/1379434856044589063?s=20
3. dessa vez eu acabei indo um pouco demais pro meio, também prefiro um pouco mais pro outro lado.
Vou ajustar pro próximo ;)
Não estava entendendo o pq de o som, no meu fone, estar tão incomodo.
@@Akitando Só opinião dele mesmo. Achei q ficou melhor em todos os sentidos, mas que não fez diferença relevante alguma, já que q relevância ta no conteúdo, como ele mesmo indiretamente reconheceu
Como já disseram: "O jeito que o Akita soca nossa cara é diferente..." rsrs.
as vezes, eu fico cambaleando, cambaleando de tontura após o soco...hahuahuahu
Cara... Que aula!!!!! Vou sim ver várias vezes no meu tempo morto. Encontrar esse tipo de coisa for free no Brazil é difícil de acreditar.
akita, o trabalho que vc faz em pt-br, e incrivel, e conteudo precioso, e totalmente free, vc n tem ideia o quanto vc ta ajudando
Eu tinha o mal de achar que minha formação tinha sido ruim, porque os professores bateram muito em cima disso, hoje eu os agradeço.
É meio estranho mesmo, pq a gente aprende isso mas não faz ideia de como criar um clone do jogo Pong kkk
@@SuportoVc o que quis dizer foi que tive muuuita sorte. Na graduação eu tive a sorte de ver isso tudo, com uma certa profundidade: implementar jogos, implementar hash, ver ponteiros, realmente fazer aplicações com esses exemplos, ver o funcionamento do banco de dados a fundo, entender paralelismo, concorrência, programar a GPU, arquitetura de computadores e de ter tido uma boa base em Cálculo, Álgebra, Estatística, essas coisas, mas eu achava que era besteira, porque eu pensava que o mercado absorvia somente quem soubesse JavaScript, PHP, as tecnologias do momento, entre outro i(sso era eu bem mais novo e sendo super ingênuo.) Mesmo a gente fazendo linguagem de programação, fazendo árvores, implementando muita coisa, eu ainda achava que era desnecessário e que era algo trivial. Hoje vejo os vídeos do Akita e começo a rir de felicidade. De ver ele falando e eu entendendo tudo, sem dúvidas. De ver que o que eu achava desnecessário me fez um programador melhor. Espero que todo mundo um dia vire um Akita, não uma cópia, mas que tenham a mesma mentalidade de realmente querer ir a fundo. De se tornarem independentes, de irem sempre além. Se cuida irmão.
Formação em universidade pública ou privada?
@@danielpustowka5684 Pública
@@derekmartins3751 vc fez CC, brother? E possivel trabalhar durante o curso?
Akitando em Moçambique 😃
Notificação do Akita = Meu dia melhor
"Vem coisa boa aí"
Ver essa sequência de vídeos do Akita só reforça como nossa área é bonita e mudou o mundo. Foda d+ você trazer esse tipo de conteúdo aqui para o Brasil. Poucos falam sobre a importância de estudar estrutura de dados.
- Árvore = Grafo conectado e acíclico;
- Árvore Binária = Árvore em que cada nó possui, no máximo, dois filhos (e.g. left and right). Possui altura h e complexidade de tempo O(h). No pior caso, ela é skewed e h = n (i.e. parecida com uma lista com filhos só à esquerda ou só à direita), com 'n' sendo o número de nós da árvore;
- Árvore Binária de Pesquisa = Árvore Binária em que o filho à esquerda < nó pai e filho à direita > nó pai (igual pode ficar à direita ou à esquerda, fica a gosto do freguês). O pior caso também é skewed com h = n.
- Árvore Binária de Pesquisa Balanceada = Árvore Binária de Pesquisa com altura logn no pior caso. Temos as AVL e RB Trees como exemplos mais comuns, embora existam as Splay Trees que possuem uma complexidade amortizada de O(logn) também. Para manter o balanceamento, é necessário empregar rotações de nós que mexe em um grupo específico de nós onde foi chamada e tem complexidade constante (e.g. dependendo do autor pode ser chamado de zig-zag ou left-right).
Queria ter visto um vídeo assim quando estava "aprendendo" sobre árvore, muito bom como sempre
@@allansobrado1 essa foi foda kkk agora q fui perceber, provavelmente estava digitando rápido de mais, mas valeu pela correção
Fala sobre placas de vídeos. O Ben Eater tem um vídeo fazendo uma bem simples do zero. Achei simplesmente sensacional
Grande Fábio, justamente quando estou precisando de conteúdo sobre estrutura de dados. Obrigado!
Qualidade absurda, tanto no conteúdo quanto na gravação! Parabéns Akita! :D
Quando recebo as notificações de vídeos novos do Akita, já sei que terei de levar mais um tapa na cara de aprendizado e absorção de conhecimento, parabéns Akita, para min sempre vai ser referência
que video top! Obrigado por compartilhar Akita!
Obrigada por tantos conhecimentos compartilhados.
O que eu mais gosto é a velocidade da voz, com que ele expõe o conteúdo, fixa mais rápido na mente e prende a atenção.
Eu sempre vejo e revejo isso. Esse tema é excelente. Ótimo trabalho Akita!
Estou aprendendo a programar de maneira autodidata e conteúdos como este me ajudam demais! Não só pela didática, mas pela identificação que tenho com o Akita na forma de encarar as dificuldades e o aprendizado... GRATIDÃO!
Sensacional, por mais vídeos atemporais sobre fundamentos da computação, conteúdo impar!!! Ta de parabéns d+++++
@Fábio Akita são videos como esse que esclarece demais o que estava sombrio na minha cabeça, estou estudando estrutura de dados e esse vídeo triplicou o meu entendimento sobre o assunto, forte abraço !!!
Fantástico! Conhecimento genuíno!
Parabéns Akita!!! Mas uma grande obra de arte. Muito obrigado pelo seu tempo e dedicação! Mestre de conhecimento e humildade, um dia quem sabe chego lá inspirado em pessoas como você.
Me impressiona como consegue ser tão didático. Muita gratidão por vc existir!
Preciso aprender logo tudo que o Akita diz pra explicar em forma de animê, pra ONTEM! HAHAHA 😅
Ótimo conteúdo, Akita!!!
Pra quem trabalha com isso, explicando six sigma, é de chorar de emoção. Valeu!
Porra, Akita... foda pra caralho! O mundo (em especial o nosso país) tá precisando demais disso. Minha irmã tá entrando agora no mundo de TI (ela é psicóloga!), mas, com o apoio didático do marido e do irmão, o caminho tá ficando menos bruto. Em breve, mais uma visualizadora do teu conteúdo da hora! Vai ajudar muito ela, assim como tá ajudando a todos nós. Obrigado!
Como está ela hoje?
@@anonymousanonymous1472 hoje se formou num curso de humanas (letras), virou transex, esta com metade do cabelo roxo, outro amarelo.
Começei ciências da computação no início do ano e tô adorando essa série!
Só comecei a ver agora, mas já sei que vai ser mais um vídeo de qualidade!! Bela camisa do Link, mto bonita mesmo!
Parabéns Akita! Você é uma cara bacana demais. Sucesso meu caro. Continue assim. 👏🏻👏🏻👏🏻👏🏻
Mais um conteúdo ótimo! Valeu novamente Akita!
Grande Akita. Deve dar um baita trabalho fazer esses vídeos. Eu assisto até quando acho que já conheço bem o conteúdo. Além de retificar o conhecimento, sempre tem alguma coisa ou outra que eu não sei, além das ótimas referências que complementam o assunto.
Muito bom o vídeo, Akita. Me aventurei a dar aulas justamente de estruturas de dados na universidade onde me formei e sei o quanto é difícil estruturar todos esses conceitos de uma forma didática como você fez. Parabéns!
Muito massa! a colorização do vídeo ficou animal! Estou aprendendo em algoritmos na faculdade, sobre Heaps e a implementação de Arvores, mas sobre as funções de espalhamento de hash não tinha visto ainda, só a nível black box mesmo hehe. Obrigado pela qualidade Akita!
Parabens!!! Acredito q uma das maiores licoes dessa serie e a Humildade em reconhecer q se pode errar, assim aumentando sua eficacia em revisar e corrigir os erros e aumentar o seu entendimento no assunto.
Adoro seus vídeos, Akita. Eu faço Sistemas de Informação, e os seus vídeos sempre dão um refresh em assuntos que eu possa ter esquecido ou pq eu simplesmente fui um péssimo aluno.
Seu canal é um dos melhores!!!
Baita humildade no começo e muito conhecimento durante o vídeo.. mais que merece o like!! Obrigado pela aula
Trabalho na AWS - Dublin com Cloud mas quero me tornar um SDE, venho estudando estrutura de dados todos os dias a pelo menos 14 meses e o assunto do video esta bem familiar na minha cabeça. Vc é o cara, explica muitissimo bem de uma maneira que me faz re-ver videos tecnicos com animaçao. Parabêns por mais um conteudo top!
É mano! Vc tem o "dom" para ensinar. Parabéns 👏🏽👏🏽👏🏽
9:54 até 10:18 Lição extra valiosa que quase ninguém fala. Parabéns Fabio !!!
Mesmo já sabendo sobre o assunto do vídeo eu assisti o vídeo completo muito bom o seu trabalho Fabio :)
Estudei e aprendi isso na faculdade e nos livros, mas mesmo assim quando seu vídeo foi recomendado eu assisti os 3 minutos para ver a qualidade do conteúdo e... me surpreendi! Ansioso já para assistir os outros da série no tempo livre.
Grande Fabão!! Adoro seus vídeos!
Vou começar a ver estrutura de dados no curso, que vídeo fantástico!
Massa demais Akita, tu fala rápido pra carvalho, joga informação pra dedéu e no fim a gente entende.
Parabéns.
Acho que é uma das melhores introduções a algoritimos que vc pode ver
Mesmo eu sendo de um perfil mais de Humanas o Akita consegue me deixar intrigado com tanta explicação puramente lógica e matemática.
✌️💪
Eita...mais um super vídeo.
Estou atrasado no seu conteúdo Akita, ainda não finalizei o anterior hahaha, mas esse já irá na sequência rsrs.
Obrigado.
Muito grato, Akita.
Akita, muito obrigado por isso!
Top de mais.. parabéns akita
Realmente dos 3 episódios esse foi o que mais me agregou conhecimento... coisas que eu estava delegando para serviços esternos do programa agora posso explorar melhor isso... não tão raiz mais com mais foco no que procurar ... obrigado
Não, Akita!
Você não está fazendo um substituto de cursos acadêmicos.
Você está, mesmo que não queira, dando aulas muito melhores do que a maioria das faculdades por aí.
Obrigado por compartilhar! Você é foda!
concordo com o que voce disse
Fantástico vídeo, me lembrou muita coisa quando estudei sobre grafos em SIG, pessoal que estuda trânsito em cidades adora estudar formas de melhores caminhos entre os nós, os GPS fazem isso. Quando ouvi que estava explicando sobre os grafos pensei que também iria falar sobre o algoritmo de Floyd-Warshall e sobre o algoritmo de Colônia das Formigas. Obrigado por mais esse excelente vídeo.
Excellent communicator. 👏👏👏👏👏👍
Obrigado, Akita!!!!
Errar faz parte do processo e o que aprendemos com os erros é como não fazer aquela coisa!!!..... Akita e seus vídeos sempre com temas interessantes, foda e camisetas show!!!
Nossa minha mente fez varias operações de rotação e balanceamento de varias peças do quebra-cabeça se encacharam, deu uma visão muito boa da coisa e sua aplicações praticas, muito obrigado, vou estudar mais estes temas
Kramba, muito bom, deu até uma nostalgia, trabalhei muitos anos com mumps (so + linguagem + bd) nele tudo é armazenado numa estrutura de arvore balanceada + matriz esparsa, existe até editores de blocos pra vc corrigir a estrutura na mão qdo for preciso, e os comandos da linguagem fazem tudo, carregamento do programa, gravação do banco de dados etc, algumas sabores do mumps se tornaram banco de dados especializados, e recentemente descobri que algumas versoes do GT.M (mumps open source), se tornaram NoSQL databases (yottadb).
Hora da overdose de conhecimento! Obrigado mestre Akita, ótimo vídeo. Justamente no momento em que estou estudando estrutura de dados, hahaha!
Parabéns Akita!! eu aprendi mais com seu vídeo, do que 1 ano na faculdade.
Você explica rápido, e tem uma didática excelente.
Muito obrigado pelo vídeo 🖖
Que video incrível, realmente vale a pena se aprofundar nesse tema
Show mestre Akita!
Parabéns por fechar a série Akita. Ao teu ouvir dá uma vontade de tentar sair implementando tudo, mesmo sem saber.
Obrigado por nos estimular com assuntos teóricos denso deixandos os mesmos mais leves, nesta época de pandemia é um ótimo passatempo. Provavelmente eu que não sou da área não teria contato com estes fundamentos. Virei a chave aqui não sei se AVL ou Red/Black mas vou tentar seguir esta tree. Abraço
Cheguei aqui de paraquedas e vou ficar por aqui nesse canal mesmo. parabens mano.
que vídeo foda, parabéns Akita
Akita, em pouco mais de 57min vi neste video o que demorei mais de um semestre para ver na faculdade de Ciência da Computação, base boa...prédio bom, base ruim....prédio fraco. Isso me fez relembrar assuntos como métodos selection sort, inserction sort, quick sort, bubble sort e etc. Akita, gostaria muito de um video sobre Banco de Dados, funcionamento de indices e otimização de buscas dentro de uma base de dados. Vlw obrigado, te admiro muito por todo o conhecimento que tem e repassa. Este é o seu legado! Abco.
Parabéns pelas explicações! e por ajudar outras pessoas com a doação, sucesso!
Eu sempre soube que as coisas são muito maiores e mais complexas do que nós imaginamos, e para um iniciante (meu caso) é fundamental saber pelo menos que essas coisas existem, toda vez que eu vejo um video do akita eu tenho mais certeza que estou fazendo tudo errado ( ou de um jeito ingênuo) kkkkkkkkkkkkkkk
Melhor canal de tecnologia, muito bom Akita😃👏👏
esse akita é o cara, sempre genial explorando os assuntos. Ja assisti videos dele com papel e caneta na mão kkk
Esse é meu vídeo favorito kkk, é impressionante como eu assisto varias vezes e é como se fosse a primeira vez
Ai sim hein, que imagem top, qualidade do vídeo está demais 👏
O cara nem bebe água enquanto fala , muito conteúdo estou aprendendo bastante.
Muito show, obrigada por esse baita conteúdo! :D
A melhor notificação, ja chego no like pois o selo de qualidade é padrão Akita.
Quase cai da cadeira quando vi seu video no feed kkkkkk
Muito bom!
Muito bom!!!!
A qualidade do video ta animal, melhorou muito!!
Aula excelente!!! Parabéns!!
primeiro, mto bem escolhida a camiseta com a triforce p encerrar a trilogia.
totalmente apoio os videos sobre garbage collector, os numeros pseudo-aleatorios e qualquer um q vc fizer. seu conteudo eh incrivel. parabens.
qto às árvores, n sabia q tinha tanto de arvores na criação de indices de banco de dados e mta coisa do q falou.
aula maravilhosa demais e c ctz vou assistir mtas vezes.
obrigado demais. parabens.
alguém entendeu a referência do Triforce ;-)
Estou fazendo estrutura de dados Árvore na faculdade e em poucos minutos você me explicou oq o meu professor passou quase um mês explicando na teoria, que não vale de nada sem a prática do mesmo.
Muito obrigado Akita vc é mil
Impressionante. Vi o vídeo pela primeira vez, mas se visse há 2 anos atrás não iria entender tudo. Hoje consigo dizer que entendi tudo(ou quase) que o Akita falou e consigo enxergar que o q foi dito foi só a base e tem muito conteúdo por trás dos conseuitos.
Minha inspiração diária!
Excelente conteúdo como sempre
Eu tinha desistido de estudar estrutura de dados, e hoje eu ganhei vontade de retomar e derepende esse vídeo !!!
-eu: pronto akita vai me salvar kkk
É os vídeos do Akita não da pra assistir no 1.5, é muito legal mesmo. Em velocidade normal ainda tenho que assistir umas 3 vezes. Obrigado pelo trabalho Akita.
Obrigado pelo conteúdo 👍👍👍👍👍
Como sempre, uma aula, obrigado veio.
Sensacional esse cara. Isso é alguém contribuindo para o progresso do país. Para a melhora da sociedade e do mundo. É uma outra mentalidade, outra cultura.
Eu amoo seu Canal Akita❤
Graça a playlist começando aos 40 eu com 38 anos resolvi começar minha segunda graduação, desta vez no que eu sempre quis mas era preguiçoso demais pra começar. Seguindo com uma bolsa do educa mais Brasil consegui 73% de desconto na mensalidade e em maio começo no curso de Ciência da Computação. Obrigado mestre Akita. Seus vídeos me ajudam muito a pivotar na carreira e sair da zona da preguiça ou melhor de conforto.
Saber que o Akita doa 200% do lucro dos vídeos aumentou drasticamente meu respeito a admiração por tal ser humano. Muito bom o cara fazer o que gosta. Lindo e espetacular. Quando eu crescer (não no youtube rsrs) quero ser assim. Grande exemplo.