1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> 케빈 슈 미드 : 때때로 구축 할 때
이 프로그램은, 당신은 사용 할 수 있습니다

3
00:00:10,890 --> 00:00:13,190
사전으로 알려진 데이터 구조.

4
00:00:13,190 --> 00:00:17,960
있습니다 사전지도 키,
일반적으로 문자열 값, 정수,

5
00:00:17,960 --> 00:00:21,900
문자, 일부 개체에 대한 포인터,
우리는 원하는대로.

6
00:00:21,900 --> 00:00:26,510
그냥 일반 사전처럼
정의를 통해 그지도는 말.

7
00:00:26,510 --> 00:00:29,440
>> 사전은 우리에게 제공
정보를 저장하는 능력

8
00:00:29,440 --> 00:00:32,750
뭔가와 관련된
나중에 그것을보고.

9
00:00:32,750 --> 00:00:36,620
어떻게 우리가 실제로 어떻게 구현합니까
C 코드, 말, 사전에 우리가 할 수있는

10
00:00:36,620 --> 00:00:38,460
우리의 프로그램 중 하나에서 사용할 수 있습니까?

11
00:00:38,460 --> 00:00:41,790
음, 많은 방법이 있습니다 그
우리는 사전을 구현할 수 있습니다.

12
00:00:41,790 --> 00:00:45,930
>> 하나, 우리는 배열을 사용할 수 있습니다 우리
동적으로 다시 크기 또는 우리가 사용할 수

13
00:00:45,930 --> 00:00:49,150
연결리스트, 해쉬 테이블
또는 이진 트리.

14
00:00:49,150 --> 00:00:52,250
하지만 우리가 무엇을 선택, 우리가해야
효율성을 염두하고

15
00:00:52,250 --> 00:00:54,300
구현의 성능을 제공합니다.

16
00:00:54,300 --> 00:00:57,930
우리는 사용 된 알고리즘에 대해 생각해야
삽입에 항목을 찾으려면

17
00:00:57,930 --> 00:00:59,120
우리의 데이터 구조입니다.

18
00:00:59,120 --> 00:01:03,060
>> 지금, 이제 우리를 가정 해 보자
문자열을 키로 사용합니다.

19
00:01:03,060 --> 00:01:07,290
의 하나의 가능성에 대해 얘기하자,
데이터 구조는 트라이 불렀다.

20
00:01:07,290 --> 00:01:11,210
그래서 여기에 시각적 표현이다
트라이의.

21
00:01:11,210 --> 00:01:14,590
>> 사진은 트라이에게 알 수 있듯이
와 트리 데이터 구조

22
00:01:14,590 --> 00:01:16,050
노드는 서로 연결.

23
00:01:16,050 --> 00:01:19,420
우리는 뿌리가 분명히 있다는 것을 참조
몇 가지 링크가 확장과 노드

24
00:01:19,420 --> 00:01:20,500
다른 노드.

25
00:01:20,500 --> 00:01:23,040
그러나 각 노드에 대해 어떻게 구성되어 있습니까?

26
00:01:23,040 --> 00:01:26,700
우리는 우리가 키를 저장한다고 가정하면
영문자와 함께

27
00:01:26,700 --> 00:01:30,150
우리는 자본에 대해 걱정하지 않는다,
여기 노드의 정의의 그

28
00:01:30,150 --> 00:01:31,100
충분합니다.

29
00:01:31,100 --> 00:01:34,130
>> 유형이 객체는 구조체입니다
노드는 두 부분으로 구성되어 있습니다

30
00:01:34,130 --> 00:01:35,740
데이터와 아이들을했다.

31
00:01:35,740 --> 00:01:39,200
우리는 주석으로 데이터 부분을 남겨 두었습니다
구성 요소에 의해 대체 될 수 있습니다

32
00:01:39,200 --> 00:01:43,190
구조체 노드 인 선언
C 프로그램에 포함.

33
00:01:43,190 --> 00:01:47,040
노드의 데이터 부분이 될 수도
나타내는 부울 값 여부

34
00:01:47,040 --> 00:01:51,160
하지 노드는 완료를 의미
사전 키 또는이 될 수 있습니다

35
00:01:51,160 --> 00:01:54,240
정의를 나타내는 문자열
사전에있는 단어.

36
00:01:54,240 --> 00:01:58,870
>> 우리는 나타 내기 위해 웃는 얼굴을 사용합니다
데이터 노드에 존재하는 경우.

37
00:01:58,870 --> 00:02:02,310
26 요소가 우리의
어린이 배열, 하나의 인덱스

