1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] どのようにコンピュータ内のすべてのあなたの家族のメンバーを表すでしょう？

2
00:00:10,790 --> 00:00:12,390
我々は、単に、リストを使用することができます

3
00:00:12,390 --> 00:00:14,400
しかし、明確な階層がここにあります。

4
00:00:14,400 --> 00:00:17,110
>> Let 'sは、我々はあなたの曾祖母、アリスから始めていると言う。

5
00:00:17,110 --> 00:00:19,030
彼女はボブ、2人の息子がいます

6
00:00:19,030 --> 00:00:21,310
そしてあなたの祖父、チャーリー。

7
00:00:21,310 --> 00:00:23,190
チャーリーは、3人の子供を持っている

8
00:00:23,190 --> 00:00:26,730
あなたの叔父、デイブ、あなたの叔母、イブ、とあなたの父、フレッド。

9
00:00:26,730 --> 00:00:28,750
あなたは、フレッドの唯一の子である。

10
00:00:28,750 --> 00:00:30,950
>> なぜ、このようにあなたの家族のメンバーの編成であろう

11
00:00:30,950 --> 00:00:34,010
単純なリスト表現よりも良くなる？

12
00:00:34,010 --> 00:00:36,630
一つの理由は、この階層構造、

13
00:00:36,630 --> 00:00:39,660
いわゆる "木を、"単純なリストよりも多くの情報が含まれています。

14
00:00:40,540 --> 00:00:43,520
我々は皆の間に家族関係を知る

15
00:00:43,520 --> 00:00:45,440
ただ木を調べることによって。

16
00:00:45,440 --> 00:00:47,250
また、スピードアップすることができます

17
00:00:47,250 --> 00:00:50,010
ツリーデータがソートされている場合、途方もなく時間のルックアップ。

18
00:00:50,010 --> 00:00:53,850
>> 私たちはここでそれを活用することはできませんが、我々はすぐにこのような例を見ることができます。

19
00:00:53,850 --> 00:00:56,150
各人は、ツリー上のノードで表されます。

20
00:00:56,680 --> 00:00:58,370
ノードが子ノードを持つことができます

21
00:00:58,370 --> 00:01:00,350
同様に親ノードとして。

22
00:01:00,350 --> 00:01:02,390
これらは、技術的な用語である

23
00:01:02,390 --> 00:01:05,220
家族以外のもののために木を用いた場合であっても。

24
00:01:05,220 --> 00:01:07,940
アリスのノードは、2人の子供と親のないを持っている

25
00:01:07,940 --> 00:01:11,500
チャーリーのノードは3人の子供と1親を持ちながら。

26
00:01:11,500 --> 00:01:14,330
>> リーフノードは子を持たないものである

27
00:01:14,330 --> 00:01:16,410
木の外側の端に。

28
00:01:16,410 --> 00:01:18,520
ツリーの最上位ノード、ルートノード、

29
00:01:18,520 --> 00:01:20,240
親を持たない。

30
00:01:20,240 --> 00:01:23,170
>> バイナリツリーでは、ツリーの特定のタイプです

31
00:01:23,170 --> 00:01:26,720
その内の各ノードは、最大で2人の子供を持っています。

32
00:01:26,720 --> 00:01:30,490
ここではC言語でバイナリツリーのノードの構造体は、

33
00:01:31,560 --> 00:01:34,530
すべてのノードは、それに関連付けられているいくつかのデータを持って

34
00:01:34,530 --> 00:01:36,520
他のノードへのポインタと2。

35
00:01:36,520 --> 00:01:38,110
>> 私たちの家族のツリーで、

36
00:01:38,110 --> 00:01:40,900
関連付けられているデータは、それぞれの人の名前だった。

37
00:01:40,900 --> 00:01:43,850
それは何でもかまいませんけれども、ここでは、int型です。

38
00:01:44,510 --> 00:01:46,200
それは結局のところ、

39
00:01:46,200 --> 00:01:48,990
バイナリツリーは、家族のために良い表現ではない

