YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Portuguese, Brazilian subtitles

← 05x-01 Trees

05x-01 Árvores

Get Embed Code
3 Languages

Subtitles translated from English Showing Revision 1 created 01/31/2013 by Lucilia Figueiredo.

  1. Bem vindo, masi uma vez, a outra chance de praticar suas habilidades de programação.
  2. Hoje vamos dar uma olhada em um problema que é importante para dispositivos físicos,
  3. como calendários de uma escola, ou catálogos de telefone, ou qualquer índice ordenado.
  4. O problema de que vamos tratar é como organizar
  5. e fazer busca em informação ordenada.
  6. A abordagem que eu quero adotar é usar uma árvore.
  7. Já vimos árvores antes, em algu outro curso de programação.
  8. O tipo de árvore em que eu vou focar é
  9. uma que tem dois ramos em cada nível.
  10. Suponha que eu tenho um certo número de amigos, que eu quero guardar em meu calendário,
  11. ou em meu caderno de telefones.
  12. Eu poderia usar uma lista, em Pyton, para incluir esses 4 nomes, ou todos esses 4 elementos
  13. E eu poderia verificar se um elemento está na lista, em Python, usando a palavra chave in --
  14. colocando o elemento à esquerda e à lista à direta.
  15. Mas, podemos nos perguntar: "O que Python esta'fazendo por trás disso?"
  16. "Como isso é implementado, na prática?"
  17. Uma maneira de fazer isso -- e a maneira que vamos explorar hoje --
  18. é construir um tipo especial de árvore para armazenar toda a informação que eu quero ver.
  19. Vou começar com o primeiro elemento da minha lista,
  20. e fazê-lo a raiza, ou o topo, da árvore.
  21. Deixe-me desenhar o resto,para que seja mais fácil ver a árvore.
  22. Eu adicionei os elementos da minha lista -- 1, 2, 3, 4 -- a esta árvore,
  23. e os coloquei em uma ordem especial, correspondendo a como eles ocorreriam,
  24. em ordem alfabética.
  25. Então, como o J, de Jacob, vem antes de M, de Margaret,
  26. eu coloque Jacob como filha à esquerda de Margaret.
  27. Como N, de Nelson, vem antes de M, de Margaret, -- j,k,l,m,n,o,p,
  28. sim! eu me lembor do alfabeto inglês! -- eu o coloquei como filha à direita.
  29. E o A, de alice, segue todo o caminho para a esquerda.
  30. Vou construir uma árvore especial para armazenar informação, como esta,
  31. que tem várias propriedades.
  32. As 2 primeiras resumem, ou formalizam, essa intuição de ordem que vimos acima:
  33. tudo o que está à esquerda de Margaret, em todo o caminho para baixo,
  34. é menor ou igual -- vem antes no alfabeto,
  35. ou é um número menor, se eu estiver armazenando números --
  36. do que a informação armazenada no nodo de Margaret.
  37. Jacob e Alice vêm, ambos, antes de Margaret, no alfabeto -- portanto estão ambos à esquerda.
  38. De modo análogo, subárvores à direita contêm apenas informação maior ou igual --
  39. maior, mais à frente no alfabeto.
  40. Nelson vem depois de Margartet -- portanto está aqui, à direita.
  41. Finalmente -- isso é realmente importante --
  42. ambas as subárvores, à direita e à esquerda, seguem as regras I, II e III.
  43. Isso funciona ao longo de todo o caminho.
  44. Isso faz dessa 'rvore algo espevcial em ciência da computação:
  45. é uma estrutura de dados recursiva.
  46. Já vimos funções recursivas, que são definidas em termos de si próprias.
  47. Agora estou falando de uma maneira recursiva de posicionar dados, que é definida em termos dela própria.