38
00:02:02,310 --> 00:02:03,690
알파벳 문자 당.

39
00:02:03,690 --> 00:02:06,570
우리는 의미를 볼 수 있습니다
곧이의.

40
00:02:06,570 --> 00:02:10,759
>> 의 루트 노드의 면밀한 관찰을하자
우리의 그림에서, 이는 데이터가 없습니다

41
00:02:10,759 --> 00:02:14,740
로 나타낸 바와 같이, 그것과 관련된
에서 웃는 얼굴의 부재

42
00:02:14,740 --> 00:02:16,110
데이터 부분.

43
00:02:16,110 --> 00:02:19,910
의 부분으로부터 연장되는 화살표
어린이 배열이 아닌 노드를 나타냅니다

44
00:02:19,910 --> 00:02:21,640
다른 노드에 대한 포인터.

45
00:02:21,640 --> 00:02:25,500
예를 들어, 화살표부터 연장
아이들의 두 번째 요소

46
00:02:25,500 --> 00:02:28,400
문자 B를 나타냅니다
사전의 키.

47
00:02:28,400 --> 00:02:31,920
그리고 큰 그림에서
우리는 B를 레이블을

48
00:02:31,920 --> 00:02:35,810
>> 더 큰 그림의 점에 유의하면 우리
다른 노드에 대한 포인터를 그려, 그

49
00:02:35,810 --> 00:02:39,100
문제가되지 않는 곳 화살촉
다른 노드를 충족합니다.

50
00:02:39,100 --> 00:02:43,850
샘플 사전 트라이는 포함
두 단어, 즉 줌.

51
00:02:43,850 --> 00:02:47,040
의는의 예를 살펴 보겠습니다
키에 대한 데이터를 찾고입니다.

52
00:02:47,040 --> 00:02:50,800
>> 우리가보고 싶어한다고 가정
키 목욕 값을 해당.

53
00:02:50,800 --> 00:02:53,610
우리는 우리의 모습을 시작합니다
루트 노드.

54
00:02:53,610 --> 00:02:57,870
그런 다음 우리는 우리의 첫 번째 편지 할게요
키 B, 및 대응하는 정보를 찾아

55
00:02:57,870 --> 00:03:00,020
우리 아이 배열에 자리.

56
00:03:00,020 --> 00:03:04,490
정확히 26 반점이 있다는 것을 알 수
배열의 각 문자 하나

57
00:03:04,490 --> 00:03:05,330
알파벳.

58
00:03:05,330 --> 00:03:08,800
그리고 우리는 관광 명소가 표현해야합니다
순서대로 알파벳의 편지입니다.

59
00:03:08,800 --> 00:03:13,960
>> 우리는 두 번째 인덱스에 대해 알아 보겠습니다
일반적으로 B의 인덱스 하나, 만약에 우리

60
00:03:13,960 --> 00:03:17,990
일부 알파벳 문자 C의 우리가
해당 지점을 결정할 수

61
00:03:17,990 --> 00:03:21,520
사용하여 아이들의 배열
이 같은 계산.

62
00:03:21,520 --> 00:03:25,140
우리는 더 큰 아이들을 사용할 수도
우리는 모양 업을 제공하고 싶었 배열하는 경우

63
00:03:25,140 --> 00:03:28,380
다양한 문자와 키
예를 들면 전체로

64
00:03:28,380 --> 00:03:29,880
ASCII 문자를 설정합니다.

65
00:03:29,880 --> 00:03:32,630
>> 이 경우, 포인터
우리 아이 배열에있는

66
00:03:32,630 --> 00:03:34,320
인덱스에 null이 아닙니다.

67
00:03:34,320 --> 00:03:36,600
그래서 우리는 계속 찾고 있습니다
키 목욕 업.

68
00:03:36,600 --> 00:03:40,130
우리는 지금까지 널 포인터가 발생하는 경우
아이들의 적절한 자리에

69
00:03:40,130 --> 00:03:43,230
어레이 우리는 노드를 통과하는 동안,
우리는 우리 말을해야합니다

70
00:03:43,230 --> 00:03:45,630
해당 키에 대한 아무것도 찾을 수 없습니다.

71
00:03:45,630 --> 00:03:49,370
>> 이제, 우리는 두 번째 편지 할게요
우리의 키, A, 계속 다음

72
00:03:49,370 --> 00:03:52,400
이러한 방식으로 포인터 우리까지
우리 키의 단부에 도달한다.

73
00:03:52,400 --> 00:03:56,530
우리없이 키의 끝에 도달하면
죽은 끝을 타격, 널 포인터,