40
00:01:48,990 --> 00:01:51,960
人々は頻繁に2つ以上の子供を持っているので。

41
00:01:51,960 --> 00:01:53,510
>> 二分探索木

42
00:01:53,510 --> 00:01:56,380
バイナリツリーの特別な、秩序タイプです

43
00:01:56,380 --> 00:01:58,090
それは私達がすぐに値を見ることができます。

44
00:01:58,740 --> 00:02:00,050
あなたは気づいているかもしれません

45
00:02:00,050 --> 00:02:02,010
そのツリーのルートの下のすべてのノード

46
00:02:02,010 --> 00:02:04,620
別のツリーのルートは、 "サブツリー"と呼ばれます。

47
00:02:04,960 --> 00:02:07,090
ここでは、ツリーのルートは、6です

48
00:02:07,090 --> 00:02:09,860
とその子、2は、サブツリーのルートです。

49
00:02:09,860 --> 00:02:11,870
>> 二分探索木で

50
00:02:11,870 --> 00:02:15,790
ノードの右の部分木のすべての値

51
00:02:15,790 --> 00:02:18,690
ノードの値よりも大きくなります。ここに：6。

52
00:02:18,690 --> 00:02:22,640
さて、ノードの左の部分木の値

53
00:02:24,540 --> 00:02:26,890
ノードの値未満です。

54
00:02:26,890 --> 00:02:28,620
我々は、重複値を処理する必要がある場合は、

55
00:02:28,620 --> 00:02:31,760
我々は、緩い不平等のいずれかにそれらの変更ができます

56
00:02:31,760 --> 00:02:34,410
同一の値は、左または右のいずれかに落ちることができることを意味し、

57
00:02:34,410 --> 00:02:37,400
限り、我々は全体で約一貫性があるように。

58
00:02:37,400 --> 00:02:39,620
このツリーは、二分探索木である

59
00:02:39,620 --> 00:02:41,540
それは次のルールに従いますので。

60
00:02:42,320 --> 00:02:46,020
>> これは、我々はC言語の構造体にすべてのノードをオンにした場合、それがどのように見えるかです。

61
00:02:46,880 --> 00:02:48,410
ていることに注意して子供が欠落している場合、

62
00:02:48,410 --> 00:02:50,340
ポインタはnullになります。

63
00:02:50,340 --> 00:02:53,270
どのように我々は7が木になっているかどうかをチェックしますか？

64
00:02:53,270 --> 00:02:55,020
私たちは、ルートから始まる。

65
00:02:55,020 --> 00:02:58,690
セブンが6より大きいので、それがツリーになら、それは右にでなければなりません。

66
00:02:59,680 --> 00:03:03,650
そして、それが8未満であるので、それは残さなければなりません。

67
00:03:03,650 --> 00:03:06,210
ここでは、7を発見した。

68
00:03:06,210 --> 00:03:08,160
今、我々は5のために確認してみます。

69
00:03:08,160 --> 00:03:11,500
ファイブは、6未満であるので、左側にあることが必要です。

70
00:03:11,500 --> 00:03:13,460
ファイブは、2より大きい

71
00:03:13,460 --> 00:03:15,010
ので、権利でなければなりません

72
00:03:15,010 --> 00:03:18,100
そしてそれはまた、4よりも大きいので、それは再び右にする必要があります。

73
00:03:18,100 --> 00:03:20,300
しかし、ここには子がありません。

74
00:03:20,300 --> 00:03:22,000
ポインタはnullになります。

75
00:03:22,000 --> 00:03:24,270
これは5が私たちのツリーに含まれていないことを意味します。

76
00:03:24,270 --> 00:03:27,250
>> 我々は、次のコードを使用してバイナリツリーを検索することができます：

77
00:03:28,430 --> 00:03:31,140
すべてのノードで、我々が発見したかどうかを確認してください

78
00:03:31,140 --> 00:03:33,020
私たちが探している値。

79
00:03:33,020 --> 00:03:35,740
我々はそれが見つからない場合は、それがあるべきならば、我々は判断

