1
00:00:00,000 --> 00:00:02,994
>> [음악 재생]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG 로이드 : 그래서 우리는 가까이 인칭했습니다
가까이 데이터의 성배

4
00:00:08,550 --> 00:00:13,050
우리가 삽입 할 수있는 구조, 하나
에,에서, 삭제 및 조회

5
00:00:13,050 --> 00:00:15,440
일정 시간에.

6
00:00:15,440 --> 00:00:16,270
권리.

7
00:00:16,270 --> 00:00:17,280
즉, 목표의 종류이다.

8
00:00:17,280 --> 00:00:19,720
우리는 할 수 있어야합니다
물건 아주, 아주 빠르게.

9
00:00:19,720 --> 00:00:22,580
>> 우리가 여기에 때를 발견
우리는 시도에 대해 얘기?

10
00:00:22,580 --> 00:00:23,670
음, 살펴 보자.

11
00:00:23,670 --> 00:00:25,628
그래서 우리는 몇 가지 봤어요
다른 데이터 구조

12
00:00:25,628 --> 00:00:28,680
즉, 매핑을 처리
키 - 값 쌍 소위,

13
00:00:28,680 --> 00:00:32,080
데이터의 일부 조각을 매핑
데이터의 다른 부분에

14
00:00:32,080 --> 00:00:36,020
그래서 우리는 어디에서 찾을 알고
구조 정보를 제공합니다.

15
00:00:36,020 --> 00:00:40,060
>> 따라서 배열, 예를 들면,
키 인덱스 또는 소자 배열

16
00:00:40,060 --> 00:00:42,600
위치 0 또는 배열 1 등.

17
00:00:42,600 --> 00:00:46,140
및 값은 데이터 인
즉, 해당 위치에 존재한다.

18
00:00:46,140 --> 00:00:48,550
그래서 배열 0에 무엇을 저장?

19
00:00:48,550 --> 00:00:54,290
무엇은 대 어레이 (1)에 저장된다
0과 1 키가 될 것이다.

20
00:00:54,290 --> 00:00:56,360
>> 해시 테이블로 그것은이다
같은 생각의 일종.

21
00:00:56,360 --> 00:01:00,690
해시 테이블, 우리는이 해시가
해시 코드를 생성하는 기능.

22
00:01:00,690 --> 00:01:03,670
그래서 키는 데이터의 해시 코드이다.

23
00:01:03,670 --> 00:01:06,530
및 값, 특히
우리는 체인에 대해 이야기

24
00:01:06,530 --> 00:01:10,590
해시 테이블에 대한 비디오,
데이터 링크 된 목록입니다

25
00:01:10,590 --> 00:01:12,550
즉, 그 해시 코드에 해시.

26
00:01:12,550 --> 00:01:14,050
권리.

27
00:01:14,050 --> 00:01:16,050
또 다른 방법은 어떻습니까
이 방법,하지만?

28
00:01:16,050 --> 00:01:21,000
방법에 대한 어떤 곳
키는 고유 보장

29
00:01:21,000 --> 00:01:25,410
해시 테이블, 우리가 할 수 달리
2 개의 데이터와 끝까지

30
00:01:25,410 --> 00:01:27,200
같은 해시 코드를 가진.

31
00:01:27,200 --> 00:01:30,020
그리고 우리가 처리해야
그 중 하나 프로빙 이상

32
00:01:30,020 --> 00:01:33,340
바람직하게는 그 문제를 해결하기 위해 체인.

33
00:01:33,340 --> 00:01:37,520
>> 그래서 지금 우리가 보장 할 수
우리의 키는 고유합니다.

34
00:01:37,520 --> 00:01:39,690
그리고 우리의 가치는 무엇 인 경우
쉬운처럼 뭔가

35
00:01:39,690 --> 00:01:44,080
여부를 우리에게 그와 같은 사실과 거짓
정보의 여부를 그 조각

36
00:01:44,080 --> 00:01:45,610
구조에 존재?

37
00:01:45,610 --> 00:01:48,180
부울 조금처럼 간단 할 수있다.

38
00:01:48,180 --> 00:01:52,660
현실적으로는 아마
조금 더 가능성 바이트.

39
00:01:52,660 --> 00:01:55,410
하지만 그보다 훨씬 작다
50 문자열 어쩌면 저장,

40
00:01:55,410 --> 00:01:57,360
예를 들면.

41
00:01:57,360 --> 00:02:02,210
>> 시도 따라서, 해시 테이블과 유사하게,
이는 결합 배열과 연결리스트,

42
00:02:02,210 --> 00:02:05,790
시도 배열을 결합,
구조 및 포인터

43
00:02:05,790 --> 00:02:08,509
서로에 데이터를 저장하도록
의 흥미로운 방법

44
00:02:08,509 --> 00:02:11,550
에서 꽤 다른
우리가 지금까지 본 적이 아무것도.

45
00:02:11,550 --> 00:02:16,750
이제 로드맵 데이터를 사용
이 데이터 구조를 탐색 할 수 있습니다.

46
00:02:16,750 --> 00:02:18,710
그리고 우리는 따라 할 수있는 경우
로드맵, 우리가 할 수있는 경우

47
00:02:18,710 --> 00:02:22,390
로부터 데이터를 따르
끝으로 시작, 우리는거야

48
00:02:22,390 --> 00:02:24,945
데이터 여부를 알
트라이에 존재합니다.

49
00:02:24,945 --> 00:02:28,310
>> 그리고 우리는지도를 수행 할 수없는 경우
전혀 종료 의미에서,

50
00:02:28,310 --> 00:02:30,600
데이터가 존재할 수 없습니다.

51
00:02:30,600 --> 00:02:32,890
또, 키는 여기에 있습니다
고유합니다.