74
00:03:56,530 --> 00:03:59,730
경우는 여기로, 우리 만
한 가지 더 확인해야합니다.

75
00:03:59,730 --> 00:04:02,110
이 열쇠 실제로
사전에?

76
00:04:02,110 --> 00:04:07,660
>> 그렇다면, 우리는 잘 값을 찾아야한다
우리 그림의 웃는 얼굴 아이콘 위치

77
00:04:07,660 --> 00:04:08,750
단어가 종료됩니다.

78
00:04:08,750 --> 00:04:12,270
에 저장된 다른 뭔가가있는 경우
데이터는, 우리는 그것을 반환 할 수 있습니다.

79
00:04:12,270 --> 00:04:16,500
예를 들어, 키 동물원에없는
우리가 할 수 있더라도 사전,

80
00:04:16,500 --> 00:04:19,810
이제까지없이이 키의 끝에 도달
, 널 포인터를 치는 동안 우리

81
00:04:19,810 --> 00:04:21,089
트라이를 반복.

82
00:04:21,089 --> 00:04:25,436
>> 우리는 키 목욕을 올려 보았습니다 경우
마지막 노드의 배열 인덱스 두 번째,

83
00:04:25,436 --> 00:04:28,750
, 편지 H에 해당하는 것
널 포인터를 개최했다.

84
00:04:28,750 --> 00:04:31,120
그래서 목욕은 사전에 없습니다.

85
00:04:31,120 --> 00:04:34,800
그리고 트라이는 키에 고유
명시 적으로 저장되지 않습니다

86
00:04:34,800 --> 00:04:36,650
데이터 구조.

87
00:04:36,650 --> 00:04:38,810
그렇다면 우리는 무엇인가를 삽입합니까
트라이에?

88
00:04:38,810 --> 00:04:41,780
>> 의 키를 삽입하자
우리의 트라이에 동물원.

89
00:04:41,780 --> 00:04:46,120
기억이 노드에서 웃는 얼굴
간단한에 코드에 해당하는 수

90
00:04:46,120 --> 00:04:50,170
그 동물원를 나타내는 부울 값
사전에 또는 그것을 할 수

91
00:04:50,170 --> 00:04:53,710
자세한 내용에 해당하는 우리
키 동물원과 연결하려면,

92
00:04:53,710 --> 00:04:56,860
정의처럼
단어 또는 뭔가.

93
00:04:56,860 --> 00:05:00,350
어떤면에서, 프로세스는 삽입
트라이에 뭔가 비슷합니다

94
00:05:00,350 --> 00:05:02,060
트라이에서 뭔가를 찾고.

95
00:05:02,060 --> 00:05:05,720
>> 우리는 다시 루트 노드로 시작한다
다음 포인터에 해당하는

96
00:05:05,720 --> 00:05:07,990
우리의 키의 문자.

97
00:05:07,990 --> 00:05:11,310
다행히, 우리는 포인터를 수행 할 수 있었다
우리가 도달 할 때까지 모든 방법

98
00:05:11,310 --> 00:05:12,770
키의 단부.

99
00:05:12,770 --> 00:05:16,480
동물원은 단어의 접두사이기 때문에
의 구성원 줌,

100
00:05:16,480 --> 00:05:19,440
사전은, 우리가 할 필요가 없습니다
새로운 노드를 할당합니다.

101
00:05:19,440 --> 00:05:23,140
>> 우리는 표시하는 노드를 수정할 수
에 선행 문자의 경로

102
00:05:23,140 --> 00:05:25,360
우리의 사전에서 키를 나타냅니다.

103
00:05:25,360 --> 00:05:28,630
이제 삽입 해보자
트라이에 키 BATH.

104
00:05:28,630 --> 00:05:32,260
우리는 루트 노드에서 시작하자
다시 포인터를 따릅니다.

105
00:05:32,260 --> 00:05:35,620
그러나이 상황에서, 우리는 죽은 충돌
우리가 얻을 수있어 이전에 종료

106
00:05:35,620 --> 00:05:36,940
키의 끝.

107
00:05:36,940 --> 00:05:40,980
이제, 우리는 새로운 할당해야합니다
노드가 하나의 새로운 할당해야합니다

108
00:05:40,980 --> 00:05:43,660
나머지 각 노드에 대한
우리의 키의 문자.

109
00:05:43,660 --> 00:05:46,740
>> 이 경우, 우리는 단지 필요
하나의 새로운 노드를 할당 할 수 있습니다.

