YouTube

Got a YouTube account?

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

Japanese subtitles

← 05x-01 Trees

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 10/23/2014 by Udacity.

  1. ようこそ ここではプログラミングスキルを
    さらに磨いていきましょう
  2. 今回詳しく見ていく問題は
  3. 名簿や電話帳など整列された索引を持つ
    物理デバイスにとって重要なものです
  4. 整列された情報をどのように編成し
  5. 検索するか考えてみましょう
  6. 問題を解くのに木を使います
  7. 木は以前にもプログラミングで見たことがあります
  8. 今回用いる木は
  9. 各段階に2本の枝があるものです
  10. 名簿や電話帳に連絡を取りたい友達が
  11. 4人いるとしましょう
  12. Pythonではリストを使って
    4人の名前つまり4つの要素を表せます
  13. そしてinというキーワードを使って
    要素を左にリストを右に書くと
  14. そのリストに要素が含まれるか
    調べることができます
  15. しかしPythonは裏側で何をして
  16. どう実装されているのか疑問です
  17. 今回見ていく方法は
  18. 特別な木を作って
    全ての情報を保持しておくというものです
  19. リストの最初の要素から始め
  20. 木の根を一番上とします
  21. 分かりやすいように残りを描いてみます
  22. リストから1、2、3、4と要素を取り出し
    木に加えました
  23. この時アルファベット順に応じて
  24. 特別な順序で加えていきます
  25. JacobのJはMargaretのMより前に来ますから
  26. JacobはMargaretの左の子にします
  27. NelsonのNはMargaretのMよりあとに来ます
    j、k、l、m、n、o、pなので
  28. 正しいですね Nelsonを右の子にします
  29. AliceのAはずっと左へ下がります
  30. このように複数の要素を情報として保持する木を
  31. 作っていきます
  32. 最初の2つは今の直観的な説明を
    規則としてまとめたものです
  33. まずMargaretの左の子はすべてアルファベット順で
  34. Margaretのノードに保持された情報と
  35. 同じか前に来るものです
  36. 電話番号を整理するなら小さい番号になります
  37. JacobとAliceはアルファベット順で
    Margaretより前なので左です
  38. 次に右の部分木にはアルファベット順で
  39. 同じか大きい情報しか来ません
  40. NelsonはMargaretよりあとなので右に来ます
  41. そして最後に重要な点ですが
  42. 左右の部分木は両方とも
    このI、II、IIIの規則に従います
  43. 同様にどんどん下につながっていきます
  44. これによって木は専門用語でいう
  45. 再帰的データ構造となります
  46. 既に自身を用いて
    定義された再帰関数について学びました
  47. これから自身と同じ規則を使ってデータ構造を
    定めた再帰的データ構造について話します