52
00:02:32,890 --> 00:02:36,020
그래서 해시 테이블과는 달리, 우리는거야
여기에 충돌을 처리해야합니다.

53
00:02:36,020 --> 00:02:39,090
그리고 데이터의 두 개의 조각 없음
똑같은 로드맵을 가지고

54
00:02:39,090 --> 00:02:40,530
하지 않는 데이터는 동일하다.

55
00:02:40,530 --> 00:02:44,580
>> 우리는 존을, 다음 삽입하는 경우
우리는 존을 검색합니다.

56
00:02:44,580 --> 00:02:47,430
즉, 두 개의 동일한 조각의
데이터, 오른쪽, 우리는을 통해 찾고 있습니다.

57
00:02:47,430 --> 00:02:49,880
그러나 그렇지 않은 경우, 어떤
데이터의 두 가지가 있습니다

58
00:02:49,880 --> 00:02:52,750
독특한 로드맵을 보장
이 데이터 구조를 통해.

59
00:02:52,750 --> 00:02:56,210
그리고 우리는 살펴거야
잠시이 시각적.

60
00:02:56,210 --> 00:02:58,810
>> 우리는에 노력하여이 작업을 수행 할 수 있습니다
새로운 데이터 구조를 생성,

61
00:02:58,810 --> 00:03:00,564
다음 키 값 쌍을 매핑.

62
00:03:00,564 --> 00:03:03,480
이 경우, 우리는 사용하지 않을거야
부울 같은 간단한.

63
00:03:03,480 --> 00:03:06,200
우리는 실제로 문자열을 저장합니다.

64
00:03:06,200 --> 00:03:08,690
그리고 그 문자열을 것입니다
대학의 이름.

65
00:03:08,690 --> 00:03:12,140
>> 그리고 키는 한 해가 될 것입니다
그 대학이 설립되었을 때.

66
00:03:12,140 --> 00:03:15,380
대학에 대한 모든 년
네 자리가 될 것입니다.

67
00:03:15,380 --> 00:03:19,840
그래서 우리는에 그 4 자리 숫자를 사용합니다
이 데이터 구조를 통해 이동합니다.

68
00:03:19,840 --> 00:03:22,270
그리고 우리는 다시 볼 수 있습니다, 방법
우리는 단지 두 번째에 그렇게.

69
00:03:22,270 --> 00:03:25,110
>> 경로의 끝에서,
우리는 이름을 볼 수 있습니다

70
00:03:25,110 --> 00:03:30,250
해당 대학의
그 키에, 그 4 자리 숫자.

71
00:03:30,250 --> 00:03:34,390
트라이의 기본 개념
우리는 중앙 경로가 있습니다.

72
00:03:34,390 --> 00:03:35,640
그래서 나무처럼 그것에 대해 생각합니다.

73
00:03:35,640 --> 00:03:39,211
그리고 이것은 철자 유사
그리고 나무에 개념.

74
00:03:39,211 --> 00:03:41,460
일반적으로 우리가 생각하면
현실 세계에서 나무,

75
00:03:41,460 --> 00:03:44,090
그들은에서의 루트를
지상 그들은 위쪽으로 성장

76
00:03:44,090 --> 00:03:46,830
그들은 지점을 가지고
그들은 잎을 가지고있다.

77
00:03:46,830 --> 00:03:49,450
그리고 기본적으로 아이디어
트라이는 똑같

78
00:03:49,450 --> 00:03:51,755
그 루트는 고정되어 제외
하늘에서 어딘가에.

79
00:03:51,755 --> 00:03:53,130
그리고 잎은 아래에 있습니다.

80
00:03:53,130 --> 00:03:55,750
>> 그래서 나무를 복용 같은 종류의
그냥 거꾸로 뒤집기.

81
00:03:55,750 --> 00:03:56,880
하지만 여전히 가지가 있습니다.

82
00:03:56,880 --> 00:03:59,463
그리고 그는 우리의 경로가 될 것이다,
사람들은 우리의 연결됩니다

83
00:03:59,463 --> 00:04:02,220
잎에 루트에서.

84
00:04:02,220 --> 00:04:04,200
이 경우, 그
경로, 그 지점

85
00:04:04,200 --> 00:04:08,490
우리에게 숫자로 표시되어 있습니다
어떤 방법으로 우리가 어디에서 이동합니다.

86
00:04:08,490 --> 00:04:11,800
>> 우리는 0을 참조하면, 우리는이 지점 아래로 이동
우리가 1을 참조하면, 우리는이 지점 아래로 이동

87
00:04:11,800 --> 00:04:12,900
등 등.

88
00:04:12,900 --> 00:04:14,060
음, 이것은 무엇을 의미합니까?

89
00:04:14,060 --> 00:04:16,519
글쎄, 그건 것을 의미한다
모든 연결 지점에서

90
00:04:16,519 --> 00:04:19,260
그리고 모든 노드
중간 모든 지점,

91
00:04:19,260 --> 00:04:23,020
수 (10)이있다
우리가 갈 수있는 곳.

92
00:04:23,020 --> 00:04:27,690
그래서 10 포인터가있다
모든 위치에서.

93
00:04:27,690 --> 00:04:30,610
>> 시도가 얻을 수있는 곳이있다
누군가 협박 조금

94
00:04:30,610 --> 00:04:34,460
누가 것은 많이 없습니다
전에 컴퓨터 과학의 경험.

95
00:04:34,460 --> 00:04:35,960
하지만 시도는 정말 꽤 굉장하다.

96
00:04:35,960 --> 00:04:37,793
그리고 당신이있는 경우
그들과 함께 작업 할 기회

