1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [第7項] [あまり快適]

2
00:00:02,500 --> 00:00:04,890
[ネイトHardison] [ハーバード大学]

3
00:00:04,890 --> 00:00:07,000
[これはCS50です。] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> 第7章へようこそ。

5
00:00:09,080 --> 00:00:11,330
ハリケーンサンディのおかげで、

6
00:00:11,330 --> 00:00:13,440
代わりに今週通常のセクションを持っていることの、

7
00:00:13,440 --> 00:00:17,650
我々は、質問のセクションを介して、ウォークスルーでこれをやっている。

8
00:00:17,650 --> 00:00:22,830
私は、6仕様を設定して問題と一緒に次のようにするつもりです

9
00:00:22,830 --> 00:00:25,650
との質問のすべてを通過

10
00:00:25,650 --> 00:00:27,770
質問セクションのセクション。

11
00:00:27,770 --> 00:00:30,940
何か質問がある場合は、

12
00:00:30,940 --> 00:00:32,960
CS50論議でこれらを投稿してください。

13
00:00:32,960 --> 00:00:35,480
>> よし。始めましょう。

14
00:00:35,480 --> 00:00:40,780
今、私は問題セット仕様の3ページ目で探しています。

15
00:00:40,780 --> 00:00:44,110
我々は最初の二分木について話し始めるつもりです

16
00:00:44,110 --> 00:00:47,850
それらは、今週の問題セットへの関連性の多くを持っているので - 

17
00:00:47,850 --> 00:00:49,950
ハフマン木のエンコーディング。

18
00:00:49,950 --> 00:00:55,000
我々はCS50での話、非常に最初のデータ構造の一つが配列だった。

19
00:00:55,000 --> 00:01:00,170
配列は要素のシーケンスであることを忘れないでください - 

20
00:01:00,170 --> 00:01:04,019
同じタイプのすべて - メモリ内で隣同士に右に格納されている。

21
00:01:04,019 --> 00:01:14,420
私は、このボックスナンバー - 整数のスタイルを使用して描くことができる整数の配列を持っている場合 - 

22
00:01:14,420 --> 00:01:20,290
私は最初のボックスに5を持っていると言うてみましょう、私は、第二の7を持っている

23
00:01:20,290 --> 00:01:27,760
それから私は、最終的なボックスに8、10、20を持っています。

24
00:01:27,760 --> 00:01:33,000
、この配列は約2本当に良いものを覚えている

25
00:01:33,000 --> 00:01:38,800
我々は、任意の特定の要素にこの一定時間のアクセスを持っているということです

26
00:01:38,800 --> 00:01:40,500
 配列内の我々は、そのインデックスを知っていれば。

27
00:01:40,500 --> 00:01:44,670
たとえば、私は、配列の3番目の要素を取得したい場合 - 

28
00:01:44,670 --> 00:01:47,870
私たちのゼロベースのインデックスシステムを使用して、インデックス2  - 

29
00:01:47,870 --> 00:01:52,220
私は文字通り単純な数学的な計算をしなければならない、

30
00:01:52,220 --> 00:01:56,170
配列内のその位置にホップ、

31
00:01:56,170 --> 00:01:57,840
、そこに格納されている8を抜く

32
00:01:57,840 --> 00:01:59,260
そして、私が行ってもいいよ。

33
00:01:59,260 --> 00:02:03,350
>> この配列の悪口の一つ - 我々は話を

34
00:02:03,350 --> 00:02:05,010
我々は、リンクされたリストについて説明したときに - 

35
00:02:05,010 --> 00:02:09,120
私は、この配列に要素を挿入する場合ということです

36
00:02:09,120 --> 00:02:11,090
私はいくつかの周りにシフトを行う必要があるつもりです。

37
00:02:11,090 --> 00:02:12,940
右ここでたとえば、この配列

38
00:02:12,940 --> 00:02:16,850
ソートされた順序になっている - 昇順にソート - 

39
00:02:16,850 --> 00:02:19,440
その後その後その後その後、5、7、8、10、20  - 

40
00:02:19,440 --> 00:02:23,100
しかし私は、この配列に9番を挿入したい場合は、

41
00:02:23,100 --> 00:02:27,460
私は、スペースを作るためにいくつかの要素をシフトする必要がありますするつもりです。

42
00:02:27,460 --> 00:02:30,440
私たちはここで、これを引き出すことができます。

43
00:02:30,440 --> 00:02:35,650
私は5,7を移動する必要があるとして、その後8だ。

44
00:02:35,650 --> 00:02:38,720
私は9を置くことができる隙間を作ります

45
00:02:38,720 --> 00:02:45,910
その後10と20は9の右に行くことができます。

46
00:02:45,910 --> 00:02:49,450
これは最悪のシナリオであるため痛みの種類です - 

47
00:02:49,450 --> 00:02:54,350
私たちは、始めまたは終わりのどちらに挿入することしているとき

48
00:02:54,350 --> 00:02:56,040
 - 私たちがシフトしている方法に応じて、配列の

49
00:02:56,040 --> 00:02:58,850
我々は、すべての要素をシフトすることに終わるかもしれない

50
00:02:58,850 --> 00:03:00,750
我々は現在、配列に格納していること。

51
00:03:00,750 --> 00:03:03,810
>> だから、これを回避する方法は何でしたか？

52
00:03:03,810 --> 00:03:09,260
これを回避する方法はどこに私達のリンクリスト方式に行くことだった - 

53
00:03:09,260 --> 00:03:19,820
代わりに、要素5、7、8、10、メモリ内の隣同士に20すべてを格納する - 

54
00:03:19,820 --> 00:03:25,630
我々はそれらを保存したい場所に私たちの代わりに種類のそれらを格納されたなかったもの

55
00:03:25,630 --> 00:03:32,470
私はここに描いてるこれらのリンクされたリスト内のノードは、アドホックの一種。

56
00:03:32,470 --> 00:03:42,060
そして、我々はこれらの次のポインタを使用して、それらを一緒に接続されています。

57
00:03:42,060 --> 00:03:44,370
私は、5日から7日へのポインタを持つことができます

58
00:03:44,370 --> 00:03:46,420
7から8へのポインタ、

59
00:03:46,420 --> 00:03:47,770
8から10へのポインタ、

60
00:03:47,770 --> 00:03:51,220
そして最後に、10から20へのポインタ、

61
00:03:51,220 --> 00:03:54,880
その後何も残っていないことを示す20でnullポインタ。

62
00:03:54,880 --> 00:03:59,690
我々がここにあるトレードオフ

63
00:03:59,690 --> 00:04:05,360
私たちは、ソートされたリストに番号9を挿入したい場合、それは、今ある

64
00:04:05,360 --> 00:04:08,270
我々がしなければならないすべては、9で新しいノードを作成している

65
00:04:08,270 --> 00:04:12,290
、適切な場所を指すようにそれを配線

66
00:04:12,290 --> 00:04:20,630
その後、再配線8を9にダウン指すようにします。

67
00:04:20,630 --> 00:04:25,660
それは我々が9を挿入したい場所を正確に私たちが知っていると仮定して、かなり速いのです。

68
00:04:25,660 --> 00:04:32,610
しかし、これと引き換えにトレードオフは、我々は今、一定時間のアクセスを失ってしまったということです

69
00:04:32,610 --> 00:04:36,230
我々のデータ構造内の特定の要素に。

70
00:04:36,230 --> 00:04:40,950
たとえば、私は、このリンクリスト内の4番目の要素を検索する場合は、

71
00:04:40,950 --> 00:04:43,510
私はリストの冒頭に開始する必要がありますするつもり

72
00:04:43,510 --> 00:04:48,930
私は4分の1を見つけるまで、ノード単位をカウントを通して私のように動作します。

73
00:04:48,930 --> 00:04:55,870
>> リンクされたリストよりも優れたアクセス性能を得るために - 

74
00:04:55,870 --> 00:04:59,360
しかし、また、我々が持っていた利点のいくつかを保持

75
00:04:59,360 --> 00:05:01,800
リンクされたリストから、挿入時間に換算すると - 

76
00:05:01,800 --> 00:05:05,750
バイナリツリーは少しより多くのメモリを使用する必要があるために起こっている。

77
00:05:05,750 --> 00:05:11,460
特に、だけではなく、バイナリツリーノードで一つのポインタを持っていることの - 

78
00:05:11,460 --> 00:05:13,350
リンクリストのようにノードがありません - 

79
00:05:13,350 --> 00:05:16,950
我々は、バイナリツリーノードへの2つのポインタを追加するつもりです。

80
00:05:16,950 --> 00:05:19,950
だけではなく、次の要素に1つのポインタを持つ

81
00:05:19,950 --> 00:05:24,420
我々は左の子と右の子へのポインタを持っているつもりです。

82
00:05:24,420 --> 00:05:26,560
>> のが実際のように見えるかを確認するために絵を描いてみましょう。

83
00:05:26,560 --> 00:05:31,350
繰り返しますが、私はこれらのボックスと矢印を使用するつもりです。

84
00:05:31,350 --> 00:05:37,150
バイナリツリーノードは、単純なボックスとオフを開始します。

85
00:05:37,150 --> 00:05:40,940
これは、値のためのスペースを持っているために起こっている

86
00:05:40,940 --> 00:05:47,280
そしてそれはまた、左の子と右の子のためのスペースを持っているために起こっている。

87
00:05:47,280 --> 00:05:49,280
私はここでそれらにラベルを付けるつもりです。

88
00:05:49,280 --> 00:05:57,560
我々は左の子を持っているつもりですし、我々は右の子を持っているつもりです。

89
00:05:57,560 --> 00:05:59,920
これを行うためのさまざまな方法があります。

90
00:05:59,920 --> 00:06:02,050
時には空間と利便性のため、

91
00:06:02,050 --> 00:06:06,460
私が下にここでやっているように私は実際にそれを描くよ

92
00:06:06,460 --> 00:06:10,910
私は一番上にある値を持っているつもりですここで、

93
00:06:10,910 --> 00:06:14,060
その後右下の右の子、

94
00:06:14,060 --> 00:06:16,060
左下のと左の子。

95
00:06:16,060 --> 00:06:20,250
この一番上の図に戻って、

96
00:06:20,250 --> 00:06:22,560
我々は、最上部に値を持っている

97
00:06:22,560 --> 00:06:25,560
次に我々は左の子ポインタを持っているし、我々は右の子ポインタを持っています。

98
00:06:25,560 --> 00:06:30,110
>> 問題セットの仕様では、

99
00:06:30,110 --> 00:06:33,110
我々は、値7を持つノードの描画の話

100
00:06:33,110 --> 00:06:39,750
してから、左の子はnullになりポインタ、nullである右の子ポインタ。

101
00:06:39,750 --> 00:06:46,040
我々は、いずれかのためのスペースに資本NULLを書き込むことができます

102
00:06:46,040 --> 00:06:51,610
両方の左の子と右の子、あるいは、我々はこの斜線を描くことができます

103
00:06:51,610 --> 00:06:53,750
ボックスのそれぞれを介して、それがnullであることを示します。

104
00:06:53,750 --> 00:06:57,560
私はそれが簡単だという理由だけでそれを行うつもりです。

105
00:06:57,560 --> 00:07:03,700
非常に単純なバイナリツリーノードを図式化には二つの方法があなたがここで見るアール

106
00:07:03,700 --> 00:07:07,960
ここで我々は、値7とヌル子のポインタを持つ。

107
00:07:07,960 --> 00:07:15,220
>> どのようにリンクされたリストを使用して約当社指定の話の第二部 - 

108
00:07:15,220 --> 00:07:18,270
覚えて、我々はリスト内の非常に最初の要素を保持しなければならなかった

109
00:07:18,270 --> 00:07:20,270
リスト全体を覚えて - 

110
00:07:20,270 --> 00:07:26,140
と同様に、バイナリツリーで、我々は唯一のツリーに一つのポインタを保持する必要が

111
00:07:26,140 --> 00:07:31,120
データ構造全体の制御を維持するためである。

112
00:07:31,120 --> 00:07:36,150
ツリーのこの特別な要素は、ツリーのルート·ノードと呼ばれます。

113
00:07:36,150 --> 00:07:43,360
たとえば、この1ノード - 値7を含む、このノード

114
00:07:43,360 --> 00:07:45,500
 -  nullの左と右の子ポインタを持つ

115
00:07:45,500 --> 00:07:47,360
、私たちのツリー内の唯一の値であった

116
00:07:47,360 --> 00:07:50,390
これは私たちのルートノードとなる。

117
00:07:50,390 --> 00:07:52,240
それは私達の木の非常に始まりです。

118
00:07:52,240 --> 00:07:58,530
私たちはツリーにノードを追加し始めると、我々は明らかに、このもう少し見ることができます。

119
00:07:58,530 --> 00:08:01,510
私は新しいページをアップしましょう​​。

120
00:08:01,510 --> 00:08:05,000
>> 今、私たちは、ルートに7を持つツリーを描画しようとしている

121
00:08:05,000 --> 00:08:10,920
そして左の子、右の子の9内の3内側。

122
00:08:10,920 --> 00:08:13,500
繰り返しますが、これは非常に単純です。

