YouTube

Got a YouTube account?

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

English subtitles

← 05x-01 Trees

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 10/24/2012 by Amara Bot.

  1. Welcome once again to another chance to practice your programming skills.
  2. Today we're going to take a look at a problem that's important for physical devices
  3. like yearbooks in a school or phone books or really any sorted index.
  4. The problem we're going to cover this time is how to organize
  5. and search through sorted information.
  6. The approach I want to take is to use a tree.
  7. We've seen trees before in some computer science programming.
  8. The particular kind of tree I'm going to focus on
  9. is one that has 2 branches at every level.
  10. Suppose I have a number of friends that I want to keep track of in my yearbook
  11. or in a telephone book.
  12. I could use a Python list to include all 4 of their names or all 4 of those elements.
  13. And I can check to see if an element is in a list in Python just by using the keyword "in"--
  14. putting the element on the left and the list on the right.
  15. But we might wonder, "What is Python doing behind the scenes?"
  16. "How is this implemented in practice?"
  17. One way to do it--and the way we'll explore today--
  18. is to build up a special kind of tree holding all of the information that I want to see.
  19. I'm going to start with the first element of my list
  20. and make it the root or the top of the tree.
  21. Let me sketch out the rest so the tree is easier to see.
  22. I've added the elements from my list--1, 2, 3 and 4--to this tree,
  23. and I've put them in a special order corresponding to how they'd fall
  24. in English alphabetical order.
  25. So since the J in Jacob comes before the M in Margaret,
  26. I've made Jacob the left child in Margaret.
  27. Since the N in Nelson comes after the M in Margaret--j, k, l, m, n, o, p;
  28. yes, I can remember the English alphabet--I've made it the right child.
  29. And the A in Alice follows all the way down here to the left.
  30. I'm going to construct a special tree to store information like this
  31. that has a number of properties.
  32. The first 2 just summarize or formalize this ordering intuition we had above.
  33. Everything to the left of Margaret and all the way down
  34. is less than or equal to--comes before in the alphabet,
  35. is a smaller number than if I'm storing phone numbers instead--
  36. the information stored at Margaret's node.
  37. Jacob and Alice both come before Margaret in the alphabet, so they're both on the left.
  38. And similarly, right subtrees contain only information that's greater than or equal to--
  39. larger, later in the alphabet.
  40. Nelson comes after Margaret, so it's here on the right.
  41. And then finally--and this is really important--
  42. both the left and the right subtrees also follow rules I, II, and III.
  43. It is turtles all the way down.
  44. That makes this tree something special in computer science:
  45. a recursive data structure.
  46. We've already seen recursive functions that are defined in terms of themselves.
  47. Now I'm talking about a recursive way to lay out data that's defined in terms of itself.