97
00:04:37,793 --> 00:04:40,420
당신은 파고-에 기꺼이
그들과 함께 실험,

98
00:04:40,420 --> 00:04:44,234
그들은 정말 아주 흥미있어
데이터 구조와 함께 작동합니다.

99
00:04:44,234 --> 00:04:46,900
우리는 요소를 삽입 할 경우
트라이에, 모든 우리가해야 할

100
00:04:46,900 --> 00:04:51,360
올바른 경로를 구축한다
잎에 루트에서.

101
00:04:51,360 --> 00:04:55,390
여기에 무엇을 모든 단계를 따라입니다
방법은 다음과 같을 수 있습니다.

102
00:04:55,390 --> 00:04:59,660
우리는 새로운 데이터를 정의하는거야
새로운 노드의 구조는 트라이를했다.

103
00:04:59,660 --> 00:05:02,560
>> 그리고 그 데이터의 내부
구조 두 가지가있다.

104
00:05:02,560 --> 00:05:05,460
우리는을 저장하는거야
대학의 이름입니다.

105
00:05:05,460 --> 00:05:09,410
그리고 우리는 저장거야
포인터 배열

106
00:05:09,410 --> 00:05:12,190
동일한 유형의 다른 노드.

107
00:05:12,190 --> 00:05:14,780
그래서, 다시, 이것은 그런 종류입니다
사방의 개념

108
00:05:14,780 --> 00:05:18,567
우리는 10 수에이다
우리가 갈 수있는 곳.

109
00:05:18,567 --> 00:05:20,150
우리는 0을 참조하면, 우리는이 지점을 아래로 이동합니다.

110
00:05:20,150 --> 00:05:22,690
우리가 1을 참조하면,이 지점,
등 등 등.

111
00:05:22,690 --> 00:05:25,160
우리가 9를 말한다면, 우리는이 지점을 아래로 이동합니다.

112
00:05:25,160 --> 00:05:28,220
모든 연결 지점에 따라서
우리는 10 가능한 장소를 갈 수 있습니다.

113
00:05:28,220 --> 00:05:35,740
그래서 각 노드가 포인터 (10)를 포함한다
(10) 다른 노드에 다른 노드에.

114
00:05:35,740 --> 00:05:39,810
>> 그리고 우리가 저장하고있는 데이터는
대학의 이름 만.

115
00:05:39,810 --> 00:05:41,060
그럼 트라이를 구축 할 수 있습니다.

116
00:05:41,060 --> 00:05:44,860
이제 몇 가지를 삽입하자
우리의 트라이에 항목.

117
00:05:44,860 --> 00:05:46,740
, 맨 위에 그래서
이것은 우리의 루트 노드입니다.

118
00:05:46,740 --> 00:05:49,740
이것은 아마도 뭔가 될 것입니다
당신은 선언을 전역 것입니다.

119
00:05:49,740 --> 00:05:53,450
그리고 당신은 유지 전역거야
항상이 노드에 대한 포인터.

120
00:05:53,450 --> 00:05:55,360
>> 당신은 말할거야
뿌리는 동일, 당신은있어

121
00:05:55,360 --> 00:05:57,580
자신에게 트라이 노드를 MALLOC 것.

122
00:05:57,580 --> 00:05:59,850
그리고 당신은 결코 않을거야
다시 뿌리를 터치합니다.

123
00:05:59,850 --> 00:06:02,300
당신이 원하는 때마다
를 탐색 시작

124
00:06:02,300 --> 00:06:05,802
다른 포인터를 설정
같은 TRAV으로, 루트와 동일,

125
00:06:05,802 --> 00:06:07,760
이는 예 I이고
내 동영상의 많은에 사용

126
00:06:07,760 --> 00:06:11,090
여기에 스택과 큐에
링크 목록 등등.

127
00:06:11,090 --> 00:06:13,320
>> 당신은 다른 포인터를 설정
순회 TRAV했다.

128
00:06:13,320 --> 00:06:15,890
그리고 당신은 이동 TRAV를 사용
데이터 구조 내지.

129
00:06:15,890 --> 00:06:17,500
그럼이 볼 수있는 방법을 살펴 보자.

130
00:06:17,500 --> 00:06:19,880
그래서 지금, 무엇을
노드가 생겼는데?

131
00:06:19,880 --> 00:06:22,920
글쎄, 우리의 데이터로
구조의 선언은, 표시

132
00:06:22,920 --> 00:06:26,906
우리는 문자열을 가지고있는
이 경우에는 비어 있습니다.

133
00:06:26,906 --> 00:06:27,780
여기에 아무것도 없습니다.

134
00:06:27,780 --> 00:06:29,550
>> 10 포인터의 배열.

135
00:06:29,550 --> 00:06:31,790
그리고 지금, 우리 만
이 트라이 1 노드를 가지고있다.

136
00:06:31,790 --> 00:06:33,110
거기에 다른 아무것도 없습니다.

137
00:06:33,110 --> 00:06:36,020
그래서 그 모든 10
포인트 포인터를 null로.

138
00:06:36,020 --> 00:06:38,090
즉, 빨간색이 표시거야.

139
00:06:38,090 --> 00:06:39,500
>> 의 문자열 하버드를 삽입 할 수 있습니다.

140
00:06:39,500 --> 00:06:41,999
이제 대학 삽입하자
이 트라이에 하버드, 어떤

141
00:06:41,999 --> 00:06:43,940
올해 1636 년에 설립되었다.

142
00:06:43,940 --> 00:06:48,220
우리는 키를 사용하려면,
1636, 우리가있어 어디 우리에게 얘기를

143
00:06:48,220 --> 00:06:50,140
트라이에 하버드를 저장하는 것.