123
00:08:13,500 --> 00:08:26,510
私達は7を持っている、3ノードのため、9用のノードを描画する

124
00:08:26,510 --> 00:08:32,150
そして私は3を含むノードを指すように7の左の子のポインタを設定するつもりだ、

125
00:08:32,150 --> 00:08:37,850
と9を含むノードまで7を含むノードの右の子ポインタ。

126
00:08:37,850 --> 00:08:42,419
さて、3と9以降の任意の子供を持っていない、

127
00:08:42,419 --> 00:08:48,500
我々は、NULLにすることは、その子のポインタをすべて設定するつもりです。

128
00:08:48,500 --> 00:08:56,060
ここでは、私たちのツリーのルートは7番を含むノードに対応しています。

129
00:08:56,060 --> 00:09:02,440
我々が持っているのが、そのルートノードへのポインタである場合は、それを見ることができます

130
00:09:02,440 --> 00:09:07,330
私達は、私達の木の中を歩くと、子ノードの両方にアクセスすることができます - 

131
00:09:07,330 --> 00:09:10,630
3と9の両方。

132
00:09:10,630 --> 00:09:14,820
いいえ、ツリー上のすべての単一のノードへのポインタを保持する必要がありません。

133
00:09:14,820 --> 00:09:22,080
よし。今、私たちは、この図に別のノードを追加するつもりです。

134
00:09:22,080 --> 00:09:25,370
我々は、6を含むノードを追加しようとしている

135
00:09:25,370 --> 00:09:34,140
そして我々は3を含むノードの右の子として追加するつもりです。

136
00:09:34,140 --> 00:09:41,850
そのために、私は3つのノードでそのヌルポインタを消去するつもりです

137
00:09:41,850 --> 00:09:47,750
と6を含むノードを指すようにそれを配線します。よし。

138
00:09:47,750 --> 00:09:53,800
>> この時点での専門用語を少し上に行くことができます。

139
00:09:53,800 --> 00:09:58,230
、これは特にバイナリツリーと呼ばれている理由を起動するには

140
00:09:58,230 --> 00:10:00,460
それが2つの子へのポインタを持っているということです。

141
00:10:00,460 --> 00:10:06,020
以上の子へのポインタを持っている木の他の種類があります。

142
00:10:06,020 --> 00:10:10,930
具体的には、問題セット5で '試し'でした。

143
00:10:10,930 --> 00:10:19,310
あなたはその試みで、あなたは別の子供たちに27種類のポインタを持っていたことに気づくでしょう - 

144
00:10:19,310 --> 00:10:22,410
英語のアルファベット26文字のそれぞれに1つずつ、

145
00:10:22,410 --> 00:10:25,410
アポストロフィ、次いで27日 - 

146
00:10:25,410 --> 00:10:28,900
そう、それは木の型に似ています。

147
00:10:28,900 --> 00:10:34,070
しかし、ここでは、それはバイナリ以来、私たちは、2つだけの子へのポインタを持っています。

148
00:10:34,070 --> 00:10:37,880
>> 我々は話をこのルートノードに加えて、

149
00:10:37,880 --> 00:10:41,470
我々はまた、この用語の周りに投げてきた "子供"。

150
00:10:41,470 --> 00:10:44,470
1ノードが別のノードの子であるためにそれは何を意味するのでしょうか？

151
00:10:44,470 --> 00:10:54,060
これは文字通り、子ノードが別のノードの子であることを意味します

152
00:10:54,060 --> 00:10:58,760
そのほかのノードは、そのノードを指すように設定され、その子ポインタのいずれかを持っている場合。

153
00:10:58,760 --> 00:11:01,230
、より具体的にこれを入れて

154
00:11:01,230 --> 00:11:11,170
3は7の子ポインタのいずれかによって指されている場合、3は7の子です。

155
00:11:11,170 --> 00:11:14,510
 - 私たちは7の子が何であるかを把握した場合

156
00:11:14,510 --> 00:11:18,510
さて、私たちは、7は3へのポインタと9へのポインタを持っていることがわかり

157
00:11:18,510 --> 00:11:22,190
ので、9と3が7の子です。

158
00:11:22,190 --> 00:11:26,650
ナインは、その子へのポインタがnullであるため、子を持たない、

159
00:11:26,650 --> 00:11:30,940
と3には1つしか子、6を有している。

160
00:11:30,940 --> 00:11:37,430
そのポインタの両方がnullであるため、シックスはまた、我々は今すぐに描画します、これは子を持ちません。

161
00:11:37,430 --> 00:11:45,010
>> さらに、我々はまた、特定のノードの親の話

162
00:11:45,010 --> 00:11:51,100
これは、あなたが期待するように、この子の説明とは逆になります。

163
00:11:51,100 --> 00:11:58,620
あなたは人間と予想されるであろう2つの代わりに - 各ノードは親を1つしか持っています。

164
00:11:58,620 --> 00:12:03,390
たとえば、3つの親は7です。

165
00:12:03,390 --> 00:12:10,800
9の親も7であり、6の親は3です。それにはあまりない。

166
00:12:10,800 --> 00:12:15,720
我々はまた、祖父母と孫の話をするための用語を持っている

167
00:12:15,720 --> 00:12:18,210
そしてより一般的に、我々は先祖の話

168
00:12:18,210 --> 00:12:20,960
と、特定のノードの子孫。

169
00:12:20,960 --> 00:12:25,710
ノードのむしろや先祖、、 - ノードの祖先 - 

170
00:12:25,710 --> 00:12:32,730
rootからそのノードへのパス上に存在するすべてのノードである。

171
00:12:32,730 --> 00:12:36,640
たとえば、私はノード6で探していた場合、

172
00:12:36,640 --> 00:12:46,430
その後の祖先は3と7の両方になるだろうしている。

173
00:12:46,430 --> 00:12:55,310
9の祖先は、例えば、 - 私はノード9で探していた場合 - 

174
00:12:55,310 --> 00:12:59,990
次に9の祖先はわずか7です。

175
00:12:59,990 --> 00:13:01,940
そして子孫はまったく逆である。

176
00:13:01,940 --> 00:13:05,430
私は7のすべての子孫を見たい場合は、

177
00:13:05,430 --> 00:13:11,020
その後、私はその下のすべてのノードを見なければなりません。

178
00:13:11,020 --> 00:13:16,950
だから、私は、3,9、および7の子孫として6すべてを持っています。

179
00:13:16,950 --> 00:13:24,170
>> 我々が話だろうという最後の項は、兄弟であることのこの概念です。

180
00:13:24,170 --> 00:13:27,980
兄弟 - これらの家族の条件に沿って続いての一種 - 

181
00:13:27,980 --> 00:13:33,150
ツリー内の同じレベルにあるノードです。

182
00:13:33,150 --> 00:13:42,230
彼らは、ツリー内の同じレベルにあるためこのように、3と9は兄弟です。

183
00:13:42,230 --> 00:13:46,190
彼らは両方とも同じ親、7を持っている。

184
00:13:46,190 --> 00:13:51,400
9が子を持っていないため、6兄弟はありません。

185
00:13:51,400 --> 00:13:55,540
それが私たちのツリーのルートだからと7は、任意の兄弟を持っていません

186
00:13:55,540 --> 00:13:59,010
としか1ルートがあります。

187
00:13:59,010 --> 00:14:02,260
7人の兄弟を持っているためにそこには7つ上のノードでなければならないであろう。

188
00:14:02,260 --> 00:14:07,480
7はもはやツリーのルートにないでしょう、その場合、7の親がなければならないだろう。

189
00:14:07,480 --> 00:14:10,480
その後7の新しい親も、子供がなければならないでしょう

190
00:14:10,480 --> 00:14:16,480
その子はその後7の兄弟であろう。

191
00:14:16,480 --> 00:14:21,040
>> よし。上を移動する。

192
00:14:21,040 --> 00:14:24,930
我々は、二分木の我々の議論を始めたとき、

193
00:14:24,930 --> 00:14:28,790
我々はそれらを使用しようとしていた方法について話しました

194
00:14:28,790 --> 00:14:32,800
配列やリンクリストの両方の上の優位性を得る。

195
00:14:32,800 --> 00:14:37,220
そして、我々はそれをやろうとしている方法は、この順序付けプロパティである。

196
00:14:37,220 --> 00:14:41,080
我々は、仕様に応じて、バイナリツリーを注文していると言う

197
00:14:41,080 --> 00:14:45,740
私たちのツリーの各ノードの場合は、左側にそのすべての子孫 - 

198
00:14:45,740 --> 00:14:48,670
左の子と左の子の子孫のすべて - 

199
00:14:48,670 --> 00:14:54,510
低い値は、右側にあるすべてのノードを持っている - 

200
00:14:54,510 --> 00:14:57,770
右の子と右の子の子孫のすべて - 

201
00:14:57,770 --> 00:15:02,800
我々が見ていること、現在のノードの値より大きいノードを持つ。

202
00:15:02,800 --> 00:15:07,850
ただ簡単にするために、我々は、ツリー内の任意の重複したノードが存在しないと仮定するつもりです。

203
00:15:07,850 --> 00:15:11,180
たとえば、このツリーには、我々はケースに対処するつもりはない

204
00:15:11,180 --> 00:15:13,680
ここで我々はルートに値7を持っている

205
00:15:13,680 --> 00:15:16,720
 それから私達はまた他の場所でツリーに値7を持っています。

206
00:15:16,720 --> 00:15:24,390
このケースでは、この木が実際に命じられていることに気づくでしょう。

207
00:15:24,390 --> 00:15:26,510
我々はルートに値7を持っています。

208
00:15:26,510 --> 00:15:29,720
7の左側にあるすべて - 

209
00:15:29,720 --> 00:15:35,310
私はここで、これらの小さなマークのすべてを取り消す場合 - 

210
00:15:35,310 --> 00:15:40,450
7の左側にあるすべてのもの -  3、6  - 

211
00:15:40,450 --> 00:15:49,410
これらの値は、両方の7未満であり、右側にあるものをすべて - ちょうどこの9  - 

212
00:15:49,410 --> 00:15:53,450
7より大きい。

213
00:15:53,450 --> 00:15:58,650
>> これは、これらの値を含む順序木だけではありませんが、

214
00:15:58,650 --> 00:16:03,120
しかし、ここではそれらのいくつかのより多くを描くことができます。

215
00:16:03,120 --> 00:16:05,030
我々はこれを行うことができる方法の全体の束は、実際にあります。

216
00:16:05,030 --> 00:16:09,380
私はちょうどここで物事をシンプルに保つために速記を使用するつもりだ - 

217
00:16:09,380 --> 00:16:11,520
全体ではなく、ボックスアンド矢印を引き出す - 

218
00:16:11,520 --> 00:16:14,220
私は数字だけを描き、それらを接続する矢印を追加するつもりです。

219
00:16:14,220 --> 00:16:22,920
開始するには、我々だけで、3それから私達は7を持っていたところ、再び私たちの元のツリーを記述して、よ

220
00:16:22,920 --> 00:16:25,590
その後3は、6に戻って右に指摘した

221
00:16:25,590 --> 00:16:30,890
および7は9であった右の子を持っていた。

222
00:16:30,890 --> 00:16:33,860
よし。我々はこの木を書くことができることを別の方法は何ですか？

223
00:16:33,860 --> 00:16:38,800
代わりに7の左の子である3持っていることの、

224
00:16:38,800 --> 00:16:41,360
我々はまた、6,7の左の子である可能性があります

225
00:16:41,360 --> 00:16:44,470
その後3は6の左の子である。

226
00:16:44,470 --> 00:16:48,520
私は7を持っているところであるが、右ここにこの木のようになります。

227
00:16:48,520 --> 00:16:57,860
その後、6、3、右に9。

228
00:16:57,860 --> 00:17:01,490
私達はまた私達のルートノードとして7を持っている必要はありません。

229
00:17:01,490 --> 00:17:03,860
私達はまた私達のルートノードとして6を及ぼす可能性があります。

230
00:17:03,860 --> 00:17:06,470
どのように見えるのでしょうか？

231
00:17:06,470 --> 00:17:09,230
我々はこの順序付きプロパティを維持するつもりなら、

232
00:17:09,230 --> 00:17:12,970
6の左側にあるすべてのものは、それ以下にする必要があります。

233
00:17:12,970 --> 00:17:16,540
そこに唯一の一つの可能​​性だし、それは3だ。

234
00:17:16,540 --> 00:17:19,869
しかし、その後、6の右の子のように、我々は2つ​​の可能性を高めています。

235
00:17:19,869 --> 00:17:25,380
まず、我々は、7その後9を及ぼす可能性があります

236
00:17:25,380 --> 00:17:28,850
あるいは、我々はそれを描くこと - 私はここで何をしようとしているような - 

237
00:17:28,850 --> 00:17:34,790
我々は6の右の子として9を有する場合、

238
00:17:34,790 --> 00:17:39,050
その後9の左の子のように7。

239
00:17:39,050 --> 00:17:44,240
>> さて、7と6は、rootに対してのみ可能な値ではありません。

240
00:17:44,240 --> 00:17:50,200
我々はまた、3ルートになる可能性があります。

