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
이 배열에 대한 기억, 둘은 정말 좋은 일

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
예를 들면, 배열의 세 번째 요소를 마시고 싶으면 -

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에서 널 포인터가 왼쪽 아무 것도 없다는 것을 나타냅니다.

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
예를 들어,이 링크 목록에 네 번째 요소를 찾으려면,

71
00:04:40,950 --> 00:04:43,510
나는이 목록의 맨 처음부터 시작해야 겠어

72
00:04:43,510 --> 00:04:48,930
제가 번째 하나를 찾을 때까지 노드의 노드 수를 헤아을 통해 내 방식대로 작동합니다.

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
우리는 이진 트리 노드에 두 번째 포인터를 추가 할거야.

80
00:05:16,950 --> 00:05:19,950
보다는 다음 요소에 하나의 포인터를 갖는

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
예를 들어,이 하나의 노드 - 값 7을 포함하는이 노드

114
00:07:43,360 --> 00:07:45,500
- 널 왼쪽 및 오른쪽 아이 포인터로

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 구 모두.

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 노드에서 해당 NULL 포인터를 지울거야

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
그 두 아이 포인터를 가지고 있다는 것입니다.

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 글자 각각에 대해 하나

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
하지만 여기, 이건 진 이후, 우리는 두 아이 포인터가 있습니다.

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
한 노드가 다른 노드의 하위되는 것이 무엇을 뜻합니까?

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는 한 자녀 6이 있습니다.

160
00:11:30,940 --> 00:11:37,430
그 포인터 모두 우리가 지금 그려 줄게 널, 때문에 여섯 또한 자식이 없습니다.

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
대신 두가 인간과 예상대로 - 각각의 노드는 하나의 부모가 있습니다.

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
루트에서 해당 노드에 대한 경로에 누워 노드에 있습니다.

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
그래서 7의 자손으로 3, 9, 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
만 어느 한 루트가 있습니다.

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
이러한 값은 모두 일곱보다이며, 오른쪽에있는 모든 - 그냥이 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
3 갖는 것은, 7의 왼쪽 자식 대신에

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의 오른쪽 자식으로, 우리는 두 가지 가능성이 있습니다.

235
00:17:19,869 --> 00:17:25,380
첫째, 우리는 9 다음 7이 있으며 수

236
00:17:25,380 --> 00:17:28,850
또는 우리가 그릴 수 있어요 - I가 여기서 할 것 같은 -

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 루트 만 가능한 값이 아닙니다.

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
또는, 우리는 7, 다음, 다음, 9 6 3 할 수 있습니다.

249
00:18:26,710 --> 00:18:35,020
또는, 우리는 9, 다음, 다음, 6 7 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 우리는 7 다음 6 할 수 있습니다.

253
00:18:54,710 --> 00:19:06,980
또는, 우리는 그 다음에, 7 9 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
각 노드는 하나의 자녀가

260
00:19:32,670 --> 00:19:38,950
그래서 우리는 예를 들어, 우리가 보는이 나무와 같은 구조를가 없습니다

261
00:19:38,950 --> 00:19:44,720
 하단 왼쪽에 이쪽 건 외로운 나무 인치

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
루트에서 시작하여 다음 트리에서 가장 먼 노드에 도착.

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
그런 다음 1 홉 (Hop) 6로 이동하려면 7까지가는 ​​두 번째 홉을해야

280
00:21:14,510 --> 00:21:20,560
세 번째 홉 (Hop)는 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까지 한 홉을해야하고 9 얻는 두 번째 홉

291
00:22:17,840 --> 00:22:21,240
와 마찬가지로, 7에서 두 번째 홉 (Hop)는 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
한 노드로 하나의 노드 -

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
그러나이 시점에서, 우리는 우리가 널 노드에 걸 눈치 채 셨을 거에요.

346
00:26:20,350 --> 00:26:23,080
거기 엔 아무 것도 없어요. 10이 있어야 할 건 없어요.