110
00:05:46,740 --> 00:05:50,590
그 다음 우리는 H 지수를 확인해야합니다
이 새로운 노드를 참조합니다.

111
00:05:50,590 --> 00:05:54,070
다시 한번, 우리는에 노드를 수정할 수 있습니다
나타낸다고 문자 경로

112
00:05:54,070 --> 00:05:57,120
그것을 선도를 나타냅니다
우리의 사전에있는 키를 누릅니다.

113
00:05:57,120 --> 00:06:00,730
의는 점근 적 추론하자
이러한 우리의 절차의 복잡성

114
00:06:00,730 --> 00:06:02,110
두 가지 작업.

115
00:06:02,110 --> 00:06:06,420
>> 우리는 알이 두 경우의 수
우리의 알고리즘은 한 걸렸다 단계

116
00:06:06,420 --> 00:06:09,470
의 개수에 비례
키워드의 편지.

117
00:06:09,470 --> 00:06:10,220
맞아요.

118
00:06:10,220 --> 00:06:13,470
당신의 단어를 검색 할 때
트라이 당신은 단지를 반복 할 필요가

119
00:06:13,470 --> 00:06:17,100
글자 하나 하나 때까지 하나
단어의 끝 또는 도달

120
00:06:17,100 --> 00:06:19,060
트라이에 막 다른 골목을 기록했다.

121
00:06:19,060 --> 00:06:22,470
>> 그리고 당신은 키를 삽입 할 때
사용 트라이에 값 쌍

122
00:06:22,470 --> 00:06:26,250
절차 우리는 최악의 경우를 논의
새로운 노드를 할당해야합니다

123
00:06:26,250 --> 00:06:27,550
각 문자.

124
00:06:27,550 --> 00:06:31,290
그리고 우리는 그 할당을 가정합니다
일정 시간 작업입니다.

125
00:06:31,290 --> 00:06:35,850
우리는 키 길이가 가정이 경우
고정 된 상수, 모두에 의해 제한

126
00:06:35,850 --> 00:06:39,400
삽입과 조회가 일정하다
트라이 시간 작업.

127
00:06:39,400 --> 00:06:42,930
>> 우리는이 가정을하지 않으면 그
키 길이는 고정에 묶여있다

128
00:06:42,930 --> 00:06:46,650
상수, 다음 삽입 및 조회,
최악의 경우에 선형

129
00:06:46,650 --> 00:06:48,240
키의 길이.

130
00:06:48,240 --> 00:06:51,800
아이템의 개수가 저장된 것을 알
트라이의 모습을 영향을주지 않습니다

131
00:06:51,800 --> 00:06:52,820
또는 삽입 시간.

132
00:06:52,820 --> 00:06:55,360
그것은 단지 영향있어
키의 길이.

133
00:06:55,360 --> 00:06:59,300
>> 반대로 말하자면,에 항목을 추가,
해시 테이블 만드는 경향

134
00:06:59,300 --> 00:07:01,250
미래는 느린 찾아보십시오.

135
00:07:01,250 --> 00:07:04,520
이 처음에는 매력적인 사운드 수 있지만
우리가 염두에 두어야하는

136
00:07:04,520 --> 00:07:08,740
유리한 점근 복잡하지 않습니다
말은 그 연습의 데이터

137
00:07:08,740 --> 00:07:11,410
구조가 필요하다
비난을 넘어.

138
00:07:11,410 --> 00:07:15,860
우리는 또한 저장하는 것을 고려해야합니다
최악의에서 우리가 필요로하는 트라이, 단어

139
00:07:15,860 --> 00:07:19,700
케이스, 노드들의 개수에 비례
단어 자체의 길이.

140
00:07:19,700 --> 00:07:21,880
>> 시도는 많은 공간을 사용하는 경향이있다.

141
00:07:21,880 --> 00:07:25,620
즉, 해시 테이블과 대조의 정보,
우리는 단지 하나의 새로운 노드를 필요로하는 곳에

142
00:07:25,620 --> 00:07:27,940
일부 키 값 쌍을 저장합니다.

143
00:07:27,940 --> 00:07:31,370
이제, 다시 이론, 큰 공간
소비가 큰 아닌 것 같아

144
00:07:31,370 --> 00:07:34,620
특히 주어진 처리하는 현대
컴퓨터는 기가 바이트를 가지고

145
00:07:34,620 --> 00:07:36,180
메모리의 기가 바이트.

146
00:07:36,180 --> 00:07:39,200
하지만 우리는 여전히이 밝혀
메모리 사용에 대한 걱정

147
00:07:39,200 --> 00:07:42,540
의 이익을 위해 조직
성능, 이후 현대 컴퓨터