144
00:06:50,140 --> 00:06:51,470
이제, 우리는 어떻게 할 수 있는가?

145
00:06:51,470 --> 00:06:52,886
>> 그것은 다음과 같을 수 있습니다.

146
00:06:52,886 --> 00:06:54,160
우리는 루트에서 시작합니다.

147
00:06:54,160 --> 00:06:56,920
그리고 우리는 우리가 갈 수있는이 10 곳이있다.

148
00:06:56,920 --> 00:06:59,900
루트는 그냥 같다
트라이의 다른 노드입니다.

149
00:06:59,900 --> 00:07:02,850
우리가 여기에서 갈 수있는 10 곳이있다.

150
00:07:02,850 --> 00:07:07,215
>> 어디 우리가 아마 싶어
키가 1636 인 경우 이동?

151
00:07:07,215 --> 00:07:08,340
정말 두 가지 옵션이있다.

152
00:07:08,340 --> 00:07:08,450
권리.

153
00:07:08,450 --> 00:07:10,825
우리는에서 키를 구축 할 수 있습니다
오른쪽에서 왼쪽으로, 6으로 시작합니다.

154
00:07:10,825 --> 00:07:14,000
아니면 우리는에서 키를 만들 수
왼쪽에서 오른쪽으로 1부터 시작.

155
00:07:14,000 --> 00:07:16,140
>> 아마 더
인간 직관적

156
00:07:16,140 --> 00:07:18,110
우리에게 있습니다 이해하기
그냥 왼쪽에서 오른쪽으로 이동합니다.

157
00:07:18,110 --> 00:07:21,140
그래서 내가 삽입 할 경우
이 트라이에 하버드,

158
00:07:21,140 --> 00:07:23,560
아마 시작하려면
루트에서 시작하여,

159
00:07:23,560 --> 00:07:25,720
제 10 옵션을보고
내 앞에, 그리고 말

160
00:07:25,720 --> 00:07:28,700
나는 1 길을 가고 싶어.

161
00:07:28,700 --> 00:07:29,700
그래.

162
00:07:29,700 --> 00:07:31,810
>> 이제 1 경로는 현재 null입니다.

163
00:07:31,810 --> 00:07:35,920
그래서 나는 그 길을 계속 진행하려면
트라이에이 요소를 삽입하려면,

164
00:07:35,920 --> 00:07:42,040
나는 1가, 새 노드를 MALLOC해야
이 지적하고 나는 갈 수 있어요.

165
00:07:42,040 --> 00:07:46,460
>> 그래서 나는 기본적으로 오전
포인트 어디 서있어

166
00:07:46,460 --> 00:07:50,270
또는 트리의 루트
트라이 10 가지가있다.

167
00:07:50,270 --> 00:07:52,260
그러나 각 지점이있다
그것의 앞에 문입니다.

168
00:07:52,260 --> 00:07:53,060
권리.

169
00:07:53,060 --> 00:07:54,850
아무것도 없기 때문에 다른 사람이있다.

170
00:07:54,850 --> 00:07:56,522
안전한 통로 없습니다.

171
00:07:56,522 --> 00:07:58,980
즉 아무 것도 없다는 것을 의미합니다
그 지점의 아래.

172
00:07:58,980 --> 00:08:02,532
나는 건물을 시작하려면
뭔가, 나는 문을 제거 할.

173
00:08:02,532 --> 00:08:04,490
나는 문을 제거 할
숫자 1의 앞.

174
00:08:04,490 --> 00:08:05,698
그리고 나는 그것을 걸어 싶습니다.

175
00:08:05,698 --> 00:08:08,060
그리고 구축하려는
나를 위해 다른 곳으로 이동합니다.

176
00:08:08,060 --> 00:08:09,470
>> 그리고 그게 내가 여기에 무슨 짓을했는지입니다.

177
00:08:09,470 --> 00:08:11,430
그래서 1은 더 이상 null로 지적 없습니다.

178
00:08:11,430 --> 00:08:13,830
나는 지금 여기에 가서하는 것이 안전 말했다했습니다.

179
00:08:13,830 --> 00:08:15,789
나는 다른 노드를 구축했다.

180
00:08:15,789 --> 00:08:18,330
그리고 해당 노드에 도착하면, 나는
만드는 또 다른 결정을해야합니다.

181
00:08:18,330 --> 00:08:20,890
어디 여기에서 갈 거지?

182
00:08:20,890 --> 00:08:22,700
>> 글쎄, 난 이미 1 내려 갔어요.

183
00:08:22,700 --> 00:08:24,470
그래서 지금은 아마 6을 가고 싶어.

184
00:08:24,470 --> 00:08:24,970
권리.

185
00:08:24,970 --> 00:08:27,100
다시 말하지만, 내가 선택할 수있는 위치가 10 개.

186
00:08:27,100 --> 00:08:30,060
그래서 지금은 숫자 6을 가자.

187
00:08:30,060 --> 00:08:32,280
그래서 문을 취소
번호 6의 앞.

188
00:08:32,280 --> 00:08:33,250
그리고 나는 거기 걸어.

189
00:08:33,250 --> 00:08:34,580
그리고 나는 또 다른 노드를 구축 할 수 있습니다.

190
00:08:34,580 --> 00:08:37,630
그리고 나는 또 다른 연결 지점에 도달했습니다.

191
00:08:37,630 --> 00:08:40,289
>> 다시 말하지만, 나는 10를 선택할 수 있습니다
내가 갈 수있는 곳합니다.

192
00:08:40,289 --> 00:08:42,799
나는 1-6 이동했습니다.

193
00:08:42,799 --> 00:08:44,215
그래서 지금은 아마 3에 가고 싶다.

194
00:08:44,215 --> 00:08:45,381
3, 아무 곳에 나 갈 수 없다.