347
00:26:23,080 --> 00:26:29,360
나무에 열이 실제로 없다는 것을 - 우리가 실패를보고 할 수있는 곳입니다.

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
이 시점에서 우리가 널 노드를 가지고, 그래서 우리는 실패를보고 할 수 있습니다.

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
로 펜과 종이, 또는이 경우에는 아이 패드와 스타일러스.

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
내 보관 폴더로 이동, 제 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
제가 보관 폴더로 갈거야 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
우리가 구조체 노드 포인터를 갖고 싶어하므로 우리는 다음 참조 할 수 있도록

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
그리고 구조체 노드 * 오른쪽 자식,. 좋아.

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 메인 (int는 argc, const 숯불 * 변수는 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
반대로 I는 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
정수 또는 포인터의 크기의 크기 -

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
다른 이유는 컴파일러가 구조체에두고있는 패딩있을 수 있다는 점입니다.

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
9 3, 6를 포함하는 하나 하나를 포함하는 하나 -

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을 설정하는거야.

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 포함의 노드, 9를 포함하는 6를 포함하는 우리의 노드와 노드.

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
모든 nulls가 적절한 장소에가에 있는지 확인합니다.

479
00:38:08,240 --> 00:38:15,630
>> 루트에서 시작하여, 내가 루트의 왼쪽 아이가 셋 것을 알고있다.

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
'BOOL 포함되어 있습니다 (int 값)'의 프로토 타입이 있습니다.

489
00:39:14,150 --> 00:39:17,060
그리고이 함수가 TRUE를 반환 것입니다 포함되어 있습니다

490
00:39:17,060 --> 00:39:21,200
 나무는 우리의 글로벌 루트 변수에 의해을 지적하는 경우

491
00:39:21,200 --> 00:39:26,950
 기능과 허위 기타에 전달 된 값이 포함되어 있습니다.

492
00:39:26,950 --> 00:39:29,000
가 가서 그런 짓을 보자.

493
00:39:29,000 --> 00:39:35,380
지금이 바로 우리가 조금 전에 아이 패드에 손으로 한 것을 조회처럼 될 것입니다.

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
나는 가서 그냥 거짓 돌아 평등을 설정하는거야.

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
어떤는 표준 BOOL 헤더 파일에 포함되어 있습니다.

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
이 컴파일됩니다. 가 내려 가서 우리가 포함 기능에 몇 가지 호출을 삽입되었는지 확인하자 -

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 개) = because

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
그리고 우리가 어떻게 할 거냐는 3 원 연산자를 사용합니다.

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
문자열 "사실"가 될 것입니다.

540
00:43:04,850 --> 00:43:07,690
하자 조금 위에 스크롤됩니다.

541
00:43:07,690 --> 00:43:16,210
그렇지 않으면, 우리는 거짓 여섯 반품이 포함되어있는 경우 문자열은 "false"를 보내려고합니다.

542
00:43:16,210 --> 00:43:19,730
이 약간 정신 이상자 모양이지만, 나는뿐만 아니라 설명 할 수 파악

543
00:43:19,730 --> 00:43:23,780
어떤 3 중 연산자는 우리가 한동안 못 봤어요부터 것 같습니다.

544
00:43:23,780 --> 00:43:27,670
이것은 우리가 포함되어 기능이 제대로 작동하는지 파악 할 수있는 좋은, 편리한 방법이 될 것입니다.

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
또는 오히려, 우리가 FALSE 리턴에 넣어어요 -

563
00:44:59,800 --> 00:45:03,300
우리는 그냥 모두에 대해 잘못된 반환 있다고 볼 수

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
우리가 널 노드에와있는 것으로 나타났습니다.

580
00:46:12,640 --> 00:46:20,720
현재는 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
10 트리하지 않기는 트리에서 6 발견, 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
우리는 코드에서 다른 모든 것을 거기에 punting 있었어요

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
우리가 대체 할 수 없어하는 한 부분은 여기이 부분이

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), 노드 * 세 = build_node (3);

647
00:51:37,400 --> 00:51:47,980
노드 * 여섯 = build_node (6), 노드 * 구 = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
이제, 우리는 또한에 노드를 추가하고 싶어 -

649
00:51:52,590 --> 00:52:03,530
노드 * 오 = build_node (5), 노드 * 팔 = build_node (8);

650
00:52:03,530 --> 00:52:09,760
와 다른 노드는 무엇 이었습니까? 여기 보자. 우리는 또한 2를 추가하고 싶어 -

651
00:52:09,760 --> 00:52:20,280
노드 * 두 사람은 = 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
우리 세의 오른쪽 아이는 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
우리는 여섯 말하여이 작업을 수행 할 수 있습니다 -> left_child = 오;

660
00:52:58,650 --> 00:53:10,790
;> left_child = 팔 - 후 8 9 명, 9의 왼쪽 자식으로 속

661
00:53:10,790 --> 00:53:22,190
그리고 2 세의 왼쪽 자식, 그래서 우리가 여기 할 수 - 그대를 -> left_child = 2;.

662
00:53:22,190 --> 00:53:27,730
당신이 꽤 많이와 함께 수행하지 않은 경우, 당신은 자신을 오래 끌어 좋습니다.