241
00:17:50,200 --> 00:17:52,240
3ルートにある場合はどうなりますか？

242
00:17:52,240 --> 00:17:54,390
ここでは、物事は少し面白くなる。

243
00:17:54,390 --> 00:17:58,440
三つには、それより小さい値はすべてを持っていません

244
00:17:58,440 --> 00:18:02,070
そう、ツリーのその全体の左側はnullであることを行っている。

245
00:18:02,070 --> 00:18:03,230
そこに何かがあるようにはならないだろう。

246
00:18:03,230 --> 00:18:07,220
右側には、我々は、昇順で物事をリストできます。

247
00:18:07,220 --> 00:18:15,530
次に次に次に図3、図6、図7、図9を及ぼす可能性があります。

248
00:18:15,530 --> 00:18:26,710
または、我々はそれから9,7その後、6次に、3を行うことができます。

249
00:18:26,710 --> 00:18:35,020
または、我々はその後、7、6、9次に、3を行うことができます。

250
00:18:35,020 --> 00:18:40,950
または、3,7  - 実際には、我々はもう7を行うことはできません。

251
00:18:40,950 --> 00:18:43,330
それはそこに私たちの一つのことだ。

252
00:18:43,330 --> 00:18:54,710
我々は9を行うことができ、その後9時から、我々は6、その後7を行うことができます。