195
00:08:45,381 --> 00:08:48,980
그래서 방법을 취소해야
자신에게 새로운 공간을 구축 할 수 있습니다.

196
00:08:48,980 --> 00:08:50,870
그리고 내가 가고 싶어 3에서?

197
00:08:50,870 --> 00:08:52,450
나는 아래로 6 가고 싶어.

198
00:08:52,450 --> 00:08:54,770
>> 그리고, 다시, 나는에 있었다
그것을 할 수있는 방법을 취소합니다.

199
00:08:54,770 --> 00:08:59,179
그래서 지금 만들고 삽입 내 키를 사용했습니다
노드는이 트라이를 구축하기 시작합니다.

200
00:08:59,179 --> 00:09:00,220
나는 루트에서 시작했습니다.

201
00:09:00,220 --> 00:09:03,666
나는 1636 아래로 갔어요.

202
00:09:03,666 --> 00:09:05,540
그리고 지금은 맨 아래에 있어요
이 노드에.

203
00:09:05,540 --> 00:09:06,610
그리고 당신은 할 수 있습니다
화면에 볼.

204
00:09:06,610 --> 00:09:07,735
>> 그것은 노란색으로 강조합니다.

205
00:09:07,735 --> 00:09:10,020
나는 현재 나는 곳이다.

206
00:09:10,020 --> 00:09:11,300
내 키가 이루어집니다.

207
00:09:11,300 --> 00:09:13,030
내 키의 모든 위치를 소진했다.

208
00:09:13,030 --> 00:09:15,040
그래서 나는 더 이상 갈 수 없습니다.

209
00:09:15,040 --> 00:09:17,720
이 시점에서, 모든 I 그래서
정말 좋아, 말을하기 만하면됩니다.

210
00:09:17,720 --> 00:09:18,990
그것은 종류의보고처럼
지상에서 아래로,

211
00:09:18,990 --> 00:09:21,115
당신이 상상하는 경우
직접 경로의 종류 등

212
00:09:21,115 --> 00:09:22,350
다른 연결이.

213
00:09:22,350 --> 00:09:25,800
정렬의 아래 종류의보고
지상에 하버드 페인팅 스프레이.

214
00:09:25,800 --> 00:09:26,800
즉,이의 이름입니다.

215
00:09:26,800 --> 00:09:28,300
즉,이 위치에서 무엇을 알고있다.

216
00:09:28,300 --> 00:09:31,870
우리는 루트에서 시작하여 우리는 내려 가지 경우
1 다음 6 다음 3 다음 6,

217
00:09:31,870 --> 00:09:32,780
우리를 어디?

218
00:09:32,780 --> 00:09:35,640
그런데 우리는 아래를 보면
우리는 하버드 참조

219
00:09:35,640 --> 00:09:38,960
우리는 하버드는 것을 알고있다
방식에 따라 1636 년에 설립

220
00:09:38,960 --> 00:09:41,400
우리는이 데이터 구조를 구현하고있다.

221
00:09:41,400 --> 00:09:43,177
그래서 희망 간단했다.

222
00:09:43,177 --> 00:09:44,760
우리는 두 개 더 삽입을 할 것입니다.

223
00:09:44,760 --> 00:09:50,060
그리고 희망이에 도움이됩니다
볼이 두 번 더 수행.

224
00:09:50,060 --> 00:09:52,210
>> 이제, 다른 대학을 삽입 할 수 있습니다.

225
00:09:52,210 --> 00:09:54,630
의이 트라이에 예일대를 삽입 할 수 있습니다.

226
00:09:54,630 --> 00:09:57,037
예일대는 1701 년에 설립되었다.

227
00:09:57,037 --> 00:09:58,870
그래서 우리는에서 시작합니다
루트, 우리가 항상있다.

228
00:09:58,870 --> 00:09:59,890
그리고 우리는 순회 포인터를 설정합니다.

229
00:09:59,890 --> 00:10:01,624
우리는을 통해 이동하는 것을 사용하는 것입니다.

230
00:10:01,624 --> 00:10:03,790
우리가 할 첫 번째 일이
수행은 1 길을 갈 것입니다.

231
00:10:03,790 --> 00:10:05,830
즉 우리의 키의 첫 번째 숫자입니다.

232
00:10:05,830 --> 00:10:08,420
다행히도, 그러나, 우리는하지 않습니다
모든 작업이 시간을해야한다.

233
00:10:08,420 --> 00:10:09,919
1 경로는 이미 지워졌습니다.

234
00:10:09,919 --> 00:10:13,520
나는 이전에 때를 지워
1636에서 하버드를 삽입했다.

235
00:10:13,520 --> 00:10:18,090
그래서 안전하게 이동할 수 있습니다
1 아래로 그냥 이동합니다.

236
00:10:18,090 --> 00:10:20,150
(1)를 아래로 이동 할 수있는 경우에.

237
00:10:20,150 --> 00:10:22,930
>> 하지만 이제 나는 7에 가고 싶다.

238
00:10:22,930 --> 00:10:24,280
나는 6시에 길을 지워.

239
00:10:24,280 --> 00:10:27,050
나는 안전하게 할 수있는 알고
6 경로를 아래로 이동합니다.

240
00:10:27,050 --> 00:10:29,220
하지만 7 경로에 진행해야합니다.

241
00:10:29,220 --> 00:10:30,580
그래서 내가 어떻게해야합니까?

242
00:10:30,580 --> 00:10:35,070
음, 그냥 예전처럼, 난 그냥 필요
게이트를 취소, 비켜,

243
00:10:35,070 --> 00:10:38,740
그리고 7 경로에서 새 노드를 구축 할 수 있습니다.