80
00:03:35,740 --> 00:03:38,990
左または右に、そのサブツリーを確認してください。

81
00:03:38,990 --> 00:03:41,160
このループは、木を切り倒していきます

82
00:03:41,160 --> 00:03:44,190
左または右のどちらかには子ノードが存在しなくなるまで。

83
00:03:45,190 --> 00:03:48,600
>> 5は木ではありませんでしたことを覚えておいてください。

84
00:03:48,600 --> 00:03:50,460
どのように我々はそれを挿入しますか？

85
00:03:50,460 --> 00:03:52,370
プロセスは、検索に似ています。

86
00:03:52,370 --> 00:03:54,830
我々は、6から始まるツリーを下に反復する

87
00:03:54,830 --> 00:03:57,040
2に残され、

88
00:03:57,040 --> 00:03:59,140
4への権利、

89
00:03:59,140 --> 00:04:02,500
そして再び右が、4は、この側には子がありません。

90
00:04:02,500 --> 00:04:06,090
これは、5用の新しい位置となります

91
00:04:06,090 --> 00:04:08,500
そして、それは子供がいないと開始されます。

92
00:04:09,020 --> 00:04:12,220
>> どのくらいの速さ二分探索木の操作はありますか？

93
00:04:12,220 --> 00:04:15,410
Bigohnotationが上限を提供しようとすることを覚えておいてください。

94
00:04:15,410 --> 00:04:17,390
最悪の場合には、

95
00:04:17,390 --> 00:04:19,480
私達の木は、単にリンクされたリストであってもかまいません

96
00:04:19,480 --> 00:04:22,220
その挿入、削除、および検索を意味

97
00:04:22,220 --> 00:04:25,380
ツリー内のノード数に比例して時間がかかることがあります。

98
00:04:25,380 --> 00:04:27,380
これはO（n）である。

99
00:04:27,380 --> 00:04:30,690
>> たとえば、以下は有効な二分探索木である。

100
00:04:31,850 --> 00:04:34,020
しかし、我々は9の検索を試みると、

101
00:04:34,020 --> 00:04:36,760
我々は、すべてのノードを横断しなければならない。

102
00:04:36,760 --> 00:04:39,120
これは、リンクされたリストと大差ありません。

103
00:04:39,120 --> 00:04:41,410
理想的には、我々は、すべてのノードが欲しい

104
00:04:41,410 --> 00:04:44,120
2人の子供を持っている私たちの二分探索木の。

105
00:04:44,120 --> 00:04:46,370
このように、挿入、削除、検索

106
00:04:46,370 --> 00:04:50,190
、最悪の場合、O（log n）の時間がかかるだろう。

107
00:04:50,190 --> 00:04:52,470
前からツリーは、よりバランスの取れたかもしれない

108
00:04:52,470 --> 00:04:54,140
このように。

109
00:04:54,140 --> 00:04:57,980
さて、任意の値を検索することは、最大でも3つのステップをとります。

110
00:04:57,980 --> 00:04:59,460
このツリーは、バランスが取れている

111
00:04:59,460 --> 00:05:01,190
最小限の深さを持っている意味

112
00:05:01,190 --> 00:05:03,680
ノード数に対して相対的。

113
00:05:03,680 --> 00:05:06,300
>> 平衡二分探索木に値を探して

114
00:05:06,300 --> 00:05:09,540
ソートされた配列でバイナリ検索に似ています。

115
00:05:09,540 --> 00:05:12,290
実際、私達が項目を挿入したり削除したりする必要がない場合は、

116
00:05:12,290 --> 00:05:15,150
彼らはまったく同じように動作します。

117
00:05:15,150 --> 00:05:17,600
しかし、ツリー構造が優れている

118
00:05:17,600 --> 00:05:19,530
挿入と削除を処理するための

119
00:05:20,360 --> 00:05:22,670
>> 私の名前はBannusファンデKlootです。

120
00:05:22,670 --> 00:05:24,030
これはCS50です。