663
00:53:27,730 --> 00:53:35,660
>> 좋아. 의이 저장 보자. 가자, 나가서는 컴파일해야합니다

664
00:53:35,660 --> 00:53:40,760
그리고 우리는 우리가 포함되어 통화에 추가 할 수 있습니다.

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
좋아요! 이제 우리는 우리의가 포함되어 작성 제대로 작동있어.

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
우리의 삽입 기능에 유일한 인수입니다.

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
그리고 두 노드는 이미 이후 트리에 존재하지 않았어 -

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
가 바로이 포함되어 위의 삽입 기능을 넣어 보자.

687
00:55:47,220 --> 00:55:56,360
다시, 그것은 (int 값) BOOL 삽입 호출 할거야.

688
00:55:56,360 --> 00:56:01,840
기본적으로 다음 조금 더 많은 공간을 지정하고,

689
00:56:01,840 --> 00:56:08,870
가 매우 끝 부분에 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
우리는 그 작업을 수행하기 위해 삽입 기능에 의존합니다.

693
00:56:30,600 --> 00:56:35,510
우리는 아직 처음부터 전체 트리를 구축하기 위해 삽입 기능에 의존하지 않습니다

694
00:56:35,510 --> 00:56:39,970
오히려 우리는이 라인을 제거하는거야 - 꼭이 줄 주석 -

695
00:56:39,970 --> 00:56:43,430
그 노드 5, 8, 2을 구축 할 수 있습니다.

696
00:56:43,430 --> 00:56:55,740
그리고 대신에, 우리는 삽입 함수 호출을 삽입합니다

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
하나 하나 나무 하나를 추락

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
 값은 현재 트리의 오른쪽 절반에 속해 때문입니다.

727
00:59:17,190 --> 00:59:30,110
그렇지 않으면, 우리는 왼쪽으로 이동거야.

728
00:59:30,110 --> 00:59:37,980
그래서 기본적으로 우리가 포함되어 거기 기능입니다.

729
00:59:37,980 --> 00:59:41,820
>> 이 시점에서, 우리는이 동안 루프를 완료 한

730
00:59:41,820 --> 00:59:47,350
우리의 현재 포인터는 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
우리는 우리의 삽입 함수의 상단에 다시 스크롤하여 그렇게 할 수

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
부모 포인터는 다음에 - 트리에서 현재 포인터보다 한 단계 높다.

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
아래로 스크롤하고, 확실히 충분히, 내 삽입 함수는 선언

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
>> 그러나이 시점에서, 우리는 실제로 삽입 기능을 호출하지 않았습니다.

789
01:05:21,640 --> 01:05:26,510
우리는 그냥 컴파일 알고 있으니,이에 가서 전화를 인치 놓고

790
01:05:26,510 --> 01:05:28,240
우리 main () 함수에서 해당 작업을 수행하자.

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
>> 다 가짜 돌아 왔습니다.

802
01:06:47,330 --> 01:06:53,830
그럼, 5, 8, 2 가지 않았어, 그리고이 포함되어 어느를 찾을 수 없습니다 것 같습니다.

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
값을 확인 - 값이 동일한 경우는 true를 반환.

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
그리고 밝혀 항상 생각하는 재미 하나의 에지 경우, 음,

846
01:10:23,170 --> 01:10:26,250
이며, 나무가이 비어있을 경우 어떤 일이 발생하고이 삽입 함수를 호출?

847
01:10:26,250 --> 01:10:30,330
작동됩니까? 음, 그것을 시도 줘.

848
01:10:30,330 --> 01:10:32,110
- binary_tree 다. -

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
이게 우리가 알고있는 우리의 에지 사례 중 하나이기 때문이다.

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
우리가 실제로 한 상황에서 하나의 오류를 가지고있는 것 같습니다 -

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
그게 우리의 삽입 기능에서 일어나고있는 것처럼 보이지만,

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
이 동안 루프는 실제로 수행되지 않는 경우

880
01:13:47,340 --> 01:13:52,330
현재 값은 널 (null)이기 때문에 - 현재이 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
대신, 여기, 우리는 다른 - 경우 - 다른 하나 할 수

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
우리는 좋은입니다 사실 반환 된, 음, 우리 삽입의 모든 것 같군요 참조하십시오.

902
01:15:30,880 --> 01:15:33,050
삽입은 모든 사실,

903
01:15:33,050 --> 01:15:36,670
한 다음 해당이 포함되어 호출에도 마찬가지입니다.

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]