244
00:10:38,740 --> 00:10:40,250
그냥이있다.

245
00:10:40,250 --> 00:10:42,930
>> 그래서 지금은 1 다음 7을 이동했습니다.

246
00:10:42,930 --> 00:10:45,550
그리고 지금, 알 내가 종류 해요
이 새로운 subbranch에.

247
00:10:45,550 --> 00:10:46,050
권리.

248
00:10:46,050 --> 00:10:49,260
(16)에서 다른 모든
에, 나는 걱정하지 않는다.

249
00:10:49,260 --> 00:10:50,720
나는 16 아무것도 아니에요.

250
00:10:50,720 --> 00:10:51,750
나는 17 물건을하고 있어요.

251
00:10:51,750 --> 00:10:58,380
>> 그래서 지금 17에서에, 나는에있다
일종의 여기에 새로운 산책로 불꽃.

252
00:10:58,380 --> 00:11:00,462
다음 숫자는 내 키는 0입니다.

253
00:11:00,462 --> 00:11:01,670
나는 분명히 어디서든 얻을 수 없습니다.

254
00:11:01,670 --> 00:11:02,628
난 그냥이 노드를 구축했다.

255
00:11:02,628 --> 00:11:04,550
그래서 나는 더있다 알지
앞으로 여기에서 경로.

256
00:11:04,550 --> 00:11:06,370
그래서 하나에게 자신을 확인해야합니다.

257
00:11:06,370 --> 00:11:09,360
>> 그래서 나는 새 노드를 MALLOC
거기에 0 점을 가지고있다.

258
00:11:09,360 --> 00:11:12,770
그리고 한 번 더, 나는 malloc에
새로운 노드가 하나의 점을 가지고있다.

259
00:11:12,770 --> 00:11:15,870
다시 말하지만, 난 내 키, 1701 소진했습니다.

260
00:11:15,870 --> 00:11:18,472
그래서 아래로보고 나는 예일 페인트 스프레이.

261
00:11:18,472 --> 00:11:19,680
즉,이 노드의 이름입니다.

262
00:11:19,680 --> 00:11:24,660
>> 그리고 지금은 그 어느 예일 있는지 확인해야하는 경우
이 트라이에, 나는 루트에서 시작되어,

263
00:11:24,660 --> 00:11:27,060
나는 1701 아래로 이동, 아래로 본다.

264
00:11:27,060 --> 00:11:30,030
그리고 예일 스프레이를 참조하는 경우
다음, 바닥에 그려진

265
00:11:30,030 --> 00:11:32,200
나는 예일이 트라이에 존재하는 것을 알고있다.

266
00:11:32,200 --> 00:11:32,950
이제 한 번 더 해 보자.

267
00:11:32,950 --> 00:11:36,430
의이에 다트머스를 삽입하자
1769 년에 설립 된 트라이.

268
00:11:36,430 --> 00:11:37,750
>> 다시 루트에서 시작합니다.

269
00:11:37,750 --> 00:11:39,445
내 키의 내 첫 번째 숫자는 1입니다.

270
00:11:39,445 --> 00:11:40,820
내가 안전하게 그 길을 이동할 수 있습니다.

271
00:11:40,820 --> 00:11:42,400
즉 이미 존재합니다.

272
00:11:42,400 --> 00:11:44,040
내 키의 다음 숫자는 7이다.

273
00:11:44,040 --> 00:11:45,890
내가 안전하게 그 길을 이동할 수 있습니다.

274
00:11:45,890 --> 00:11:47,540
그것은뿐만 아니라 존재한다.

275
00:11:47,540 --> 00:11:49,000
>> 나의 다음은 6입니다.

276
00:11:49,000 --> 00:11:52,860
여기에서, 나는 현재 나는 곳에서
그 중간 노드가 노란색,

277
00:11:52,860 --> 00:11:56,060
(6)는 현재 오프 잠겨 있습니다.

278
00:11:56,060 --> 00:11:58,830
내가 그 길을 가고 싶은 경우,
내가 직접 구축 할 수 있습니다.

279
00:11:58,830 --> 00:12:02,250
그래서 나는 새 노드를 malloc에​​ 있습니다
거기에 6 점을 가지고있다.

280
00:12:02,250 --> 00:12:04,250
그리고, 다시, 나는 해요
여기에 새로운 산책로 타오르는.

281
00:12:04,250 --> 00:12:10,750
>> 그래서 나는 새 노드를 MALLOC에서되도록
지금 그 node-- 경로 번호 9--과

282
00:12:10,750 --> 00:12:13,584
나는 1769 여행, 나는 아래를 보면.

283
00:12:13,584 --> 00:12:15,500
아무것도 현재 없습니다
이 페인트 스프레이.

284
00:12:15,500 --> 00:12:16,930
나는 다트머스을 작성할 수 있습니다.

285
00:12:16,930 --> 00:12:20,710
그리고 삽입 한
트라이에 다트머스.

286
00:12:20,710 --> 00:12:23,450
>> 그래서 삽입의
트라이에 일.

287
00:12:23,450 --> 00:12:25,384
이제 우리는 물건을 검색 할 수 있습니다.

288
00:12:25,384 --> 00:12:27,050
우리는 어떻게 트라이에 물건을 검색 할 수 있습니까?

289
00:12:27,050 --> 00:12:29,170
음, 거의 같은 생각입니다.

290
00:12:29,170 --> 00:12:33,620
이제 우리는 단지 키의 숫자를 사용
우리는 루트에서 탐색 할 수 있는지 확인하기 위해

291
00:12:33,620 --> 00:12:37,170
우리는 트라이에 가고 싶은 곳으로.