253
00:18:54,710 --> 00:19:06,980
または、我々はそれから9,7次に、3の操作を行い、[6することができます。

254
00:19:06,980 --> 00:19:12,490
>> ここにあなたの注意を引くために一つのことはある

255
00:19:12,490 --> 00:19:14,510
これらの木は少し奇妙に見えるしていること。

256
00:19:14,510 --> 00:19:17,840
特に、我々は右側の4木を見れば - 

257
00:19:17,840 --> 00:19:20,930
私はここに、それらを一周します - 

258
00:19:20,930 --> 00:19:28,410
これらの木はほぼ正確にリンクされたリストのように見えます。

259
00:19:28,410 --> 00:19:32,670
各ノードには、子が1つしかなく、

260
00:19:32,670 --> 00:19:38,950
それで我々は、例えば、我々が見ているこのツリー状の構造のいずれかを持っていない

261
00:19:38,950 --> 00:19:44,720
 左下のこっちにこの1孤独な木インチ

262
00:19:44,720 --> 00:19:52,490
これらの木は実際にはバイナリツリーを縮退と呼ばれ、

263
00:19:52,490 --> 00:19:54,170
そして我々は、将来的にこれらのよりについて話そう - 

264
00:19:54,170 --> 00:19:56,730
あなたは、他のコンピュータサイエンスのコースを取るために行く場合は特に。

265
00:19:56,730 --> 00:19:59,670
これらの木は、縮退している。

266
00:19:59,670 --> 00:20:03,780
、確かに、この構造は向いているので、彼らは非常に有用ではありません

267
00:20:03,780 --> 00:20:08,060
 リンクリストと同様の時間をルックアップします。

268
00:20:08,060 --> 00:20:13,050
私たちは余分なメモリを活用するために得ることはありません - この余分なポインタを - 

269
00:20:13,050 --> 00:20:18,840
なぜなら我々の構造のこのように悪いこと。

270
00:20:18,840 --> 00:20:24,700
むしろより上に行くとルートに9を持っている、バイナリツリーを引き出す、

271
00:20:24,700 --> 00:20:27,220
我々が持っている最後のケースは、これです

272
00:20:27,220 --> 00:20:32,380
我々は、この他の用語について少し話をしようとして、この時点では、代わりにしている

273
00:20:32,380 --> 00:20:36,150
高さと呼ばれる木々と書かれている場合、我々は、使用している。

274
00:20:36,150 --> 00:20:45,460
>> ツリーの高さは、ルートから最も遠いノードまでの距離である

275
00:20:45,460 --> 00:20:48,370
というよりあなたがするために行う必要があることにホップ数

276
00:20:48,370 --> 00:20:53,750
rootから起動して、ツリー内の最も遠いノードで終わる。

277
00:20:53,750 --> 00:20:57,330
我々はここに描かれてきたこれらの木のいくつかを、見てみると

278
00:20:57,330 --> 00:21:07,870
我々は我々が左上隅にこの木を取り、私達は3時に開始した場合見ることができ、

279
00:21:07,870 --> 00:21:14,510
次に我々は、6に到達するために1ホップを作るために7を取得する2番目のホップを持って、

280
00:21:14,510 --> 00:21:20,560
と9に到達するために第三ホップ。

281
00:21:20,560 --> 00:21:26,120
だから、この木の高さは3です。

282
00:21:26,120 --> 00:21:30,640
我々は、この緑で囲ま他の木のために同じ運動を行うことができます

283
00:21:30,640 --> 00:21:40,100
そして我々は、これらの木のすべての高さは実際にも3であることがわかります。

284
00:21:40,100 --> 00:21:45,230
それは彼らが退化作るものの一部だ - 

285
00:21:45,230 --> 00:21:53,750
その高さは、全体のツリー内のノードの数より一つ少ないこと。

286
00:21:53,750 --> 00:21:58,400
、我々は赤で囲まれているこの他の木を見れば、その一方で

287
00:21:58,400 --> 00:22:03,920
 - 私たちは、最も遠いリーフノードが6と9であることがわかり

288
00:22:03,920 --> 00:22:06,940
子を持たないそれらのノードである葉。

289
00:22:06,940 --> 00:22:11,760
だから、ルートノードから6または9のいずれかに到達するために、

290
00:22:11,760 --> 00:22:17,840
私たちは、7に到達するために1ホップを作るために持っているし、9に到達するために第二ホップ

291
00:22:17,840 --> 00:22:21,240
と同様に、7からわずか2番目のホップは6に取得します。

292
00:22:21,240 --> 00:22:29,080
だから、ここを介してこの木の高さは2です。

293
00:22:29,080 --> 00:22:35,330
あなたは戻って、我々は以前に説明した他の木々のすべてのことを行うことができます

294
00:22:35,330 --> 00:22:37,380
7,6で始まる、

295
00:22:37,480 --> 00:22:42,500
そしてあなたは、木のすべての高さも2であることがわかります。

296
00:22:42,500 --> 00:22:46,320
>> 私たちが話してきた理由は、バイナリツリーを命じた

297
00:22:46,320 --> 00:22:50,250
あなたは、これらを経由して検索することができますので、彼らはクールだ理由です

298
00:22:50,250 --> 00:22:53,810
ソートされた配列に対して検索すると非常によく似た方法。

299
00:22:53,810 --> 00:22:58,720
これは、我々はその改善ルックアップ時間を得ることについて話をする場所です

300
00:22:58,720 --> 00:23:02,730
単純なリンクリスト上。

301
00:23:02,730 --> 00:23:05,010
リンクリストと - あなたは、特定の要素を検索したい場合 - 

302
00:23:05,010 --> 00:23:07,470
あなたは、最高の状態で線形探索のいくつかの並べ替えをやろうとしている

303
00:23:07,470 --> 00:23:10,920
 - あなたは、リストとホップ一つずつの先頭から開始場所

304
00:23:10,920 --> 00:23:12,620
いずれかのノードで、1つのノード - 

305
00:23:12,620 --> 00:23:16,060
あなたはあなたが探しているものは何でも見つかるまで、リスト全体を通じ。

306
00:23:16,060 --> 00:23:19,440
は、この素敵なフォーマットで保存されているバイナリツリーを持っている場合、一方

307
00:23:19,440 --> 00:23:23,300
あなたは、実際に起こってバイナリサーチの多くを得ることができます

308
00:23:23,300 --> 00:23:25,160
あなたは、分割統治場所

309
00:23:25,160 --> 00:23:29,490
各ステップでのツリーの適切な半部を検索してください。

310
00:23:29,490 --> 00:23:32,840
のは、その仕組みを見てみましょう。

311
00:23:32,840 --> 00:23:38,850
>> 我々が持っている場合 - もう一度、私たちの元の木に戻って - 

312
00:23:38,850 --> 00:23:46,710
我々は、右側に、我々は左の3を持って、7時9を起動

313
00:23:46,710 --> 00:23:51,740
と3の下、我々は6を持っています。

314
00:23:51,740 --> 00:24:01,880
我々はこのツリー内の数字6を検索したい場合、我々は、ルートから始まると思います。

315
00:24:01,880 --> 00:24:08,910
我々は、6と言う、我々が探している値と比較します

316
00:24:08,910 --> 00:24:12,320
我々が現在見ていることをノードに格納された値、7、

317
00:24:12,320 --> 00:24:21,200
6は確かに7未満であるので、我々は左に移動したいことがわかります。

318
00:24:21,200 --> 00:24:25,530
6の値が7以上であった場合、我々はその代わりに右に移動していただろう。

319
00:24:25,530 --> 00:24:29,770
我々は知っているので、その - 私たちの順序付けられたバイナリツリーの構造に起因する - 

320
00:24:29,770 --> 00:24:33,910
7未満のすべての値は、7の左側に格納することとしている

321
00:24:33,910 --> 00:24:40,520
でも、木の右側を通って見て気にする必要はありません。

322
00:24:40,520 --> 00:24:43,780
かつて我々は左に移動し、我々は3を含むノードで今なら、

323
00:24:43,780 --> 00:24:48,110
我々は3と6を比較するところ、我々は再びその同じ比較を行うことができます。

324
00:24:48,110 --> 00:24:52,430
、3より大きいです - 我々が探している価値 - 私たちは、しばらく6はわかり

325
00:24:52,430 --> 00:24:58,580
我々は、3を含むノードの右側に行くことができます。

326
00:24:58,580 --> 00:25:02,670
そこには左側がここにないので、我々はそれを無視している可能性があります。

327
00:25:02,670 --> 00:25:06,510
しかし、我々は唯一の、私たちは木そのものを見ていることを知っているので、

328
00:25:06,510 --> 00:25:08,660
そして我々は木が子を持たないことがわかります。

329
00:25:08,660 --> 00:25:13,640
>> それは、我々は人間として私達自身をやっている場合、このツリーに6をルックアップするためにも非常に簡単です

330
00:25:13,640 --> 00:25:16,890
しかし、どうなるのがコンピュータのように機械的に、次のプロセスに従いましょう

331
00:25:16,890 --> 00:25:18,620
実際にアルゴリズムを理解する。

332
00:25:18,620 --> 00:25:26,200
この時点で、我々は今、6を含むノードを見ている

333
00:25:26,200 --> 00:25:29,180
そして我々は、値6を探している

334
00:25:29,180 --> 00:25:31,740
そう、確かに、我々は適切なノードを発見した。

335
00:25:31,740 --> 00:25:35,070
私たちは、ツリー内の値6を発見し、我々は検索を停止できます。

336
00:25:35,070 --> 00:25:37,330
この時点で、何が起こっているかに応じて、

337
00:25:37,330 --> 00:25:41,870
私たちが言うことができる、そう、我々は値6を発見した、それは私たちのツリーに存在します。

338
00:25:41,870 --> 00:25:47,640
または、我々はノードを挿入したり、何かをする予定になっているならば、我々は、この時点でそれを行うことができる。

339
00:25:47,640 --> 00:25:53,010
>> どれだけこの作品を見てカップルより多くのルックアップをやってみましょうの。

340
00:25:53,010 --> 00:25:59,390
のは、我々がしようとすると、10の値をルックアップした場合に何が起こるか見てみましょう。

341
00:25:59,390 --> 00:26:02,970
私たちは、10の値をルックアップした場合、我々はルートから始まります。

342
00:26:02,970 --> 00:26:07,070
我々は10が7以上であることがわかると思いますので、私たちは右に移動したいと思います。

343
00:26:07,070 --> 00:26:13,640
我々は9に取得し、10から9を比較し、9は確かに10未満であることがわかると思います。

344
00:26:13,640 --> 00:26:16,210
だからもう一度、私たちは右に移動しようと思います。

345
00:26:16,210 --> 00:26:20,350
しかし、この時点で、我々は我々がnullノードにいることに気づくと思います。

346
00:26:20,350 --> 00:26:23,080
そこには何もありません。 10は、あるべきものは何もありません。

347
00:26:23,080 --> 00:26:29,360
ツリーには10が実際に存在しないことを - 私たちは失敗を報告することができる場所です。

348
00:26:29,360 --> 00:26:35,420
そして最後に、のは私たちがツリーに1をルックアップしようとしているケースを介して行くことができます。

349
00:26:35,420 --> 00:26:38,790
これは、右に行くの代わりにを除いて、我々は10を見れば何が起こるかに似ています

350
00:26:38,790 --> 00:26:41,260
我々は左に行くつもりです。

351
00:26:41,260 --> 00:26:46,170
私達は7時に始まって、1が7未満であることがわかるので、我々は左に移動します。

352
00:26:46,170 --> 00:26:51,750
私たちは3を取得すると1が3未満であることがわかりますので、再び我々は左に移動してみてください。

353
00:26:51,750 --> 00:26:59,080
この時点で我々がnullノードを持っているので、再び我々は失敗を報告することができます。

354
00:26:59,080 --> 00:27:10,260
>> あなたは、バイナリツリーの詳細についてはしたい場合は、

355
00:27:10,260 --> 00:27:14,420
あなたも一緒に行うことができます楽しい小さな問題の全体の束があります。

356
00:27:14,420 --> 00:27:19,450
私は、これらの図を一つずつの描画を練習することをお勧め

357
00:27:19,450 --> 00:27:21,910
と、別のステップのすべてを介して次の

358
00:27:21,910 --> 00:27:25,060
これが超便利になるだろうので、

359
00:27:25,060 --> 00:27:27,480
あなたは、ハフマン符号化された問題セットをやっているときだけでなく、

360
00:27:27,480 --> 00:27:29,390
だけでなく、将来のコースで - 

361
00:27:29,390 --> 00:27:32,220
ただ、これらのデータ構造を引き出すと問題を通して考える方法を学ぶ

362
00:27:32,220 --> 00:27:38,000
ペンと紙や、この場合には、iPadとスタイラス。

363
00:27:38,000 --> 00:27:41,000
>> しかしこの時点で、我々はいくつかのコーディングの練習を行うために移動するつもりだ

364
00:27:41,000 --> 00:27:44,870
そして、実際にこれらのバイナリツリーと遊ぶ参照してください。

365
00:27:44,870 --> 00:27:52,150
私は自分のコンピュータに上にスイッチバックするつもりです。

366
00:27:52,150 --> 00:27:58,480
セクションのこの部分のため、代わりにCS50 CS50ランまたはスペースを使用するのではなく、

367
00:27:58,480 --> 00:28:01,500
私は、アプライアンスを使用するつもりです。

368
00:28:01,500 --> 00:28:04,950
>> 問題セットの仕様に沿って続いて、

369
00:28:04,950 --> 00:28:07,740
私は、私は、アプライアンスを開くことになっていることがわかり

370
00:28:07,740 --> 00:28:11,020
、私のDropboxフォルダに移動し、第7節と呼ばれるフォルダを作成

371
00:28:11,020 --> 00:28:15,730
その後binary_tree.cという名前のファイルを作成します。

372
00:28:15,730 --> 00:28:22,050
ここに私達は行く。私は、アプライアンスがすでに開いて持っている。

373
00:28:22,050 --> 00:28:25,910
私は、端子をプルアップして行きます。

374
00:28:25,910 --> 00:28:38,250
私はDropboxのフォルダに行くつもりです、section7というディレクトリを作り、

375
00:28:38,250 --> 00:28:42,230
そしてそれは完全に空です参照してください。

376
00:28:42,230 --> 00:28:48,860
今私はbinary_tree.cを開くつもりです。

377
00:28:48,860 --> 00:28:51,750
よし。ここに私達は行く - 空のファイルを。

378
00:28:51,750 --> 00:28:54,330
>> のが仕様に戻りましょう。

379
00:28:54,330 --> 00:28:59,850
仕様は新しい型定義を作成するか尋ね

380
00:28:59,850 --> 00:29:03,080
int型の値を格納したバイナリツリーノードの - 

381
00:29:03,080 --> 00:29:07,110
ちょうど私達が私達の前に、作図中で描いたような値。

382
00:29:07,110 --> 00:29:11,740
我々は、我々がここに行ったことこの決まり文句は、typedefを使用するつもりだ

383
00:29:11,740 --> 00:29:14,420
あなたは問題セット5から認識しなければならない - 

384
00:29:14,420 --> 00:29:19,190
あなたは征服スペルチェックプログラムのハッシュテーブルのやり方をしなかった場合。

385
00:29:19,190 --> 00:29:22,540
また、先週のセクションから、それを認識しなければならない

386
00:29:22,540 --> 00:29:23,890
ここで我々は、リンクリストについて話しました。

387
00:29:23,890 --> 00:29:27,870
我々は、構造ノードのこのtypedefを持っている

388
00:29:27,870 --> 00:29:34,430
そして我々はあらかじめ構造ノードのこの名前は、この構造体のノードを与えてくれた

389
00:29:34,430 --> 00:29:39,350
我々にはstructノードのポインタを持ってしたいと思うので、我々はそれを参照できるように

390
00:29:39,350 --> 00:29:45,740
私たちの構造体の一部として、私たちはその後、これを包囲しました - 

391
00:29:45,740 --> 00:29:47,700
いやむしろ、これを囲んで -  typedefで

392
00:29:47,700 --> 00:29:54,600
だから、それ以降のコードでは、代わりに構造ノードのノードだけでは、この構造体を参照することができます。

393
00:29:54,600 --> 00:30:03,120
>> これは、我々が先週見た、片方向リンクリストの定義に非常に似ているために起こっている。

394
00:30:03,120 --> 00:30:20,070
これを行うには、単に定型文を書くことから始めてみましょう。

395
00:30:20,070 --> 00:30:23,840
私たちは、整数値を持たなければならないことを知っている

396
00:30:23,840 --> 00:30:32,170
ので、我々はint値を入れ、その後、代わりに次の要素にただ一つのポインタを持つのだろう - 

397
00:30:32,170 --> 00:30:33,970
我々は、片方向リンクリストの場合と同じように - 

398
00:30:33,970 --> 00:30:38,110
我々は左と右の子へのポインタを持っているつもりです。

399
00:30:38,110 --> 00:30:42,880
それはあまりにも非常に簡単です - 構造体のノード*左の子;

400
00:30:42,880 --> 00:30:51,190
とstructノード*右の子;クール。

401
00:30:51,190 --> 00:30:54,740
これはかなり良いスタートのように見えます。

402
00:30:54,740 --> 00:30:58,530
のが仕様に戻りましょう。

403
00:30:58,530 --> 00:31:05,030
>> 今、私たちはツリーのルートのためのグローバル·ノード*変数を宣言する必要があります。

404
00:31:05,030 --> 00:31:10,590
我々はまた、グローバルな私達のリンクリストの最初のポインタを作っただけのように、これはグローバルにするつもりだ。

405
00:31:10,590 --> 00:31:12,690
これは、我々が記述した関数でようでした

406
00:31:12,690 --> 00:31:16,180
我々は、このルートを回す維持する必要はありません - 

407
00:31:16,180 --> 00:31:19,620
私たちは、あなたが再帰的にこれらの関数を記述したいのであればことがわかりますけれども、

408
00:31:19,620 --> 00:31:22,830
それは最初の場所であってもグローバル変数として、それを周りに渡さないほうがよいかもしれません

409
00:31:22,830 --> 00:31:28,090
そして代わりに、メイン関数内で局所的にそれを初期化します。

410
00:31:28,090 --> 00:31:31,960
しかし、我々は、開始するために、グローバルにそれをやる。

411
00:31:31,960 --> 00:31:39,920
再び、我々はスペースのカップルを与えるだろう、と私は、ノード*ルートを宣言するつもりです。

412
00:31:39,920 --> 00:31:46,770
ただ私はこれが初期化されていないままにしないことを確認するために、私がnullに等しいそれを設定するつもりです。

413
00:31:46,770 --> 00:31:52,210
さて、main関数で - 私たちは右ここでは本当に速く書こうと思います - 

414
00:31:52,210 --> 00:32:00,450
int型のmain（int型のargc、const char *型のargv []） - 

415
00:32:00,450 --> 00:32:10,640
と私はちょうどので、私が知っているconstとして私のargv配列を宣言する開始するつもりだ

416
00:32:10,640 --> 00:32:14,550
これらの引数は、私はおそらく変更したくないの引数であること。

417
00:32:14,550 --> 00:32:18,390
私はそれらを修正したい場合、私はおそらくそれらのコピーを作成する必要があります。

418
00:32:18,390 --> 00:32:21,740
このコードの多くが表示されます。

419
00:32:21,740 --> 00:32:25,440
これは、いずれかの方法で大丈夫です。それをとして残していいのよ - あなたがご希望の場合はconstを省略します。

420
00:32:25,440 --> 00:32:28,630
私は通常、ちょうどので、私は自分自身を思い出させることにそれを置く

421
00:32:28,630 --> 00:32:33,650
 私はおそらく、これらの引数を変更したくない。

422
00:32:33,650 --> 00:32:39,240
>> いつものように、私はメインの最後に、このリターン0の行を含めるつもりです。

423
00:32:39,240 --> 00:32:45,730
ここでは、私は私のルートノードを初期化します。

424
00:32:45,730 --> 00:32:48,900
それが今立っているように、私は、nullに設定されているポインタを持っている

425
00:32:48,900 --> 00:32:52,970
そうそれは何を指している。

426
00:32:52,970 --> 00:32:57,480
、実際にはノードの構築を開始するために

427
00:32:57,480 --> 00:32:59,250
私が最初にそれ用のメモリを確保する必要があります。

428
00:32:59,250 --> 00:33:05,910
私は、mallocを使用してヒープ上のメモリにすることによってそれを行うつもりです。

429
00:33:05,910 --> 00:33:10,660
私は、mallocの結果と同じルートを設定するつもりだ

430
00:33:10,660 --> 00:33:19,550
と私は、ノードのサイズを計算するためにsizeof演算子を使用するつもりです。

431
00:33:19,550 --> 00:33:24,990
とは対照的に、私はsizeof演算ノードを使用している理由は、言う、

432
00:33:24,990 --> 00:33:37,020
malloc関数（4 +4 +4）またはmalloc  -  12  - このような何かを

433
00:33:37,020 --> 00:33:40,820
私は私のコードはできるだけ互換性を持たせたいからです。

434
00:33:40,820 --> 00:33:44,540
私はこのcファイルを取ることができるようにしたい、アプライアンス上でそれをコンパイルし、

435
00:33:44,540 --> 00:33:48,820
そしてその後、私の64ビットのMac上でそれをコンパイルする - 

436
00:33:48,820 --> 00:33:52,040
または完全に異なるアーキテクチャ上で - 

437
00:33:52,040 --> 00:33:54,640
と私はこのすべてが同じ仕事をしたい。

438
00:33:54,640 --> 00:33:59,510
>> 私は変数のサイズについての仮定を作ってる場合 - 

439
00:33:59,510 --> 00:34:02,070
intやポインタのサイズの大きさ - 

440
00:34:02,070 --> 00:34:06,070
その後、私はまた、アーキテクチャの種類について仮定を作ってるんだ

441
00:34:06,070 --> 00:34:10,440
実行時にどんな私のコードは正常にコンパイルできます。

442
00:34:10,440 --> 00:34:15,030
手動で構造体のフィールドを加算するのではなく、常にsizeofを使用しています。

443
00:34:15,030 --> 00:34:20,500
他の理由は、コンパイラがstructにパディングを置くことがあるかもしれないということです。

444
00:34:20,500 --> 00:34:26,570
だけでも、個々のフィールドを加算することで、一般的にやりたいことは何かありませんが、

445
00:34:26,570 --> 00:34:30,340
ので、その行を削除します。

446
00:34:30,340 --> 00:34:33,090
さて、実際には、このルートノードを初期化する

447
00:34:33,090 --> 00:34:36,489
私は、その異なる各フィールドの値をプラグインする必要がありますするつもりです。

448
00:34:36,489 --> 00:34:41,400
たとえば、値のために私は7に初期化したい知っている、

449
00:34:41,400 --> 00:34:46,920
そして今の私は左の子がnullに設定するつもりです

450
00:34:46,920 --> 00:34:55,820
そして右の子もNULLにする。すばらしい！

451
00:34:55,820 --> 00:35:02,670
我々は、仕様のその部分をやった。

452
00:35:02,670 --> 00:35:07,390
>> 3ページの一番下にある仕様ダウンより3つのノードを作成するために私に尋ねる - 

453
00:35:07,390 --> 00:35:10,600
3、6を含むもの、及び9と1を含む1  - 

454
00:35:10,600 --> 00:35:14,210
それはまさに私たちの樹形図のようになりますので、それらをしてから配線する

455
00:35:14,210 --> 00:35:17,120
我々は以前に話したこと。

456
00:35:17,120 --> 00:35:20,450
ここでかなり迅速にそれを行うてみましょう。

457
00:35:20,450 --> 00:35:26,270
あなたは、私は重複したコードの束の書き込みを開始するつもりだ本当にすぐわかります。

458
00:35:26,270 --> 00:35:32,100
私は、ノード*を作成するつもりですし、私はそれ3呼び出すつもりです。

459
00:35:32,100 --> 00:35:36,000
私は、malloc（sizeofの（ノード））と等しくなるように設定するつもりです。

460
00:35:36,000 --> 00:35:41,070
私は3->値= 3を設定するつもりです。

461
00:35:41,070 --> 00:35:54,780
三 - > left_child = NULL; 3  - >右_child = NULL;同様。

462
00:35:54,780 --> 00:36:01,150
その根を初期化することにかなり似ています、それが正確に何を

463
00:36:01,150 --> 00:36:05,760
私は同様に6と9を初期起動した場合に行う必要があるつもりです。

464
00:36:05,760 --> 00:36:20,720
私はすぐにここでは本当にそれを行うだろう - 実際に、私は少しのコピー＆ペーストをするつもりです、

465
00:36:20,720 --> 00:36:46,140
大丈夫 - と、私は確認してください。

466
00:36:46,470 --> 00:37:09,900
 今、私はそれをコピーして持っていると私は先に行くと、6〜この等しいを設定することができます。

467
00:37:09,900 --> 00:37:14,670
あなたは、これはしばらくかかり、超効率的ではないことがわかります。

468
00:37:14,670 --> 00:37:22,610
ほんの少しで、私たちは私たちのためにこれを行います関数を記述します。

469
00:37:22,610 --> 00:37:32,890
私は9でこれを置き換えたい、6でそれを交換してください。

470
00:37:32,890 --> 00:37:37,360
>> 今、我々はすべてのノードに作成および初期化を持っている。

471
00:37:37,360 --> 00:37:41,200
私達は私達のルート7と等しくなるように設定するか、値7を含有し、持っている

472
00:37:41,200 --> 00:37:46,510
3を含む我々のノード、6を含む我々のノード、および9を含む我々のノード。

473
00:37:46,510 --> 00:37:50,390
この時点で、我々がしなければならないすべてはすべてのものを線である。

474
00:37:50,390 --> 00:37:53,020
私はnullにすべてのポインタを初期化した理由は、私はそのことを確認してくださいちょうどそうということである

475
00:37:53,020 --> 00:37:56,260
私は偶然そこに初期化されていないポインタを持っていない。

476
00:37:56,260 --> 00:38:02,290
また、以来、この時点で、私は実際にお互いにノードを接続する必要があります - 

477
00:38:02,290 --> 00:38:04,750
それらが実際に接続していることをものに - 私は通過するとする必要はありません

478
00:38:04,750 --> 00:38:08,240
すべてNULLが適切な場所にそこにいることを確認してください。

479
00:38:08,240 --> 00:38:15,630
>> ルートから始まり、私はルートの左の子が3であることを知っています。

480
00:38:15,630 --> 00:38:21,250
私はルートの右の子が9であることを知っている。

481
00:38:21,250 --> 00:38:24,880
その後、私が心配する残っているだけで、他の子

482
00:38:24,880 --> 00:38:39,080
6は3の右の子です。

483
00:38:39,080 --> 00:38:44,670
この時点で、それはすべてかなりよさそうだ。

484
00:38:44,670 --> 00:38:54,210
私たちは、これらの行の一部を削除することもできる。

485
00:38:54,210 --> 00:38:59,540
これですべてがかなりよさそうだ。

486
00:38:59,540 --> 00:39:04,240
のが私たちの仕様に戻って、我々は次に何をしなければならないものを見てみましょう。

487
00:39:04,240 --> 00:39:07,610
>> この時点で、我々は 'が含まれている'という関数を記述する必要があります

488
00:39:07,610 --> 00:39:14,150
"ブールのcontains（int値）"のプロトタイプを持つ。

489
00:39:14,150 --> 00:39:17,060
そして、これは関数がtrueを返すように起こっている含まれています

490
00:39:17,060 --> 00:39:21,200
 ツリーには、当社のグローバルroot変数が指す場合

491
00:39:21,200 --> 00:39:26,950
 機能とそうでない場合はfalseに渡された値が含まれています。

492
00:39:26,950 --> 00:39:29,000
先に進み、それをやってみましょう。

493
00:39:29,000 --> 00:39:35,380
これはまさに我々がほんの少し前にiPad上で手でやったルックアップのようになるだろう。

494
00:39:35,380 --> 00:39:40,130
少しでズームインやスクロールアップしてみましょう。

495
00:39:40,130 --> 00:39:43,130
我々は右の私達の主な機能の上に、この関数を置くつもりだ

496
00:39:43,130 --> 00:39:48,990
ので、我々はプロトタイピングの任意の並べ替えを行う必要がないこと。

497
00:39:48,990 --> 00:39:55,960
だから、boolは（int値）が含まれています。

498
00:39:55,960 --> 00:40:00,330
そうしよう。私たちの決まり文句の宣言があります。

499
00:40:00,330 --> 00:40:02,900
ただ、これはコンパイルされていることを確認し、

500
00:40:02,900 --> 00:40:06,820
私は先に行くとちょうどfalseを返すことが等しくなるように設定するつもりです。

501
00:40:06,820 --> 00:40:09,980
今のところ、この関数は単に何もしないであろうと、常にそのを報告

502
00:40:09,980 --> 00:40:14,010
我々が捜している値は、ツリーではありません。

503
00:40:14,010 --> 00:40:16,280
>> この時点で、それはおそらく良いアイデアだ - 

504
00:40:16,280 --> 00:40:19,600
私たちはコードの全体の束を書いていると私たちも、まだそれをテストしようとしていないので - 

505
00:40:19,600 --> 00:40:22,590
それがすべてコンパイルされることを確認します。

506
00:40:22,590 --> 00:40:27,460
私たちは、これが実際にコンパイルすることを確認するためにしなければならないという点がいくつかあります。

507
00:40:27,460 --> 00:40:33,530
まず、我々はまだ含まれていないことにあるライブラリに任意の関数を使用してきたかどうかを確認します。

508
00:40:33,530 --> 00:40:37,940
我々はこれまで使ってきた関数はmalloc関数であり、

509
00:40:37,940 --> 00:40:43,310
その後、我々はまた、このタイプを使用してきた -  'bool'と呼ばれるこの規格外のタイプを - 

510
00:40:43,310 --> 00:40:45,750
標準のブール値のヘッダーファイルに含まれている。

511
00:40:45,750 --> 00:40:53,250
我々は間違いなく、bool型の標準的なbool.hを含めたい

512
00:40:53,250 --> 00:40:59,230
我々はまた、＃標準ライブラリの標準lib.hを含めたい

513
00:40:59,230 --> 00:41:03,530
それは、malloc、自由、そしてそのすべてが含まれています。

514
00:41:03,530 --> 00:41:08,660
だから、ズームアウト、我々はやめるつもりです。

515
00:41:08,660 --> 00:41:14,190
試してみて、これは実際にコンパイルを行っていることを確認してみましょう。

516
00:41:14,190 --> 00:41:18,150
我々はそれがないことがわかりますので、我々は正しい軌道に乗っている。

517
00:41:18,150 --> 00:41:22,990
>> さんが再びbinary_tree.cを開いてみましょう。

518
00:41:22,990 --> 00:41:34,530
これは、コンパイルされます。のが下がると我々は、CONTAINS関数にいくつかの呼び出しを挿入していることを確認してみよう - 

519
00:41:34,530 --> 00:41:40,130
ただそれはそれで良いのことを確認します。

520
00:41:40,130 --> 00:41:43,170
たとえば、先ほど私たちのツリーにいくつかの検索を行ったとき、

521
00:41:43,170 --> 00:41:48,500
、我々は値6,10、および1をルックアップしよう、と我々は6ツリー内であることを知っていた

522
00:41:48,500 --> 00:41:52,220
10には、ツリーではなかったし、1のいずれかのツリーではありませんでした。

523
00:41:52,220 --> 00:41:57,230
かどうかを把握する方法としてこれらのサンプル·コールを使用してみましょう

524
00:41:57,230 --> 00:41:59,880
私たちは、機能が働いているが含まれています。

525
00:41:59,880 --> 00:42:05,210
そのためには、私は、printf関数を使用するつもりだ

526
00:42:05,210 --> 00:42:10,280
そして我々は含まれていますへの呼び出しの結果をプリントアウトするつもりだ。

527
00:42:10,280 --> 00:42:13,280
私は（％d）=が含まれているため "という文字列に置くつもりです

528
00:42:13,280 --> 00:42:20,470
 私達は私達が見ていくつもりですした値をプラグインするつもりだ、

529
00:42:20,470 --> 00:42:27,130
と=％s \ n "が、我々の形式の文字列としてそれを使用しています。

530
00:42:27,130 --> 00:42:30,720
文字通り、画面にプリントアウトする - 我々は、ちょうど見に行くしている - 

531
00:42:30,720 --> 00:42:32,060
何が関数呼び出しのように見えます。

532
00:42:32,060 --> 00:42:33,580
これは実際には関数呼び出しではありません。

533
00:42:33,580 --> 00:42:36,760
 これはただの関数呼び出しのように見えるように設計される文字列です。

534
00:42:36,760 --> 00:42:41,140
>> 今、我々は値をプラグインするつもりだ。

535
00:42:41,140 --> 00:42:43,580
我々は試していくつもりですが、6日に含まれています

536
00:42:43,580 --> 00:42:48,340
その後、我々はここでやろうとしているが、その三項演算子を使用しています。

537
00:42:48,340 --> 00:42:56,340
見てみましょう -  6が含まれている - そう、今私は6を含んでいたし、もし6が真である含まれており、

538
00:42:56,340 --> 00:43:01,850
我々は％sフォーマット文字に送信しようとしている文字列

539
00:43:01,850 --> 00:43:04,850
文字列 "true"になるだろう。

540
00:43:04,850 --> 00:43:07,690
レッツは、少し上をスクロール。

541
00:43:07,690 --> 00:43:16,210
そうでなければ、我々は偽6リターンが含まれている場合は、 "false"という文字列を送りたいのですが。

542
00:43:16,210 --> 00:43:19,730
これはちょっと間抜けに見えるのですが、私は、私は同様に説明するかもしれない把握

543
00:43:19,730 --> 00:43:23,780
何の三項演算子は、我々はしばらくの間、それを見ていないので、次のようになります。

544
00:43:23,780 --> 00:43:27,670
これが私たちのCONTAINS機能が働いているかどうかを把握するための良い、便利な方法となります。

545
00:43:27,670 --> 00:43:30,040
私は、左に上にスクロールバックするつもりです

546
00:43:30,040 --> 00:43:39,900
と私は何回かこの行をコピーして貼り付けるつもりです。

547
00:43:39,900 --> 00:43:44,910
それは、周りのこれらの値の一部を変更

548
00:43:44,910 --> 00:43:59,380
ので、これが1になるだろうが、これは10になるだろう。

549
00:43:59,380 --> 00:44:02,480
>> この時点で私たちは素敵な関数を含む持っている。

550
00:44:02,480 --> 00:44:06,080
我々はいくつかのテストを持っている、と我々はこのすべての作品かどうかを確認します。

551
00:44:06,080 --> 00:44:08,120
この時点で、我々はいくつかのより多くのコードを書きました。

552
00:44:08,120 --> 00:44:13,160
すべて終了させて​​、すべてがまだコンパイルされることを確認するために時間。

553
00:44:13,160 --> 00:44:20,360
途中で辞め、現在は再び二分木を作ってみてみましょう。

554
00:44:20,360 --> 00:44:22,260
我々はエラーを持っているようにまあ、それは、見え

555
00:44:22,260 --> 00:44:26,930
そして我々は、これは明示的にprintfライブラリ関数を宣言するんだ。

556
00:44:26,930 --> 00:44:39,350
私たちが行くと＃standardio.hをインクルードする必要がありように見えます。

557
00:44:39,350 --> 00:44:45,350
とということで、すべてがコンパイルされるはずです。我々は、すべての良いです。

558
00:44:45,350 --> 00:44:50,420
今度は、バイナリツリーを実行してみて、何が起こるか見てみましょう。

559
00:44:50,420 --> 00:44:53,520
ここでは、。/ binary_tree、アール、

560
00:44:53,520 --> 00:44:55,190
我々は、我々は予想通り、ことがわかります - 

561
00:44:55,190 --> 00:44:56,910
我々が実装していないので、まだ含まれています

562
00:44:56,910 --> 00:44:59,800
あるいはむしろ、我々はちょうど偽見返りに入れてきた - 

563
00:44:59,800 --> 00:45:03,300
私たちは、それだけで、それらのすべてのためにfalseを返すていることがわかり

564
00:45:03,300 --> 00:45:06,180
そう、それはすべてかなりよく、ほとんどの部分のために働いている。

565
00:45:06,180 --> 00:45:11,860
>> のは、この時点で含まれています奥に行くと、実際に実装してみましょう。

566
00:45:11,860 --> 00:45:17,490
 - 私は、下にスクロールしてズームイン、とするつもりだ

567
00:45:17,490 --> 00:45:22,330
覚えて、我々が使用しているアルゴリズムは、我々はルートノードから開始されたことだった

568
00:45:22,330 --> 00:45:28,010
その後、我々が遭遇する各ノードで、我々は、比較を行う

569
00:45:28,010 --> 00:45:32,380
し、その比較に基づいて、我々はどちらか左の子か右の子に移動します。

570
00:45:32,380 --> 00:45:39,670
これは、我々は初期の用語で書いたバイナリ検索コードと非常によく似て見に行くされています。

571
00:45:39,670 --> 00:45:47,810
我々が始めたとき、我々は、現在のノードを保持することがわかっている

572
00:45:47,810 --> 00:45:54,050
我々は見ていると、現在のノードがルートノードに初期化されようとしていること。

573
00:45:54,050 --> 00:45:56,260
そして今、私たちは、木を通過維持するつもりだ

574
00:45:56,260 --> 00:45:58,140
そして私達の停止条件を覚えて - 

575
00:45:58,140 --> 00:46:01,870
 私たちは実際に手で例を通して働いていたとき - 

576
00:46:01,870 --> 00:46:03,960
我々はヌルノードに遭遇したとき、だった

577
00:46:03,960 --> 00:46:05,480
我々は、NULLの子を見ていないときに、

578
00:46:05,480 --> 00:46:09,620
むしろ我々が実際に、ツリー内のノードに移動するとき

579
00:46:09,620 --> 00:46:12,640
そして我々がnullノードにいることがわかった。

580
00:46:12,640 --> 00:46:20,720
我々は、curがnullに等しいなくなるまで反復するつもりです。

581
00:46:20,720 --> 00:46:22,920
と私たちはどうするつもりですか？

582
00:46:22,920 --> 00:46:31,610
我々は、かどうかをテストするつもりだ（最新版 - >値==値）は、

583
00:46:31,610 --> 00:46:35,160
その後、我々は実際に我々が捜しているノードを見つけたことを知っています。

584
00:46:35,160 --> 00:46:40,450
だからここで、我々は、trueを返すことができます。

585
00:46:40,450 --> 00:46:49,830
そうでなければ、我々は値が値より小さいかどうかを見たいと思っています。

586
00:46:49,830 --> 00:46:53,850
現在のノードの値は、我々が探している値よりも小さい場合は、

587
00:46:53,850 --> 00:46:57,280
私たちは右に移動するつもりです。

588
00:46:57,280 --> 00:47:10,600
だから、電流は電流=  - > right_child、そうでないと、我々は左に移動するつもりです。

589
00:47:10,600 --> 00:47:17,480
電流=電流 - > left_child;かなりシンプル。

590
00:47:17,480 --> 00:47:22,830
>> おそらくこれによく似たループを認識

591
00:47:22,830 --> 00:47:27,580
次に我々は、低域、中域、高扱ったことを除いて、以前の用語で二分探索、。

592
00:47:27,580 --> 00:47:30,000
ここでは、単に、現在の値を見ている

593
00:47:30,000 --> 00:47:31,930
ので、それはいいと簡単です。

594
00:47:31,930 --> 00:47:34,960
レッツは、このコードが動作していることを確認してください。

595
00:47:34,960 --> 00:47:42,780
まず、コンパイルを確認してください。それがないように見えます。

596
00:47:42,780 --> 00:47:47,920
のはそれを実行してみましょう。

597
00:47:47,920 --> 00:47:50,160
そして実際、それは我々が期待するすべてのものを出力します。

598
00:47:50,160 --> 00:47:54,320
これは、ツリー内の6を見つけ、10はツリーではないので、10を見つけることができない

599
00:47:54,320 --> 00:47:57,740
1ツリーでもありませんので、どちらか1が見つかりません。

600
00:47:57,740 --> 00:48:01,420
クールなもの。

601
00:48:01,420 --> 00:48:04,470
>> よし。のが私たちの仕様に戻って、次は何を見てみましょう。

602
00:48:04,470 --> 00:48:07,990
さて、それは私たちのツリーにいくつかのより多くのノードを追加したいと考えています。

603
00:48:07,990 --> 00:48:11,690
これは、5、2、および8を追加して、私たちのは、コードが含まれていることを確認したい

604
00:48:11,690 --> 00:48:13,570
期待どおりに動作します。

605
00:48:13,570 --> 00:48:14,900
そんな行きましょう。

606
00:48:14,900 --> 00:48:19,430
この時点ではなく、再びその迷惑なコピー＆ペーストを行うよりも、

607
00:48:19,430 --> 00:48:23,770
実際にノードを作成するための関数を書いてみましょう。

608
00:48:23,770 --> 00:48:27,740
我々は主にすべての方法を下にスクロールすると、我々はこれを行ってきたことがわかり

609
00:48:27,740 --> 00:48:31,210
我々はノードを作成するたびに何度も何度も非常によく似たコード。

610
00:48:31,210 --> 00:48:39,540
>> のは、実際に私たちのためにノードを構築し、それを返す関数を書いてみましょう。

611
00:48:39,540 --> 00:48:41,960
私はそれがbuild_node呼ぶつもりです。

612
00:48:41,960 --> 00:48:45,130
私は、特定の値を持つノードを構築するつもりです。

613
00:48:45,130 --> 00:48:51,040
ここでズーム。

614
00:48:51,040 --> 00:48:56,600
私は何をするつもりだ最初のものは、実際にヒープ上のノードのためのスペースを作成しています。

615
00:48:56,600 --> 00:49:05,400
だから、ノード* N =のmalloc（sizeofの（ノード））であり、n  - >値=値;

616
00:49:05,400 --> 00:49:14,960
し、ここで、私はちょうど適切な値になるように、すべてのフィールドを初期化するつもりです。

617
00:49:14,960 --> 00:49:22,500
そして一番最後に、我々はノードを返すでしょう。

618
00:49:22,500 --> 00:49:28,690
よし。もう一つ注意すべき点は、この関数はそのまさにここです

619
00:49:28,690 --> 00:49:34,320
ヒープ割り当てられたメモリへのポインタを返すために起こっている。

620
00:49:34,320 --> 00:49:38,880
これは何についての素晴らしいのは、今、このノードということです - 

621
00:49:38,880 --> 00:49:42,420
我々はそれをスタックに宣言した場合ので、私たちは、ヒープ上にそれを宣言しなければならない

622
00:49:42,420 --> 00:49:45,050
我々はこのように、この関数の中でそれを行うことができないでしょう。

623
00:49:45,050 --> 00:49:47,690
そのメモリの範囲の外に行くだろう

624
00:49:47,690 --> 00:49:51,590
我々は、後でそれにアクセスしようとした場合と無効になります。

625
00:49:51,590 --> 00:49:53,500
我々は、ヒープ上のメモリを宣言しているので、

626
00:49:53,500 --> 00:49:55,830
我々は、後でそれを解放するの世話をする必要があるとしている

627
00:49:55,830 --> 00:49:58,530
我々のプログラムのために、任意のメモリリークが発生しないように。

628
00:49:58,530 --> 00:50:01,270
我々は、コード内の他のすべてのためにそれにけってきた

629
00:50:01,270 --> 00:50:02,880
ただ当時の簡略化のため、

630
00:50:02,880 --> 00:50:05,610
しかし、あなたは今までにこのような関数を記述する場合

631
00:50:05,610 --> 00:50:10,370
あなたが持っているどこに - いくつかは、その中にmallocやreallocを呼ぶ - 

632
00:50:10,370 --> 00:50:14,330
あなたは、あなたが言う、ここにコメントのいくつかの並べ替えを置くことを確認したい

633
00:50:14,330 --> 00:50:29,970
ねえ、あなたが知っている、渡された値で初期化されたヒープに割り当てられたノードを返します。

634
00:50:29,970 --> 00:50:33,600
そして、あなたが言うノートのいくつかの並べ替えに置くことを確認したい

635
00:50:33,600 --> 00:50:41,720
呼び出し元は、返されたメモリを解放する必要があります。

636
00:50:41,720 --> 00:50:45,450
そうすれば、誰かがこれまで行くとすると、その関数を使用しています

637
00:50:45,450 --> 00:50:48,150
彼らは、その関数から戻ってどんなことを知っている

638
00:50:48,150 --> 00:50:50,870
いくつかの時点で解放する必要があります。

639
00:50:50,870 --> 00:50:53,940
>> 、すべてがここでいいであると仮定すると

640
00:50:53,940 --> 00:51:02,300
私達は私達のコードに下ると右ここで、これらのすべての行を置き換えることができます

641
00:51:02,300 --> 00:51:05,410
私たちのビルドノード関数への呼び出しを使用して。

642
00:51:05,410 --> 00:51:08,170
のは、本当に迅速にやってみましょう。

643
00:51:08,170 --> 00:51:15,840
我々は交換するつもりはないことを1の部分は、ダウンここでは、この部分です

644
00:51:15,840 --> 00:51:18,520
私たちが実際にお互いを指すようにノードを配線下部に、

645
00:51:18,520 --> 00:51:21,030
そのため、我々は関数の中で行うことはできません。

646
00:51:21,030 --> 00:51:37,400
しかし、聞かせてやるルート= build_node（7）;ノード* 3 = build_node（3）;

647
00:51:37,400 --> 00:51:47,980
ノード* 6 = build_node（6）;ノード* 9 = build_node（9）;

648
00:51:47,980 --> 00:51:52,590
そして今、我々はまたのためにノードを追加したい - 

649
00:51:52,590 --> 00:52:03,530
ノード* 5 = build_node（5）;ノード* 8 = build_node（8）;

650
00:52:03,530 --> 00:52:09,760
そしてもう一方のノードは何でしたか？ここを参照してみましょう。我々はまた、2を追加したい - 

651
00:52:09,760 --> 00:52:20,280
ノードには、* 2 = build_node（2）;

652
00:52:20,280 --> 00:52:26,850
よし。この時点で、我々は7、3,9、および6を持っていることを知っている

653
00:52:26,850 --> 00:52:30,320
適切に配線されたすべてが、どのような約5、8、2？

654
00:52:30,320 --> 00:52:33,550
適切な順序ですべてを保つために、

655
00:52:33,550 --> 00:52:39,230
我々は3つの右の子が6であることを知っています。

656
00:52:39,230 --> 00:52:40,890
だから、我々は5を追加するつもりなら、

657
00:52:40,890 --> 00:52:46,670
5はまた、3ルートとなっている木の右側に属し

658
00:52:46,670 --> 00:52:50,440
ので、5、6の左の子として所属しています。

659
00:52:50,440 --> 00:52:58,650
我々は、6を言って、これを行うことができます - > left_child = 5;

660
00:52:58,650 --> 00:53:10,790
その後8ので9、9の左の子として所属 - > left_child = 8;

661
00:53:10,790 --> 00:53:22,190
その後2が3の左の子ですので、我々はここまでそれを行うことができます - なた - > left_child = 2;

662
00:53:22,190 --> 00:53:27,730
あなたは非常にそれに沿って実行しなかった場合、私はあなたがそれを自分で引き出すお勧めします。

663
00:53:27,730 --> 00:53:35,660
>> よし。これを保存してみましょう。 Let 'sは、外に出て、それをコンパイルしていることを確認し

664
00:53:35,660 --> 00:53:40,760
それから私達は私達のcontainsの呼び出しを追加することができます。

665
00:53:40,760 --> 00:53:44,120
すべてがまだコンパイルのように見えます。

666
00:53:44,120 --> 00:53:51,790
のがに行くといくつかの呼び出しが含まれているに追加してみましょう。

667
00:53:51,790 --> 00:53:59,640
繰り返しますが、私はコピー＆ペーストの少しを行うつもりです。

668
00:53:59,640 --> 00:54:15,860
今では5,8、および2の検索してみましょう。よし。

669
00:54:15,860 --> 00:54:28,330
レッツは、このすべてがまだ良く見えていることを確認してください。すばらしい！保存して終了します。

670
00:54:28,330 --> 00:54:33,220
さて、コンパイルしてみましょう、と今度は実行してみましょう。

671
00:54:33,220 --> 00:54:37,540
すべてがちょうどいいとうまく機能しているような結果から、それが見えます。

672
00:54:37,540 --> 00:54:41,780
すばらしい！だから今我々は我々のcontainsが書かれた関数持っている。

673
00:54:41,780 --> 00:54:46,160
レッツに移動し、ツリーにノードを挿入する方法で作業を開始

674
00:54:46,160 --> 00:54:50,000
我々は今それをやっているように、以来、物事は非常にきれいではありません。

675
00:54:50,000 --> 00:54:52,280
>> 我々は、仕様に戻った場合は、

676
00:54:52,280 --> 00:55:00,540
それは、インサートと呼ばれる関数を記述することが求​​められます - もう一度、boolを返す

677
00:55:00,540 --> 00:55:04,400
かどうかのために私たちは実際にツリーにノードを挿入することができます - 

678
00:55:04,400 --> 00:55:07,710
その後木に挿入する値は次のように指定されている

679
00:55:07,710 --> 00:55:11,060
私たちのinsert関数に引数のみ。

680
00:55:11,060 --> 00:55:18,180
我々は確かにツリーにノードを含む値を挿入することができれば、trueを返します

681
00:55:18,180 --> 00:55:20,930
これは、我々、人は、十分なメモリを持っていたことを意味します

682
00:55:20,930 --> 00:55:24,840
その後2、そのノードは既に以来ツリーに存在していなかった - 

683
00:55:24,840 --> 00:55:32,170
覚えて、我々は物事を簡単にするには、ツリー内の重複する値を持っているつもりはありません。

684
00:55:32,170 --> 00:55:35,590
よし。コー​​ドに戻る。

685
00:55:35,590 --> 00:55:44,240
それを開く。少しのズームは、次にスクロールダウンします。

686
00:55:44,240 --> 00:55:47,220
のが右のcontains上記insert関数を入れてみましょう。

687
00:55:47,220 --> 00:55:56,360
再び、それはboolインサート（int値）と呼ばれるようになるだろう。

688
00:55:56,360 --> 00:56:01,840
デフォルトとして、それを少しより多くのスペースを与え、そして、

689
00:56:01,840 --> 00:56:08,870
のは非常に末尾のreturn falseを入れてみましょう。

690
00:56:08,870 --> 00:56:22,620
今すぐダウン下部に、先に進み、代わりに手動でノードを構築しましょう

691
00:56:22,620 --> 00:56:27,900
メインで自分自身と配線それらを我々がやっているようにお互いを指すように、

692
00:56:27,900 --> 00:56:30,600
我々はそれを行うために私達のinsert関数に依存します。

693
00:56:30,600 --> 00:56:35,510
我々は、ちょうどまだ最初からツリー全体を構築するために私達のinsert関数に依存しません

694
00:56:35,510 --> 00:56:39,970
むしろ我々は、これらの行を取り除くでしょう -  we'llは、これらの行をコメントアウトします - 

695
00:56:39,970 --> 00:56:43,430
それは、ノード5,8、および2を構築します。

696
00:56:43,430 --> 00:56:55,740
そしてその代わりに、我々はinsert関数への呼び出しを挿入します

697
00:56:55,740 --> 00:57:01,280
実際に動作することを確認します。

698
00:57:01,280 --> 00:57:05,840
ここに私達は行く。

699
00:57:05,840 --> 00:57:09,300
>> 今、私たちは、これらの行をコメントアウトしました。

700
00:57:09,300 --> 00:57:13,700
私たちはこの時点で私たちのツリーに7、3,9、および6を持っています。

701
00:57:13,700 --> 00:57:18,870
これがすべて動作していることを確認し、

702
00:57:18,870 --> 00:57:25,050
我々は、我々のバイナリツリーを作成し、ズームアウトすることができます

703
00:57:25,050 --> 00:57:30,750
それを実行し、我々は今、我々は完全に右だということを告げている含まれていることがわかります - 

704
00:57:30,750 --> 00:57:33,110
5,8、および2は、ツリーではなくなっています。

705
00:57:33,110 --> 00:57:37,960
コー​​ドに戻って、

706
00:57:37,960 --> 00:57:41,070
そしてどのように我々は挿入するつもりですか？

707
00:57:41,070 --> 00:57:46,290
我々は実際に以前、8、2 5を挿入したときに我々が何をしたか覚えています。

708
00:57:46,290 --> 00:57:50,100
我々は、我々はルートで開始したPlinkoゲームをプレイ

709
00:57:50,100 --> 00:57:52,780
一つずつ、ツリー1を下った

710
00:57:52,780 --> 00:57:54,980
我々は適切なギャップを発見するまで、

711
00:57:54,980 --> 00:57:57,570
その後、我々は適切な場所にノードに配線。

712
00:57:57,570 --> 00:57:59,480
私たちは同じことをやろうとしている。

713
00:57:59,480 --> 00:58:04,070
これは、我々が含まれている関数の中で使われているコードを書くようなもの基本的には

714
00:58:04,070 --> 00:58:05,910
ノードがどこにあるべき場所を見つけるために、

715
00:58:05,910 --> 00:58:10,560
それから私達はちょうどそこにノードを挿入しようとしている。

716
00:58:10,560 --> 00:58:17,000
ことをやってみましょう。

717
00:58:17,000 --> 00:58:24,200
>> だから我々は、ノード*電流=ルートを持って、我々は、単にコードが含まれてフォローするつもりだ

718
00:58:24,200 --> 00:58:26,850
我々はそれが非常に私たちのために動作しないことに気づくまで。

719
00:58:26,850 --> 00:58:32,390
我々は、現在の要素がnullでないときにツリーを通過しようとしている、

720
00:58:32,390 --> 00:58:45,280
我々が発見した場合、その電流の値は、我々は挿入しようとしている値と等しいです - 

721
00:58:45,280 --> 00:58:49,600
まあ、これは我々が実際にノードを挿入できませんでしたケースの一つである

722
00:58:49,600 --> 00:58:52,730
ツリーにこれは我々が重複した値を持つことを意味するので。

723
00:58:52,730 --> 00:58:59,010
ここでは、実際にはfalseを返すつもりだ。

724
00:58:59,010 --> 00:59:08,440
さて、誰か他の電流の値が値よりも小さい場合、

725
00:59:08,440 --> 00:59:10,930
今、我々は右に移動することを知っている

726
00:59:10,930 --> 00:59:17,190
 値は、curの木の右半分に属しているため。

727
00:59:17,190 --> 00:59:30,110
そうでなければ、我々は左に移動するつもりです。

728
00:59:30,110 --> 00:59:37,980
それはすぐそこに、基本的に私たちのCONTAINS関数です。

729
00:59:37,980 --> 00:59:41,820
>> この時点で、一度我々は、このwhileループを完了しました

730
00:59:41,820 --> 00:59:47,350
当社curのポインタがNULLを指すことになるだろう

731
00:59:47,350 --> 00:59:51,540
場合、この関数は既に戻っていない。

732
00:59:51,540 --> 00:59:58,710
そこで我々は、我々は新しいノードを挿入したい箇所に電流を抱えている。

733
00:59:58,710 --> 01:00:05,210
何を行うことが残っていることは、実際に新しいノードを構築することである

734
01:00:05,210 --> 01:00:08,480
その我々はかなり簡単に行うことができます。

735
01:00:08,480 --> 01:00:14,930
我々は、我々の超便利なビルドノード機能を使用することができます

736
01:00:14,930 --> 01:00:17,210
我々が以前行っていないことと何か - 

737
01:00:17,210 --> 01:00:21,400
我々だけの種類のは当然のことだが、今は念のためにやる - 

738
01:00:21,400 --> 01:00:27,130
我々は、新しいノードによって返された値が実際にあったことを確認するためにテストします

739
01:00:27,130 --> 01:00:33,410
それがnullである場合、我々は、そのメモリへのアクセスを開始したくないので、nullではない。

740
01:00:33,410 --> 01:00:39,910
私たちは、新しいノードがnullに等しくないことを確認するためにテストすることができます。

741
01:00:39,910 --> 01:00:42,910
またはその代わりに、私たちは、それが実際にnullであるかどうかを確認できます

742
01:00:42,910 --> 01:00:52,120
それがnullである場合には、私たちはただ早いfalseを返すことができます。

743
01:00:52,120 --> 01:00:59,090
>> この時点で、我々は、ツリー内の適切な場所に新しいノードを配線する必要があります。

744
01:00:59,090 --> 01:01:03,510
私たちは主を振り返ると、ここで我々は、前に実際に値の配線だったら

745
01:01:03,510 --> 01:01:08,470
私たちはツリーに3を置きたいと思ったときの方法は、我々はそれをやっていたことがわかり

746
01:01:08,470 --> 01:01:11,750
我々は、ルートの左の子にアクセスしました。

747
01:01:11,750 --> 01:01:14,920
私たちはツリーに9を置くとき、私たちはルートの右の子にアクセスしなければならなかった。

748
01:01:14,920 --> 01:01:21,030
私たちは、木に新たな価値を置くために親へのポインタを持つ必要がありました。

749
01:01:21,030 --> 01:01:24,430
挿入するために戻って上にスクロールして、それはかなりここで働くことはないだろう

750
01:01:24,430 --> 01:01:27,550
私たちは、親のポインタを持っていないので。

751
01:01:27,550 --> 01:01:31,650
私たちに何ができるようにしたいことは、この時点では、ある

752
01:01:31,650 --> 01:01:37,080
親の値をチェックしてください - まあ、おやっ、

753
01:01:37,080 --> 01:01:41,990
親の値が現在の値よりも小さい場合、

754
01:01:41,990 --> 01:01:54,440
その後、親の右の子は、新しいノードでなければなりません。

755
01:01:54,440 --> 01:02:07,280
そうでなければ、親の左の子は、新しいノードでなければなりません。

756
01:02:07,280 --> 01:02:10,290
しかし、我々は非常にまだこの親のポインタを持っていない。

757
01:02:10,290 --> 01:02:15,010
>> 私たちは木を通って行くようにそれを得るために、我々は実際にそれを追跡する必要があるとしている

758
01:02:15,010 --> 01:02:18,440
そして先ほどのループ内の適切な場所を見つける。

759
01:02:18,440 --> 01:02:26,840
私たちは、insert関数の先頭に戻って上にスクロールしていることを行うことができます

760
01:02:26,840 --> 01:02:32,350
と別のポインタ変数を追跡することで、親を呼んだ。

761
01:02:32,350 --> 01:02:39,340
我々は、最初はnullに等しいそれを設定しようとしている

762
01:02:39,340 --> 01:02:43,640
私たちは木を通過した後、毎回、

763
01:02:43,640 --> 01:02:51,540
我々は現在のポインタと一致するように、親のポインタを設定しようとしている。

764
01:02:51,540 --> 01:02:59,140
電流に等しい親を設定します。

765
01:02:59,140 --> 01:03:02,260
このように、我々が通過するたびに、

766
01:03:02,260 --> 01:03:05,550
我々は現在のポインタにインクリメントされるようにするつもりだ

767
01:03:05,550 --> 01:03:12,640
親ポインタは、それに続く - ツリーの現在のポインタよりもちょうど1レベル高い。

768
01:03:12,640 --> 01:03:17,370
それはすべてのかなりよさそうだ。

769
01:03:17,370 --> 01:03:22,380
>> 私は我々が調整したいと思う一つのことは、これはnullを返すノードを構築だと思います。

770
01:03:22,380 --> 01:03:25,380
ためには実際には正常にnullを返すためにノードを構築し得るため、

771
01:03:25,380 --> 01:03:31,060
私たちは、そのコードを変更する必要があります

772
01:03:31,060 --> 01:03:37,270
ここにいるので、私たちは、mallocは有効なポインタが返されたことを確認するためにテストされない。

773
01:03:37,270 --> 01:03:53,390
だから、その後、（！N = NULL）の場合 - 

774
01:03:53,390 --> 01:03:55,250
mallocが有効なポインタが返された場合、次に我々はそれを初期化します;

775
01:03:55,250 --> 01:04:02,540
そうでなければ、私達はちょうど帰る、それが私たちのためにnullを返すことになります。

776
01:04:02,540 --> 01:04:13,050
今やすべてがかなりよさそうだ。のは、これは実際にコンパイルしていることを確認してみましょう。

777
01:04:13,050 --> 01:04:22,240
バイナリツリーを確認して、ああ、私たちはここで何が起こっているいくつかのものを持っている。

778
01:04:22,240 --> 01:04:29,230
>> 我々は関数の暗黙的な宣言がノードを構築するんだ。

779
01:04:29,230 --> 01:04:31,950
繰り返しますが、これらのコンパイラで、私たちは一番上から開始するつもりです。

780
01:04:31,950 --> 01:04:36,380
何を意味する必要があり、私は実際にそれを宣言した前に私はノードを構築呼んでいるということです。

781
01:04:36,380 --> 01:04:37,730
のは本当にすぐにコードに戻りましょう。

782
01:04:37,730 --> 01:04:43,510
下にスクロールして、案の定、私のinsert関数が宣言されています

783
01:04:43,510 --> 01:04:47,400
ビルドノード機能上、

784
01:04:47,400 --> 01:04:50,070
しかし、私はカバーの内側のノードを構築使用しようとしている。

785
01:04:50,070 --> 01:05:06,610
私は、そのコピーに行くつもりです - そして、一番上にここまでビルドノード機能の方法を貼り付けます。

786
01:05:06,610 --> 01:05:11,750
そうすれば、うまくいけば、それは動作します。これはもう行くのを挙げてみましょう。

787
01:05:11,750 --> 01:05:18,920
今ではすべてコンパイルされます。すべてが良いです。

788
01:05:18,920 --> 01:05:21,640
>> しかし、この時点で、我々は、実際に私たちのinsert関数を呼び出していない。

789
01:05:21,640 --> 01:05:26,510
我々は、ちょうどそれがコンパイルされることを知っているので、のがに行くといくつかのコールをインチ置くよう

790
01:05:26,510 --> 01:05:28,240
私たちの主な機能で、その処理を行いましょう。

791
01:05:28,240 --> 01:05:32,390
ここで、我々は、5,8、および2をコメントアウト

792
01:05:32,390 --> 01:05:36,680
それから私達はここにそれらを配線しませんでした。

793
01:05:36,680 --> 01:05:41,640
いくつかのコールを挿入するようにしましょう​​、

794
01:05:41,640 --> 01:05:46,440
とのはまた、我々が使用したものと同じ種類を使用してみましょう

795
01:05:46,440 --> 01:05:52,810
我々はすべてが正しく挿入されなかったことを確認するためにこれらのprintf関数の呼び出しを行ったとき。

796
01:05:52,810 --> 01:06:00,550
私は、コピーして貼り付けるつもりだ

797
01:06:00,550 --> 01:06:12,450
そして代わりに、我々は挿入をやろう​​としているが含まれています。

798
01:06:12,450 --> 01:06:30,140
とはなく、6、10、1の、我々は5 8、2、を使用するつもりです。

799
01:06:30,140 --> 01:06:37,320
これはうまくいけば木に5,8、および2を挿入する必要があります。

800
01:06:37,320 --> 01:06:44,050
コンパイルします。すべてが良いです。今、私たちは、実際に我々のプログラムを実行することになるでしょう。

801
01:06:44,050 --> 01:06:47,330
>> すべてはfalseが返された場合。

802
01:06:47,330 --> 01:06:53,830
だから、5、8、2は行かなかった、とCONTAINSは、それらを見つけることができませんでしたように見えます。

803
01:06:53,830 --> 01:06:58,890
どうなってるの？ズームアウトしてみましょう。

804
01:06:58,890 --> 01:07:02,160
最初の問題は、インサートがfalseを返すように見えたということでした

805
01:07:02,160 --> 01:07:08,750
そしてそれは私達が私達のリターン偽の呼び出しでおいたのでそれはだような、見える

806
01:07:08,750 --> 01:07:14,590
そして我々は実際に本当返されることはありません。

807
01:07:14,590 --> 01:07:17,880
私たちは、それを設定することができます。

808
01:07:17,880 --> 01:07:25,290
第二の問題は、我々が行う場合であっても、今ある - 、これを終了し、これを保存する

809
01:07:25,290 --> 01:07:34,530
makeを再度実行し、それを実行して、コンパイルしました - 

810
01:07:34,530 --> 01:07:37,670
私たちは、何か他のものがここで起きていることがわかります。

811
01:07:37,670 --> 01:07:42,980
5,8、および2はまだツリーで見つかることはありませんでした。

812
01:07:42,980 --> 01:07:44,350
だから、何が起こっているのですか？

813
01:07:44,350 --> 01:07:45,700
>> のは、コード内でこれを見てみましょう。

814
01:07:45,700 --> 01:07:49,790
我々はこれを理解できるかどうか見てみましょう。

815
01:07:49,790 --> 01:07:57,940
私たちは、親がNULLになることはないから始まります。

816
01:07:57,940 --> 01:07:59,510
我々は、ルートポインタに等しい現在のポインタを設定する

817
01:07:59,510 --> 01:08:04,280
そして我々は木を通って我々の道を降りていくつもりです。

818
01:08:04,280 --> 01:08:08,650
現在のノードがnullでない場合は、我々は少し下に移動することができることを知っている。

819
01:08:08,650 --> 01:08:12,330
我々は、現在のポインタと等しくなるように私たちの親のポインタを設定する

820
01:08:12,330 --> 01:08:15,420
値をチェック - 値が同じである場合、我々は、falseが返された場合。

821
01:08:15,420 --> 01:08:17,540
値が小さい場合、我々は右に移動;

822
01:08:17,540 --> 01:08:20,399
そうでなければ、我々は左に移動しました。

823
01:08:20,399 --> 01:08:24,220
その後、我々はノードを構築します。私は少しでズームインします。

824
01:08:24,220 --> 01:08:31,410
そしてここで、我々は同じになるように値を配線しようとするつもりだ。

825
01:08:31,410 --> 01:08:37,250
どうなってるの？おそらくValgrindは私たちにヒントを与えることができるかどうかを確認してみましょう。

826
01:08:37,250 --> 01:08:43,910
>> 私はValgrindは本当にすぐに実行という理由だけでValgrindは使いたい

827
01:08:43,910 --> 01:08:46,729
任意のメモリエラーがある場合は、あなたに伝えます。

828
01:08:46,729 --> 01:08:48,300
我々は、コードにValgrindはを実行すると

829
01:08:48,300 --> 01:08:55,859
あなたが見ることができるように右here--Valgrind./binary_tree--andのエンターキーを押します。

830
01:08:55,859 --> 01:09:03,640
あなたは、私たちは任意のメモリエラーを持っていなかったことがわかりますので、すべてが今のところ大丈夫みたいだ。

831
01:09:03,640 --> 01:09:07,529
我々はわからないので、私たちは、私たちが知っているいくつかのメモリリークを、持っている

832
01:09:07,529 --> 01:09:08,910
私たちのいずれかのノードを解放するために起こっている。

833
01:09:08,910 --> 01:09:13,050
実際に何が起こっているのを見て、GDBを実行してみましょう。

834
01:09:13,050 --> 01:09:20,010
私たちは、gdbをやる。/ binary_tree。それだけで正常に起動。

835
01:09:20,010 --> 01:09:23,670
の挿入時にブレークポイントを設定してみましょう。

836
01:09:23,670 --> 01:09:28,600
のは、実行してみましょう。

837
01:09:28,600 --> 01:09:31,200
それは我々が実際にインサートと呼ばれることがないように見えます。

838
01:09:31,200 --> 01:09:39,410
問題は、私は主にここに降りて変更されたときだけのことであったように見えます - 

839
01:09:39,410 --> 01:09:44,279
含まれていますから、これらのprintfの呼び出しのすべて - 

840
01:09:44,279 --> 01:09:56,430
私は実際にインサートを呼び出すために、これらを変更することはありません。

841
01:09:56,430 --> 01:10:01,660
今度はそれを試してみましょう。コンパイルしてみましょう。

842
01:10:01,660 --> 01:10:09,130
すべてはそこに良さそうに見える。今それを実行してみましょう、何が起こるかを参照してください。

843
01:10:09,130 --> 01:10:13,320
よし！すべてがそこにかなりよさそうだ。

844
01:10:13,320 --> 01:10:18,130
>> 考えるための最終的なものであり、この挿入に任意のエッジケースがありますか？

845
01:10:18,130 --> 01:10:23,170
そしてそれは常に考えることは興味深い1エッジケース、まあ、ことが判明

846
01:10:23,170 --> 01:10:26,250
あなたのツリーが空であり、このinsert関数を呼び出す場合に何が起こるか、ですか？

847
01:10:26,250 --> 01:10:30,330
それは動作しますか？まあ、のはそれを試してみましょう。

848
01:10:30,330 --> 01:10:32,110
 -  binary_tree C  - 

849
01:10:32,110 --> 01:10:35,810
我々はこれをテストするつもりだ方法は、我々は、私たちの主な機能にまで行くつもりさ

850
01:10:35,810 --> 01:10:41,690
とではなく、このような配線はこれらのノードを構成するのではなく、

851
01:10:41,690 --> 01:10:56,730
我々だけで、全体の事をコメントアウトするつもりだ

852
01:10:56,730 --> 01:11:02,620
そして代わりにノード自身、アップ配線

853
01:11:02,620 --> 01:11:09,400
私たちは実際にちょうど先に行くとこれのすべてを削除することができます。

854
01:11:09,400 --> 01:11:17,560
私たちはすべて挿入するための呼び出しをするつもりだ。

855
01:11:17,560 --> 01:11:49,020
それでは、やらせる - の代わりに5、8、2、我々は3,7を挿入して、9になるだろう。

856
01:11:49,020 --> 01:11:58,440
そして、我々はまた、同様に6を挿入したいと思う。

857
01:11:58,440 --> 01:12:05,190
保存します。終了します。バイナリツリーを作成します。

858
01:12:05,190 --> 01:12:08,540
それはすべてコンパイルされます。

859
01:12:08,540 --> 01:12:10,320
私たちはただ、それをそのまま実行すると何が起こるかを見ることができます

860
01:12:10,320 --> 01:12:12,770
それはまたことを確認するために、本当に重要なことになるだろう

861
01:12:12,770 --> 01:12:14,740
我々は、任意のメモリエラーを持っていない

862
01:12:14,740 --> 01:12:16,840
これは我々が知っている私たちの最先端の例の1つなので。

863
01:12:16,840 --> 01:12:20,150
>> レッツは、それがValgrindでうまく動作することを確認する

864
01:12:20,150 --> 01:12:28,310
その我々がちょうどValgrindの。/ binary_treeを実行してやる。

865
01:12:28,310 --> 01:12:31,110
我々は確かに一つの文脈からエラーを1つ持っているように見えます - 

866
01:12:31,110 --> 01:12:33,790
我々は、このセグメンテーションフォールトを持っています。

867
01:12:33,790 --> 01:12:36,690
何が起こったのか？

868
01:12:36,690 --> 01:12:41,650
それがどこにあるかValgrindは、実際に教えてくれる。

869
01:12:41,650 --> 01:12:43,050
少しズームアウトします。

870
01:12:43,050 --> 01:12:46,040
それが私たちのinsert関数で何が起こっているようにそれは、見え

871
01:12:46,040 --> 01:12:53,420
我々は挿入でサイズ4の不正な読み取りを持って、60行目。

872
01:12:53,420 --> 01:13:03,590
の前に戻って、ここで何が起こっているのか見てみましょう。

873
01:13:03,590 --> 01:13:05,350
本当に速いズームアウトします。

874
01:13:05,350 --> 01:13:14,230
私たちはすべてを見ることができるので、それが画面の端に行かないことを確認したい。

875
01:13:14,230 --> 01:13:18,760
少しでそれを引き出します。よし。

876
01:13:18,760 --> 01:13:35,030
下にスクロールして、問題はまさにここです。

877
01:13:35,030 --> 01:13:40,120
、私たちが降りる場合はどうなりますか、私たちの現在のノードがすでにnullである

878
01:13:40,120 --> 01:13:44,010
我々は非常に上、右ここで見上げるので、もし私たちの親ノードがnullの場合 - 

879
01:13:44,010 --> 01:13:47,340
このwhileループは、実際には決して実行されない場合

880
01:13:47,340 --> 01:13:52,330
我々の現在の値がnullであるため -  curがnullであるように私達のルートがnullである - 

881
01:13:52,330 --> 01:13:57,810
その後、私たちの親は、最新版にするか、有効な値に設定されることはありませ

882
01:13:57,810 --> 01:14:00,580
そう、親もnullになります。

883
01:14:00,580 --> 01:14:03,700
我々はそれをチェックするために覚えておく必要が

884
01:14:03,700 --> 01:14:08,750
時間によって、私たちはここで降りて、私たちは親の値へのアクセスを開始。

885
01:14:08,750 --> 01:14:13,190
だから、何が起こりますか？まあ、親がnullの場合 - 

886
01:14:13,190 --> 01:14:17,990
（親== NULL）の場合 - その後、私たちは知っている

887
01:14:17,990 --> 01:14:19,530
ツリーには何があってはなりません。

888
01:14:19,530 --> 01:14:22,030
我々はルートにそれを挿入しようとしなければなりません。

889
01:14:22,030 --> 01:14:32,570
私達はちょうど新しいノードに等しいルートを設定することにより、それを行うことができる。

890
01:14:32,570 --> 01:14:40,010
すると、この時点で、我々は実際にこれらの他のものを通過する必要はありません。

891
01:14:40,010 --> 01:14:44,780
代わりに、右ここで、我々は、のelse-if-elseのいずれかを行うことができます

892
01:14:44,780 --> 01:14:47,610
または我々は、他のここですべてのものを組み合わせることができます

893
01:14:47,610 --> 01:14:56,300
しかし、ここで我々はちょうど他の使用して、それをそのようにするつもりだ。

894
01:14:56,300 --> 01:14:59,030
今、私たちは私たちの親がnullでないことを確認するためにテストするつもりだ

895
01:14:59,030 --> 01:15:02,160
その前に実際にそのフィールドにアクセスしようとしている。

896
01:15:02,160 --> 01:15:05,330
これは、私たちはセグメンテーションフォールトを避けるのを助けるでしょう。

897
01:15:05,330 --> 01:15:14,740
だから、我々が終了し、実行、コンパイル、ズームアウトします。

898
01:15:14,740 --> 01:15:18,130
>> エラーはありませんが、我々はまだメモリリークの束を持っているん

899
01:15:18,130 --> 01:15:20,650
我々は任意のノードを解放しなかったため。

900
01:15:20,650 --> 01:15:24,350
しかし、我々がここまで行くと、我々のプリントアウトを見れば、

901
01:15:24,350 --> 01:15:30,880
我々は良いです、trueを返したが、まあ、私たちのインサートのすべてのように見えることがわかります。

902
01:15:30,880 --> 01:15:33,050
挿入はすべてtrueになり、

903
01:15:33,050 --> 01:15:36,670
し、適切なCONTAINSコールもまた真である。

904
01:15:36,670 --> 01:15:41,510
>> 仕事グッド！我々は正常にインサートを書いているように見えます。

905
01:15:41,510 --> 01:15:47,430
それは私たちが今週の問題セットの仕様のために持っているすべてです。

906
01:15:47,430 --> 01:15:51,720
考えるための一つの楽しいチャレンジは、あなたが実際に行くとどのように

907
01:15:51,720 --> 01:15:55,340
そしてこのツリー内のノードのすべての自由。

908
01:15:55,340 --> 01:15:58,830
我々は、そう多くの異なった方法を行うことができます

909
01:15:58,830 --> 01:16:01,930
しかし、私は、実験にあなたにすることをお任せします

910
01:16:01,930 --> 01:16:06,080
そして楽しい挑戦として試してみて、あなたが確認することができていることを確認してください

911
01:16:06,080 --> 01:16:09,490
このValgrindのレポートは、エラーや漏れが返されないことを確認します。

912
01:16:09,490 --> 01:16:12,880
>> 今週のハフマン符号化の問題セットで頑張って、

913
01:16:12,880 --> 01:16:14,380
そして我々は来週お会いしましょう​​！

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]