148
00:07:42,540 --> 00:07:46,960
아래의 장소에있는 메커니즘이
메모리 액세스 속도를 높일 수 후드.

149
00:07:46,960 --> 00:07:51,180
>> 그러나 이러한 메커니즘은 가장 좋은 때 작동
메모리 액세스는 소형에서한다

150
00:07:51,180 --> 00:07:52,810
지역이나 지역.

151
00:07:52,810 --> 00:07:55,910
그리고 트라이의 노드가 상주 할 수
그 힙의 아무 곳.

152
00:07:55,910 --> 00:07:58,390
그러나 이러한 트레이드 오프입니다
우리는 고려해야합니다.

153
00:07:58,390 --> 00:08:01,440
>> 데이터를 선택할 때, 그 기억
특정 작업에 대한 구조, 우리

154
00:08:01,440 --> 00:08:04,420
에 대해 생각해야 어떤 종류의
작업 데이터 구조는 필요

155
00:08:04,420 --> 00:08:07,140
지원 얼마나 성능
이들 각각의

156
00:08:07,140 --> 00:08:09,080
우리에게 운영 문제.

157
00:08:09,080 --> 00:08:11,300
이러한 작업도 할 수있다
그냥 넘어 확장

158
00:08:11,300 --> 00:08:13,430
기본적인 모양의 위로 삽입.

159
00:08:13,430 --> 00:08:17,010
우리는 친절을 구현하고 싶어한다고 가정
자동 완성 기능의 많은

160
00:08:17,010 --> 00:08:18,890
같은 구글의 검색 엔진은 않습니다.

161
00:08:18,890 --> 00:08:22,210
즉, 모든 키를 반환
잠재적으로 가치있는

162
00:08:22,210 --> 00:08:24,130
특정 접두사가.

163
00:08:24,130 --> 00:08:27,050
>> 트라이 고유 유용
이 작업.

164
00:08:27,050 --> 00:08:29,890
그것은을 통해 반복하는 간단합니다
각 문자의 트라이

165
00:08:29,890 --> 00:08:30,950
접두사.

166
00:08:30,950 --> 00:08:33,559
다만, 조회 작업 등
우리는 포인터를 수행 할 수

167
00:08:33,559 --> 00:08:35,400
문자 단위.

168
00:08:35,400 --> 00:08:38,659
그 후, 우리는 말에 도착하면
접두사, 우리는을 반복 할 수

169
00:08:38,659 --> 00:08:42,049
데이터 구조의 나머지 부분
키 중 하나 이상 이후

170
00:08:42,049 --> 00:08:43,980
이 점은 접두사가.

171
00:08:43,980 --> 00:08:47,670
>> 그것은이 리스팅을 얻기도 쉽다
이후 알파벳 순서로

172
00:08:47,670 --> 00:08:50,970
어린이 배열의 요소
알파벳 순으로 정렬됩니다.

173
00:08:50,970 --> 00:08:54,420
그래서 희망을 고려해야합니다
기부는 시도를하려고합니다.

174
00:08:54,420 --> 00:08:56,085
나는 케빈 슈미트 해요, 이것은 CS50입니다.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> 아, 이것은 시작에 불과하다
감소.

177
00:09:00,790 --> 00:09:01,350
미안 해요.

178
00:09:01,350 --> 00:09:01,870
미안 해요.

179
00:09:01,870 --> 00:09:02,480
미안 해요.

180
00:09:02,480 --> 00:09:03,130
미안 해요.

181
00:09:03,130 --> 00:09:03,950
>> 네 스트라이크.

182
00:09:03,950 --> 00:09:04,360
나도 야.

183
00:09:04,360 --> 00:09:05,280
미안 해요.

184
00:09:05,280 --> 00:09:06,500
미안 해요.

185
00:09:06,500 --> 00:09:07,490
미안 해요.

186
00:09:07,490 --> 00:09:12,352
사람을 만들기위한 죄송합니다 사람
이 미쳐 편집 할 수 있습니다.

187
00:09:12,352 --> 00:09:13,280
>> 미안 해요.

188
00:09:13,280 --> 00:09:13,880
미안 해요.

189
00:09:13,880 --> 00:09:15,080
미안 해요.

190
00:09:15,080 --> 00:09:15,680
미안 해요.

191
00:09:15,680 --> 00:09:16,280
>> 스피커 1 : 잘 했어.

192
00:09:16,280 --> 00:09:17,530
그건 정말 잘 이루어졌다.

193
00:09:17,530 --> 00:09:18,430