292
00:12:37,170 --> 00:12:41,620
>> 우리는, 어떤 시점에서 막 다른 골목에 충돌하는 경우
우리는 그 요소가 존재할 수 있음을 알

293
00:12:41,620 --> 00:12:44,500
그렇지 않으면 그 경로는 것
이미 삭제되었다.

294
00:12:44,500 --> 00:12:45,930
우리는 모든 방식을 한 경우
결국, 모든 우리가해야 할

295
00:12:45,930 --> 00:12:48,471
아래로보고 그건 있는지입니다
우리가 찾고있는 요소입니다.

296
00:12:48,471 --> 00:12:49,335
그것은 성공 인 경우.

297
00:12:49,335 --> 00:12:52,610
그렇지 않은 경우, 실패합니다.

298
00:12:52,610 --> 00:12:54,940
>> 그럼 검색하자
이 트라이 하버드.

299
00:12:54,940 --> 00:12:56,020
우리는 루트에서 시작합니다.

300
00:12:56,020 --> 00:12:58,228
그리고 다시, 우리는거야
탐색 포인터를 만들

301
00:12:58,228 --> 00:12:59,390
우리를 위해 우리의 이동을합니다.

302
00:12:59,390 --> 00:13:02,080
루트에서 우리는 알고
우리가 갈 필요가 첫 번째 장소는, 1

303
00:13:02,080 --> 00:13:03,390
우리는 그렇게 할 수 있습니까?

304
00:13:03,390 --> 00:13:03,982
그래 우리는 할 수있어.

305
00:13:03,982 --> 00:13:04,690
경우 안전하게 존재한다.

306
00:13:04,690 --> 00:13:06,660
우리는 거기에 갈 수 있습니다.

307
00:13:06,660 --> 00:13:08,440
>> 이제, 우리가 갈 필요가 다음 장소는 6입니다.

308
00:13:08,440 --> 00:13:10,557
6 경로는 여기에서 존재 하는가?

309
00:13:10,557 --> 00:13:11,140
네, 그렇습니다.

310
00:13:11,140 --> 00:13:12,690
우리는 6 길을 갈 수 있습니다.

311
00:13:12,690 --> 00:13:13,905
그리고 우리는 여기서 끝.

312
00:13:13,905 --> 00:13:16,130
>> 우리는 여기에서 3 길로 갈 수 있습니까?

313
00:13:16,130 --> 00:13:18,450
글쎄, 그것은 밝혀,
네, 역시 존재한다.

314
00:13:18,450 --> 00:13:20,790
그리고 우리는 여기에서 6 경로에받을 수 있나요?

315
00:13:20,790 --> 00:13:21,982
그래 우리는 할 수있어.

316
00:13:21,982 --> 00:13:24,002
>> 우리는 아주 대답하지 않은
아직 질문입니다.

317
00:13:24,002 --> 00:13:25,710
하나는 여전히있다
지금 단계,

318
00:13:25,710 --> 00:13:28,520
우리가 아래로 볼 필요가와
그 ... 사실상의 경우 참조

319
00:13:28,520 --> 00:13:32,660
우리가 하버드를 찾고 있다면,이다
우리가 키를 배출 한 후 우리는 무엇을 찾아?

320
00:13:32,660 --> 00:13:35,430
이 예에서 우리가 여기에서 사용하고,
년은 항상 네 자리 숫자입니다.

321
00:13:35,430 --> 00:13:40,280
하지만 당신은 예를 어디에 사용 될 수 있습니다
당신은 단어의 사전을 저장한다.

322
00:13:40,280 --> 00:13:44,060
>> 그래서 대신에 10 포인터를 갖는
내 위치, 당신은 26가있을 수 있습니다.

323
00:13:44,060 --> 00:13:46,040
알파벳의 각 문자 하나.

324
00:13:46,040 --> 00:13:50,350
그리고 박쥐와 같은 일부 단어가있다,
이는 예를 들어 배치의 부분 집합이다.

325
00:13:50,350 --> 00:13:53,511
그리고 당신은 얻을 그래서 경우에도
키의 끝 당신은 아래로보고,

326
00:13:53,511 --> 00:13:55,260
당신은 무엇을 볼 수 있습니다
당신이 찾고 있습니다.

327
00:13:55,260 --> 00:13:58,500
>> 그래서 당신은 항상 통과해야
전체 경로 다음

328
00:13:58,500 --> 00:14:01,540
당신은 성공적으로 수 있다면
전체 경로를 통과합니다,

329
00:14:01,540 --> 00:14:03,440
아래로보고 한 최종 확인을한다.

330
00:14:03,440 --> 00:14:05,120
그게 내가 바라는 건 무엇인가?

331
00:14:05,120 --> 00:14:07,740
글쎄, 난 시작한 후 아래로 보이는
상단과 1636을 것.

332
00:14:07,740 --> 00:14:08,240
나는 아래로 본다.

333
00:14:08,240 --> 00:14:09,400
나는 하버드를 참조하십시오.

334
00:14:09,400 --> 00:14:11,689
그래서, 그래, 나는 성공했다.

335
00:14:11,689 --> 00:14:13,980
어떤 경우에는 내가 무엇을 찾고 있어요
하지만, 트라이에 있지 않습니다.

336
00:14:13,980 --> 00:14:17,200
내가 프린스턴 무엇을 찾고 있어요 경우,
이는 1746 년에 설립되었다.

337
00:14:17,200 --> 00:14:20,875
그리고 1746 내 키가된다
트라이을 탐색합니다.

338
00:14:20,875 --> 00:14:22,040
글쎄, 난 루트에서 시작합니다.

339
00:14:22,040 --> 00:14:24,760
그리고 내가 원하는 첫 번째 장소
에는 1 길을 간다.

340
00:14:24,760 --> 00:14:25,590
나는 그것을 할 수 있습니까?

341
00:14:25,590 --> 00:14:26,490
예, 저는 할수 있습니다.

342
00:14:26,490 --> 00:14:28,730
>> 나는 거기에서 7 경로 아래로 갈 수 있습니까?

343
00:14:28,730 --> 00:14:29,230
네, 할 수 있습니다.

344
00:14:29,230 --> 00:14:30,750
즉,도 존재한다.

345
00:14:30,750 --> 00:14:32,460
그러나 여기에서 4 경로 아래로 갈 수 있나요?

346
00:14:32,460 --> 00:14:35,550
즉, 수, 질문처럼
나는 작은 광장 것을 아래 진행

347
00:14:35,550 --> 00:14:37,114
것을 나는 노란색으로 강조했습니다?

348
00:14:37,114 --> 00:14:38,030
거기에 아무것도 없습니다.

349
00:14:38,030 --> 00:14:38,610
권리.

350
00:14:38,610 --> 00:14:41,310
>> 방법 앞으로 4 경로 아래 없습니다.

351
00:14:41,310 --> 00:14:46,480
프린스턴,이 트라이에 있었다 (4) 그 경우
이미 우리를 위해 삭제되었을 것입니다.

352
00:14:46,480 --> 00:14:49,130
그리고이 시점에서
우리는 막 다른 골목에 도달했습니다.

353
00:14:49,130 --> 00:14:50,250
우리는 더 이상 갈 수 없습니다.

354
00:14:50,250 --> 00:14:53,440
그래서 우리는 아니, 확실히 말할 수 있습니다.

355
00:14:53,440 --> 00:14:56,760
프린스턴이 트라이에 존재하지 않습니다.

356
00:14:56,760 --> 00:14:58,860
>> 그래서이 모든 무엇을 의미 하는가?

357
00:14:58,860 --> 00:14:59,360
권리.

358
00:14:59,360 --> 00:15:01,000
여기서 살펴 봐야 할 것들이 많다.

359
00:15:01,000 --> 00:15:02,500
도처에 포인터가있다.

360
00:15:02,500 --> 00:15:04,249
그리고, 같이 당신은 볼 수 있습니다
다만, 다이어그램에서

361
00:15:04,249 --> 00:15:07,010
노드가 많이있다 그
종류의 주위를 날고있다.

362
00:15:07,010 --> 00:15:13,480
그러나 우리가 원하는 모든 시간을 알
뭔가 트라이에 있었다 여부를 확인,

363
00:15:13,480 --> 00:15:15,000
우리는 단지 4 이동했습니다.

364
00:15:15,000 --> 00:15:17,208
>> 우리가 원하는 때마다
트라이에 무언가를 삽입,

365
00:15:17,208 --> 00:15:20,440
우리는 아마도 4 이동을해야
길을 따라 몇 가지 물건을 mallocing.

366
00:15:20,440 --> 00:15:23,482
우리가 삽입 때 우리가 본 바와 같이
트라이에 다트머스,

367
00:15:23,482 --> 00:15:25,940
때때로 경로의 일부
이미 우리를 위해 삭제 될 수 있습니다.

368
00:15:25,940 --> 00:15:30,520
그래서 우리의 트라이가수록 더 크고
더 큰, 우리는 적은 작업을 할 때마다 수행해야

369
00:15:30,520 --> 00:15:32,270
새로운 것을 삽입
우리는 이미했습니다 때문에

370
00:15:32,270 --> 00:15:35,746
중간 많이 내장
길을 따라 가지.

371
00:15:35,746 --> 00:15:38,370
우리는 지금까지보고해야하는 경우
4 일, 4 단 일정하다.

372
00:15:38,370 --> 00:15:41,750
우리는 정말 가지 접근하고있다
일정 시간 삽입

373
00:15:41,750 --> 00:15:44,501
그리고 일정 시간 조회.

374
00:15:44,501 --> 00:15:47,500
트레이드 오프는 물론, 주도
이 트라이는,로 당신은 아마 알 수 있습니다

375
00:15:47,500 --> 00:15:49,030
거대하다​​.

376
00:15:49,030 --> 00:15:51,040
이러한 각 노드 하나
많은 공간을 차지한다.

377
00:15:51,040 --> 00:15:52,090
>> 그러나 그것은 트레이드 오프입니다.

378
00:15:52,090 --> 00:15:55,260
우리는 정말 빠른하려면
삽입, 정말 빠른 삭제,

379
00:15:55,260 --> 00:15:59,630
정말 빠른 조회, 우리는해야
많은 양의 데이터가 주위를 비행합니다.

380
00:15:59,630 --> 00:16:03,590
우리는 많은 공간을 따로 설정할 필요
그 데이터 구조에 대한 메모리

381
00:16:03,590 --> 00:16:04,290
존재합니다.

382
00:16:04,290 --> 00:16:05,415
>> 그리고 그 트레이드 오프입니다.

383
00:16:05,415 --> 00:16:07,310
하지만 우리처럼 보인다
그것을 발견했을 수 있습니다.

384
00:16:07,310 --> 00:16:09,560
우리는 것을 발견 할 수
데이터 구조의 성배

385
00:16:09,560 --> 00:16:12,264
빠른 삽입과,
삭제, 조회.

386
00:16:12,264 --> 00:16:14,430
그리고 어쩌면이 될 것입니다
적절한 데이터 구조

387
00:16:14,430 --> 00:16:18,890
어떤 정보를 사용하는
우리는 가게에 시도하고있다.

388
00:16:18,890 --> 00:16:21,860
내가 더그 로이드 해요,이 CS50입니다.

389
00:16:21,860 --> 00:16:23,433