1
00:00:00,000 --> 00:00:02,994
>> [MUSIC CHƠI]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Vì vậy, chúng tôi đã nhích gần hơn
và gần gũi hơn mà Chén thánh của dữ liệu

4
00:00:08,550 --> 00:00:13,050
cấu trúc, một trong đó chúng ta có thể chèn
vào, xóa từ, và nhìn lên

5
00:00:13,050 --> 00:00:15,440
trong thời gian liên tục.

6
00:00:15,440 --> 00:00:16,270
Bên phải.

7
00:00:16,270 --> 00:00:17,280
Đó là loại khung thành.

8
00:00:17,280 --> 00:00:19,720
Chúng tôi muốn có thể làm
điều rất, rất nhanh chóng.

9
00:00:19,720 --> 00:00:22,580
>> Chúng ta đã tìm thấy nó ở đây khi
chúng ta đang nói về cố gắng?

10
00:00:22,580 --> 00:00:23,670
Vâng, chúng ta hãy có một cái nhìn.

11
00:00:23,670 --> 00:00:25,628
Vì vậy, chúng tôi đã nhìn thấy một số
cấu trúc dữ liệu khác nhau

12
00:00:25,628 --> 00:00:28,680
có thể xử lý các bản đồ của
Cái gọi là cặp khóa-giá trị,

13
00:00:28,680 --> 00:00:32,080
lập bản đồ số phần dữ liệu
để một số phần khác của dữ liệu

14
00:00:32,080 --> 00:00:36,020
vì vậy chúng tôi biết nơi để tìm thấy
thông tin trong cấu trúc.

15
00:00:36,020 --> 00:00:40,060
>> Vì vậy, đối với mảng, ví dụ,
Điều quan trọng là các chỉ số phần tử hay mảng

16
00:00:40,060 --> 00:00:42,600
vị trí 0 hoặc 1 mảng và như vậy.

17
00:00:42,600 --> 00:00:46,140
Và giá trị là các dữ liệu
mà tồn tại ở vị trí đó.

18
00:00:46,140 --> 00:00:48,550
Vì vậy, những gì được lưu trữ trong mảng 0?

19
00:00:48,550 --> 00:00:54,290
Những gì được lưu trong mảng 1 so với chỉ
0 và 1, đó sẽ là chìa khóa.

20
00:00:54,290 --> 00:00:56,360
>> Với một bảng băm nó
loại ý tưởng tương tự.

21
00:00:56,360 --> 00:01:00,690
Với một bảng băm, chúng ta có băm này
chức năng mà tạo mã băm.

22
00:01:00,690 --> 00:01:03,670
Vì vậy, điều quan trọng là các mã băm của dữ liệu.

23
00:01:03,670 --> 00:01:06,530
Và giá trị, đặc biệt
chúng tôi nói chuyện về chuỗi

24
00:01:06,530 --> 00:01:10,590
trong đoạn video trên bảng băm,
là danh sách liên kết dữ liệu

25
00:01:10,590 --> 00:01:12,550
mà băm để hashcode đó.

26
00:01:12,550 --> 00:01:14,050
Bên phải.

27
00:01:14,050 --> 00:01:16,050
Những gì về cách tiếp cận khác
phương pháp này, mặc dù?

28
00:01:16,050 --> 00:01:21,000
Những gì về một phương pháp mà các
quan trọng là đảm bảo là duy nhất,

29
00:01:21,000 --> 00:01:25,410
không giống như một bảng băm, nơi chúng tôi có thể
kết thúc với hai mẩu dữ liệu

30
00:01:25,410 --> 00:01:27,200
có hashcode cùng.

31
00:01:27,200 --> 00:01:30,020
Và sau đó chúng ta phải đối phó với
rằng bằng cách hoặc là thăm dò hay hơn

32
00:01:30,020 --> 00:01:33,340
tốt chain để khắc phục vấn đề đó.

33
00:01:33,340 --> 00:01:37,520
>> Vì vậy, bây giờ chúng tôi có thể đảm bảo
rằng chính của chúng tôi là duy nhất.

34
00:01:37,520 --> 00:01:39,690
Và nếu giá trị của chúng tôi là
chỉ một cái gì đó dễ dàng

35
00:01:39,690 --> 00:01:44,080
như đúng và sai cho chúng ta biết liệu
hoặc không có mẩu thông tin

36
00:01:44,080 --> 00:01:45,610
tồn tại trong cấu trúc?

37
00:01:45,610 --> 00:01:48,180
Một Boolean có thể đơn giản như là một chút.

38
00:01:48,180 --> 00:01:52,660
Thực tế nó có thể là một
byte nhiều hơn một chút.

39
00:01:52,660 --> 00:01:55,410
Nhưng đó là nhỏ hơn rất nhiều so với
lưu trữ có thể là một chuỗi 50 ký tự,

40
00:01:55,410 --> 00:01:57,360
Ví dụ như.

41
00:01:57,360 --> 00:02:02,210
>> Vì vậy, cố gắng, tương tự như bảng băm,
trong đó kết hợp các mảng và danh sách liên kết,

42
00:02:02,210 --> 00:02:05,790
cố gắng kết hợp các mảng,
cấu trúc, và con trỏ

43
00:02:05,790 --> 00:02:08,509
với nhau để lưu trữ dữ liệu trong
một cách thú vị đó là

44
00:02:08,509 --> 00:02:11,550
khá khác nhau từ
bất cứ điều gì chúng ta đã thấy cho đến nay.

45
00:02:11,550 --> 00:02:16,750
Bây giờ chúng ta sử dụng các dữ liệu như là một lộ trình
để điều hướng cấu trúc dữ liệu này.

46
00:02:16,750 --> 00:02:18,710
Và nếu chúng ta có thể làm theo
lộ trình, nếu chúng ta có thể

47
00:02:18,710 --> 00:02:22,390
theo các dữ liệu từ
đầu đến cuối, chúng tôi sẽ

48
00:02:22,390 --> 00:02:24,945
biết liệu dữ liệu
tồn tại trong Trie.

49
00:02:24,945 --> 00:02:28,310
>> Và nếu chúng ta không thể làm theo bản đồ
từ có nghĩa là kết thúc ở tất cả,

50
00:02:28,310 --> 00:02:30,600
các dữ liệu không thể tồn tại.

51
00:02:30,600 --> 00:02:32,890
Một lần nữa, các phím ở đây là
đảm bảo là duy nhất.

52
00:02:32,890 --> 00:02:36,020
Và không giống như một bảng băm, chúng tôi sẽ không bao giờ
phải đối phó với các va chạm ở đây.

53
00:02:36,020 --> 00:02:39,090
Và không có hai mẩu dữ liệu
có chính xác cùng một lộ trình

54
00:02:39,090 --> 00:02:40,530
trừ khi dữ liệu đó là giống hệt nhau.

55
00:02:40,530 --> 00:02:44,580
>> Nếu chúng ta chèn John, sau đó
chúng tôi tìm kiếm cho John.

56
00:02:44,580 --> 00:02:47,430
Đó là hai phần giống hệt nhau của
dữ liệu, phải, chúng tôi đang tìm kiếm thông qua.

57
00:02:47,430 --> 00:02:49,880
Nhưng nếu không, bất kỳ
hai mẩu dữ liệu là

58
00:02:49,880 --> 00:02:52,750
đảm bảo để có lộ trình độc đáo
thông qua các cấu trúc dữ liệu này.

59
00:02:52,750 --> 00:02:56,210
Và chúng ta sẽ có một cái nhìn tại
một hình ảnh của này chỉ trong một khoảnh khắc.

60
00:02:56,210 --> 00:02:58,810
>> Chúng tôi sẽ làm điều này bằng cách cố gắng
tạo ra một cấu trúc dữ liệu mới,

61
00:02:58,810 --> 00:03:00,564
lập bản đồ các cặp giá trị quan trọng sau đây.

62
00:03:00,564 --> 00:03:03,480
Trong trường hợp này, chúng tôi sẽ không sử dụng
một cái gì đó đơn giản như một Boolean.

63
00:03:03,480 --> 00:03:06,200
Chúng tôi sẽ thực sự lưu trữ các chuỗi.

64
00:03:06,200 --> 00:03:08,690
Và chuỗi được sắp
là tên của một trường đại học.

65
00:03:08,690 --> 00:03:12,140
>> Và chìa khóa là có được năm
khi các trường đại học được thành lập.

66
00:03:12,140 --> 00:03:15,380
Tất cả các trường đại học năm
sẽ có bốn chữ số.

67
00:03:15,380 --> 00:03:19,840
Và vì vậy chúng tôi sẽ sử dụng những bốn chữ số
điều hướng thông qua các cấu trúc dữ liệu này.

68
00:03:19,840 --> 00:03:22,270
Và chúng ta sẽ thấy, một lần nữa, làm thế nào
chúng tôi làm điều đó chỉ trong một giây.

69
00:03:22,270 --> 00:03:25,110
>> Vào cuối của con đường,
chúng ta sẽ thấy tên

70
00:03:25,110 --> 00:03:30,250
của các trường đại học tương ứng
với phím đó, bốn chữ số.

71
00:03:30,250 --> 00:03:34,390
Ý tưởng cơ bản đằng sau một Trie
là chúng ta có một tuyến đường trung tâm.

72
00:03:34,390 --> 00:03:35,640
Vì vậy, suy nghĩ về nó như một cái cây.

73
00:03:35,640 --> 00:03:39,211
Và điều này cũng tương tự như trong chính tả
và trong khái niệm một cái cây.

74
00:03:39,211 --> 00:03:41,460
Thông thường khi chúng ta nghĩ về
cây trong thế giới thực,

75
00:03:41,460 --> 00:03:44,090
họ có một gốc đó là trong
mặt đất và chúng lớn lên

76
00:03:44,090 --> 00:03:46,830
và họ có các chi nhánh
và họ có lá.

77
00:03:46,830 --> 00:03:49,450
Và về cơ bản các ý tưởng của
một Trie là giống hệt nhau,

78
00:03:49,450 --> 00:03:51,755
trừ gốc được neo
một nơi nào đó trên bầu trời.

79
00:03:51,755 --> 00:03:53,130
Và lá ở phía dưới.

80
00:03:53,130 --> 00:03:55,750
>> Vì vậy, nó là loại giống như dùng một cây
và chỉ flipping nó lộn ngược.

81
00:03:55,750 --> 00:03:56,880
Nhưng vẫn có những lĩnh.

82
00:03:56,880 --> 00:03:59,463
Và những người sẽ là con đường của chúng tôi,
những người sẽ kết nối chúng tôi

83
00:03:59,463 --> 00:04:02,220
từ gốc đến lá.

84
00:04:02,220 --> 00:04:04,200
Trong trường hợp này, những người
con đường, những chi nhánh

85
00:04:04,200 --> 00:04:08,490
được dán nhãn bằng các con số đó cho chúng tôi
có cách nào để đi từ nơi mà chúng ta đang có.

86
00:04:08,490 --> 00:04:11,800
>> 0 nếu chúng ta thấy, chúng ta đi xuống chi nhánh này,
nếu chúng ta nhìn thấy một 1, chúng tôi đi xuống chi nhánh này,

87
00:04:11,800 --> 00:04:12,900
và như vậy và như vậy.

88
00:04:12,900 --> 00:04:14,060
Vâng, điều này có nghĩa là gì?

89
00:04:14,060 --> 00:04:16,519
Vâng, điều đó có nghĩa rằng
tại mỗi điểm giao nhau

90
00:04:16,519 --> 00:04:19,260
và tất cả các nút trong
giữa và các chi nhánh,

91
00:04:19,260 --> 00:04:23,020
có 10 thể
những nơi mà chúng ta có thể đi.

92
00:04:23,020 --> 00:04:27,690
Vì vậy, có 10 con trỏ
từ mọi vị trí.

93
00:04:27,690 --> 00:04:30,610
>> Và đây là nơi mà cố gắng có thể có được một
chút đáng sợ cho ai đó

94
00:04:30,610 --> 00:04:34,460
những người không có nhiều
kinh nghiệm trong khoa học máy tính trước.

95
00:04:34,460 --> 00:04:35,960
Nhưng cố gắng thực sự là khá tuyệt vời.

96
00:04:35,960 --> 00:04:37,793
Và nếu bạn có
cơ hội để làm việc với họ

97
00:04:37,793 --> 00:04:40,420
và bạn đã sẵn sàng để đào-in
và thử nghiệm với họ,

98
00:04:40,420 --> 00:04:44,234
chúng thực sự khá thú vị
cấu trúc dữ liệu để làm việc với.

99
00:04:44,234 --> 00:04:46,900
Nếu chúng ta muốn chèn một phần tử
vào Trie, tất cả chúng ta cần phải làm

100
00:04:46,900 --> 00:04:51,360
được xây dựng con đường đúng
từ gốc đến lá.

101
00:04:51,360 --> 00:04:55,390
Dưới đây là những gì mọi bước dọc
đường có thể trông như thế nào.

102
00:04:55,390 --> 00:04:59,660
Chúng tôi sẽ xác định một dữ liệu mới
cấu trúc cho một nút mới được gọi là một Trie.

103
00:04:59,660 --> 00:05:02,560
>> Và bên trong các dữ liệu mà
cấu trúc có hai miếng.

104
00:05:02,560 --> 00:05:05,460
Chúng ta sẽ lưu các
tên của một trường đại học.

105
00:05:05,460 --> 00:05:09,410
Và chúng ta sẽ lưu
một mảng của các con trỏ

106
00:05:09,410 --> 00:05:12,190
với các nút khác cùng loại.

107
00:05:12,190 --> 00:05:14,780
Vì vậy, một lần nữa, đây là loại đó
các khái niệm về khắp mọi nơi

108
00:05:14,780 --> 00:05:18,567
chúng tôi, chúng tôi có thể ở mức 10
nơi chúng ta có thể đi.

109
00:05:18,567 --> 00:05:20,150
0 nếu chúng ta thấy, chúng ta đi xuống chi nhánh này.

110
00:05:20,150 --> 00:05:22,690
Nếu chúng ta nhìn thấy một 1, chi nhánh này,
vv và vv và vv.

111
00:05:22,690 --> 00:05:25,160
Nếu chúng ta nói 9, chúng tôi đi xuống chi nhánh này.

112
00:05:25,160 --> 00:05:28,220
Vì vậy, tại mỗi điểm giao nhau,
chúng ta có thể đi 10 địa điểm có thể.

113
00:05:28,220 --> 00:05:35,740
Vì vậy, mỗi node có chứa 10 con trỏ
với các nút khác, để 10 nút khác.

114
00:05:35,740 --> 00:05:39,810
>> Và các dữ liệu chúng tôi đang lưu trữ là
chỉ là tên của các trường đại học.

115
00:05:39,810 --> 00:05:41,060
Vì vậy, hãy xây dựng một Trie.

116
00:05:41,060 --> 00:05:44,860
Hãy chèn một vài
các mục vào Trie của chúng tôi.

117
00:05:44,860 --> 00:05:46,740
Vì vậy, ở phía trên đỉnh,
đây là nút gốc của chúng tôi.

118
00:05:46,740 --> 00:05:49,740
Đây có lẽ sẽ là một cái gì
bạn đang đi trên toàn cầu khai báo.

119
00:05:49,740 --> 00:05:53,450
Và bạn đang đi trên toàn cầu duy trì
một con trỏ đến nút này luôn.

120
00:05:53,450 --> 00:05:55,360
>> Bạn sẽ nói,
gốc bằng, và bạn

121
00:05:55,360 --> 00:05:57,580
đi để malloc mình nút Trie.

122
00:05:57,580 --> 00:05:59,850
Và bạn sẽ không bao giờ
chạm vào gốc một lần nữa.

123
00:05:59,850 --> 00:06:02,300
Mỗi khi bạn muốn
bắt đầu điều hướng thông qua,

124
00:06:02,300 --> 00:06:05,802
bạn đặt con trỏ khác
bằng gốc, chẳng hạn như trav,

125
00:06:05,802 --> 00:06:07,760
đó là những ví dụ tôi
sử dụng trong rất nhiều các video của tôi

126
00:06:07,760 --> 00:06:11,090
đây trên ngăn xếp và hàng đợi
và danh sách liên kết và như vậy.

127
00:06:11,090 --> 00:06:13,320
>> Bạn đặt con trỏ khác
gọi trav cho traversal.

128
00:06:13,320 --> 00:06:15,890
Và bạn sử dụng để điều hướng trav
thông qua các cấu trúc dữ liệu.

129
00:06:15,890 --> 00:06:17,500
Vì vậy, chúng ta hãy xem làm thế nào điều này có thể xem xét.

130
00:06:17,500 --> 00:06:19,880
Vì vậy, ngay bây giờ, những gì
không một nút như thế nào?

131
00:06:19,880 --> 00:06:22,920
Vâng, chỉ là dữ liệu của chúng tôi
khai báo cấu trúc chỉ ra,

132
00:06:22,920 --> 00:06:26,906
chúng ta có một chuỗi,
trong trường hợp này là trống rỗng.

133
00:06:26,906 --> 00:06:27,780
Không có gì ở đây cả.

134
00:06:27,780 --> 00:06:29,550
>> Và một mảng 10 con trỏ.

135
00:06:29,550 --> 00:06:31,790
Và ngay bây giờ, chúng ta chỉ
có 1 nút ở Trie này.

136
00:06:31,790 --> 00:06:33,110
Không có gì khác trong nó.

137
00:06:33,110 --> 00:06:36,020
Vì vậy, tất cả 10 người
điểm con trỏ null.

138
00:06:36,020 --> 00:06:38,090
Đó là những gì màu đỏ cho biết.

139
00:06:38,090 --> 00:06:39,500
>> Hãy chèn chuỗi Harvard.

140
00:06:39,500 --> 00:06:41,999
Hãy chèn Đại học
Harvard vào Trie này, mà

141
00:06:41,999 --> 00:06:43,940
được thành lập vào năm 1636.

142
00:06:43,940 --> 00:06:48,220
Chúng tôi muốn sử dụng chìa khóa,
1636, cho chúng tôi biết chúng tôi

143
00:06:48,220 --> 00:06:50,140
sẽ lưu học Harvard ở Trie.

144
00:06:50,140 --> 00:06:51,470
Bây giờ, làm thế nào chúng ta có thể làm điều đó?

145
00:06:51,470 --> 00:06:52,886
>> Nó có thể giống như thế này.

146
00:06:52,886 --> 00:06:54,160
Chúng tôi bắt đầu từ gốc rễ.

147
00:06:54,160 --> 00:06:56,920
Và chúng ta có những 10 địa điểm chúng ta có thể đi.

148
00:06:56,920 --> 00:06:59,900
Gốc là giống như bất kỳ
nút khác của Trie.

149
00:06:59,900 --> 00:07:02,850
Có 10 địa điểm chúng ta có thể đi từ đây.

150
00:07:02,850 --> 00:07:07,215
>> Nơi nào chúng ta có thể muốn
để đi nếu chính là năm 1636?

151
00:07:07,215 --> 00:07:08,340
Có thực sự hai lựa chọn.

152
00:07:08,340 --> 00:07:08,450
Bên phải.

153
00:07:08,450 --> 00:07:10,825
Chúng tôi có thể xây dựng các chính từ
phải sang trái và bắt đầu với 6.

154
00:07:10,825 --> 00:07:14,000
Hoặc chúng ta có thể xây dựng các chính từ
trái sang phải và bắt đầu với 1.

155
00:07:14,000 --> 00:07:16,140
>> Đây có thể là nhiều hơn
trực quan như một con người

156
00:07:16,140 --> 00:07:18,110
để hiểu rằng chúng tôi sẽ
chỉ đi trái sang phải.

157
00:07:18,110 --> 00:07:21,140
Và vì vậy nếu tôi muốn chèn
Harvard vào Trie này,

158
00:07:21,140 --> 00:07:23,560
Tôi có lẽ muốn bắt đầu
được bắt đầu từ gốc,

159
00:07:23,560 --> 00:07:25,720
nhìn vào 10 Lựa chọn của tôi
trước mặt tôi, và nói

160
00:07:25,720 --> 00:07:28,700
Tôi muốn đi theo con đường 1.

161
00:07:28,700 --> 00:07:29,700
ĐƯỢC.

162
00:07:29,700 --> 00:07:31,810
>> Bây giờ, 1 con đường là hiện null.

163
00:07:31,810 --> 00:07:35,920
Vì vậy, nếu tôi muốn tiếp tục con đường đó
để chèn phần tử này vào Trie,

164
00:07:35,920 --> 00:07:42,040
Tôi có để malloc một nút mới, có 1
điểm đó, và sau đó tôi là tốt để đi.

165
00:07:42,040 --> 00:07:46,460
>> Vì vậy, về cơ bản tôi đang ở một
điểm mà tôi đang đứng

166
00:07:46,460 --> 00:07:50,270
ở gốc của cây hoặc
Trie và có 10 chi nhánh.

167
00:07:50,270 --> 00:07:52,260
Nhưng mỗi chi nhánh có một
cổng ở phía trước của nó.

168
00:07:52,260 --> 00:07:53,060
Bên phải.

169
00:07:53,060 --> 00:07:54,850
Bởi vì không có gì khác có.

170
00:07:54,850 --> 00:07:56,522
Không có lối đi an toàn.

171
00:07:56,522 --> 00:07:58,980
Điều đó có nghĩa rằng không có gì là
xuống bất kỳ của các ngành đó.

172
00:07:58,980 --> 00:08:02,532
Nếu tôi muốn bắt đầu xây dựng
một cái gì đó, tôi muốn loại bỏ các cửa khẩu.

173
00:08:02,532 --> 00:08:04,490
Tôi muốn loại bỏ cổng
trước số 1.

174
00:08:04,490 --> 00:08:05,698
Và tôi muốn đi bộ xuống đó.

175
00:08:05,698 --> 00:08:08,060
Và tôi muốn xây dựng
một nơi để tôi đi.

176
00:08:08,060 --> 00:08:09,470
>> Và đó là những gì tôi đã thực hiện ở đây.

177
00:08:09,470 --> 00:08:11,430
Vì vậy, 1 không còn chỉ để null.

178
00:08:11,430 --> 00:08:13,830
Tôi đã nói nó an toàn để đi xuống đây ngay bây giờ.

179
00:08:13,830 --> 00:08:15,789
Tôi xây dựng một nút khác.

180
00:08:15,789 --> 00:08:18,330
Và khi tôi được nút đó, tôi
có một quyết định để thực hiện.

181
00:08:18,330 --> 00:08:20,890
Tôi sẽ đi đâu để đi từ đây?

182
00:08:20,890 --> 00:08:22,700
>> Vâng, tôi đã đi xuống 1.

183
00:08:22,700 --> 00:08:24,470
Vì vậy, bây giờ tôi có thể muốn đi xuống 6.

184
00:08:24,470 --> 00:08:24,970
Bên phải.

185
00:08:24,970 --> 00:08:27,100
Một lần nữa, tôi có 10 địa điểm tôi có thể lựa chọn.

186
00:08:27,100 --> 00:08:30,060
Vì vậy, bây giờ chúng ta đi xuống số 6.

187
00:08:30,060 --> 00:08:32,280
Vì vậy, tôi xóa cổng
ở phía trước của số 6.

188
00:08:32,280 --> 00:08:33,250
Và tôi đi bộ xuống đó.

189
00:08:33,250 --> 00:08:34,580
Và tôi xây dựng một nút khác.

190
00:08:34,580 --> 00:08:37,630
Và tôi đã đạt đến một điểm giao nhau.

191
00:08:37,630 --> 00:08:40,289
>> Một lần nữa, tôi có 10 lựa chọn
cho nơi tôi có thể đi.

192
00:08:40,289 --> 00:08:42,799
Tôi đã di chuyển 1-6.

193
00:08:42,799 --> 00:08:44,215
Vì vậy, bây giờ tôi có thể muốn đi đến 3.

194
00:08:44,215 --> 00:08:45,381
3, có nơi nào tôi có thể đi.

195
00:08:45,381 --> 00:08:48,980
Vì vậy, tôi phải dọn đường
và xây dựng cho mình một không gian mới.

196
00:08:48,980 --> 00:08:50,870
Và sau đó từ 3, nơi nào tôi muốn đi đâu?

197
00:08:50,870 --> 00:08:52,450
Tôi muốn đi xuống 6.

198
00:08:52,450 --> 00:08:54,770
>> Và, một lần nữa, tôi đã phải
dọn đường để làm điều đó.

199
00:08:54,770 --> 00:08:59,179
Vì vậy, bây giờ tôi đã sử dụng chìa khóa của tôi để chèn tạo
nút và bắt đầu xây dựng Trie này.

200
00:08:59,179 --> 00:09:00,220
Tôi đã bắt đầu ở gốc.

201
00:09:00,220 --> 00:09:03,666
Tôi đã đi xuống 1636.

202
00:09:03,666 --> 00:09:05,540
Và bây giờ tôi đang ở phía dưới
có vào nút đó.

203
00:09:05,540 --> 00:09:06,610
Và bạn có thể có thể
nhìn thấy nó trên màn hình của bạn.

204
00:09:06,610 --> 00:09:07,735
>> Nó đánh dấu màu vàng.

205
00:09:07,735 --> 00:09:10,020
Đó là nơi mà tôi hiện nay.

206
00:09:10,020 --> 00:09:11,300
Chìa khóa của tôi được thực hiện.

207
00:09:11,300 --> 00:09:13,030
Tôi đã kiệt sức từng vị trí trong chính tôi.

208
00:09:13,030 --> 00:09:15,040
Vì vậy, tôi không thể đi xa hơn nữa.

209
00:09:15,040 --> 00:09:17,720
Vì vậy, tại thời điểm này, tất cả tôi
thực sự cần phải làm là nói, OK.

210
00:09:17,720 --> 00:09:18,990
Nó loại thích tìm kiếm
xuống đất,

211
00:09:18,990 --> 00:09:21,115
nếu bạn đang hình dung
mình là loại này con đường

212
00:09:21,115 --> 00:09:22,350
với các kết nối khác nhau.

213
00:09:22,350 --> 00:09:25,800
Sắp xếp nhìn xuống và loại
phun sơn Harvard trên mặt đất.

214
00:09:25,800 --> 00:09:26,800
Đó là tên của điều này.

215
00:09:26,800 --> 00:09:28,300
Biết đó là những gì tại địa điểm này.

216
00:09:28,300 --> 00:09:31,870
Nếu chúng ta bắt đầu ở gốc và chúng tôi đi xuống
1 và sau đó 6 và sau đó 3 và sau đó 6,

217
00:09:31,870 --> 00:09:32,780
chúng ta ở đâu?

218
00:09:32,780 --> 00:09:35,640
Vâng, nếu chúng ta nhìn xuống
và chúng ta thấy Harvard, sau đó

219
00:09:35,640 --> 00:09:38,960
chúng ta biết rằng Harvard là
thành lập năm 1636 có trụ sở trên đường

220
00:09:38,960 --> 00:09:41,400
chúng tôi đang thực thi cấu trúc dữ liệu này.

221
00:09:41,400 --> 00:09:43,177
Vì vậy, đó là hy vọng đơn giản.

222
00:09:43,177 --> 00:09:44,760
Chúng ta sẽ phải làm hai phần thêm vào nhiều hơn nữa.

223
00:09:44,760 --> 00:09:50,060
Và hy vọng rằng nó sẽ giúp
thấy điều này được thực hiện hai lần nữa.

224
00:09:50,060 --> 00:09:52,210
>> Bây giờ, chúng ta hãy chèn các trường đại học khác.

225
00:09:52,210 --> 00:09:54,630
Hãy chèn Yale vào Trie này.

226
00:09:54,630 --> 00:09:57,037
Yale được thành lập vào năm 1701.

227
00:09:57,037 --> 00:09:58,870
Vì vậy, chúng tôi sẽ bắt đầu ở
root, như chúng ta vẫn thường làm.

228
00:09:58,870 --> 00:09:59,890
Và chúng tôi thiết lập một con trỏ traversal.

229
00:09:59,890 --> 00:10:01,624
Chúng ta sẽ sử dụng để di chuyển qua.

230
00:10:01,624 --> 00:10:03,790
Điều đầu tiên chúng tôi muốn
làm là đi xuống con đường 1.

231
00:10:03,790 --> 00:10:05,830
Đó là chữ số đầu tiên của chính chúng tôi.

232
00:10:05,830 --> 00:10:08,420
May mắn thay, tuy nhiên, chúng tôi không
phải làm bất kỳ công việc lần này.

233
00:10:08,420 --> 00:10:09,919
Các đường 1 đã được giải tỏa.

234
00:10:09,919 --> 00:10:13,520
Tôi xóa nó trước khi tôi
được chèn Harvard tại 1636.

235
00:10:13,520 --> 00:10:18,090
Vì vậy, tôi có thể di chuyển một cách an toàn
xuống 1 và chỉ đi đến đó.

236
00:10:18,090 --> 00:10:20,150
Nếu có thể di chuyển xuống 1.

237
00:10:20,150 --> 00:10:22,930
>> Bây giờ, tuy nhiên, tôi muốn đi đến 7.

238
00:10:22,930 --> 00:10:24,280
Tôi đã mở đường tại 6.

239
00:10:24,280 --> 00:10:27,050
Tôi biết tôi có thể an toàn
đi xuống 6 con đường.

240
00:10:27,050 --> 00:10:29,220
Nhưng tôi cần phải tiến hành trên con đường 7.

241
00:10:29,220 --> 00:10:30,580
Vì vậy, những gì tôi cần phải làm gì?

242
00:10:30,580 --> 00:10:35,070
Vâng, giống như trước đây, tôi chỉ cần
để xóa các cửa khẩu, có được ra khỏi con đường,

243
00:10:35,070 --> 00:10:38,740
và xây dựng một nút mới từ con đường 7.

244
00:10:38,740 --> 00:10:40,250
Chỉ như thế này.

245
00:10:40,250 --> 00:10:42,930
>> Vì vậy, bây giờ tôi đã thay đổi 1 và sau đó 7.

246
00:10:42,930 --> 00:10:45,550
Và bây giờ thông báo, tôi đang sắp xếp
của trên nhánh phụ mới này.

247
00:10:45,550 --> 00:10:46,050
Bên phải.

248
00:10:46,050 --> 00:10:49,260
Mọi thứ khác từ 16
trên, tôi không quan tâm.

249
00:10:49,260 --> 00:10:50,720
Tôi không làm bất cứ điều gì 16.

250
00:10:50,720 --> 00:10:51,750
Tôi đang làm 17 công cụ.

251
00:10:51,750 --> 00:10:58,380
>> Vì vậy, bây giờ từ 17 trở đi, tôi phải
loại blaze đường mòn mới đây.

252
00:10:58,380 --> 00:11:00,462
Các chữ số tiếp theo chìa khóa của tôi là 0.

253
00:11:00,462 --> 00:11:01,670
Tôi rõ ràng không thể có được bất cứ nơi nào.

254
00:11:01,670 --> 00:11:02,628
Tôi chỉ cần xây dựng nút này.

255
00:11:02,628 --> 00:11:04,550
Vì vậy, tôi biết không có
con đường phía trước từ đây.

256
00:11:04,550 --> 00:11:06,370
Vì vậy, tôi phải làm một bản thân mình.

257
00:11:06,370 --> 00:11:09,360
>> Vì vậy, tôi malloc một nút mới
và có 0 điểm đó.

258
00:11:09,360 --> 00:11:12,770
Và sau đó một lần nữa, tôi malloc một
nút mới và có một điểm ở đó.

259
00:11:12,770 --> 00:11:15,870
Một lần nữa, tôi đã kiệt sức quan trọng của tôi, năm 1701.

260
00:11:15,870 --> 00:11:18,472
Vì vậy, tôi nhìn xuống và tôi phun sơn Yale.

261
00:11:18,472 --> 00:11:19,680
Đó là tên của nút này.

262
00:11:19,680 --> 00:11:24,660
>> Và vì vậy bây giờ nếu tôi cần phải xem nếu Yale
đang ở Trie này, tôi bắt đầu ở gốc,

263
00:11:24,660 --> 00:11:27,060
Tôi đi xuống 1701, và nhìn xuống.

264
00:11:27,060 --> 00:11:30,030
Và nếu tôi thấy phun Yale
sơn lên mặt đất, sau đó

265
00:11:30,030 --> 00:11:32,200
Tôi biết Yale tồn tại Trie này.

266
00:11:32,200 --> 00:11:32,950
Hãy làm một nhiều hơn.

267
00:11:32,950 --> 00:11:36,430
Hãy chèn Dartmouth vào đây
Trie, được thành lập vào năm 1769.

268
00:11:36,430 --> 00:11:37,750
>> Bắt đầu tại gốc một lần nữa.

269
00:11:37,750 --> 00:11:39,445
Chữ số đầu tiên của tôi về chìa khóa của tôi là 1.

270
00:11:39,445 --> 00:11:40,820
Tôi một cách an toàn có thể di chuyển xuống con đường đó.

271
00:11:40,820 --> 00:11:42,400
Điều đó đã tồn tại.

272
00:11:42,400 --> 00:11:44,040
Các chữ số tiếp theo của chính tôi là 7.

273
00:11:44,040 --> 00:11:45,890
Tôi một cách an toàn có thể di chuyển xuống con đường đó.

274
00:11:45,890 --> 00:11:47,540
Nó tồn tại là tốt.

275
00:11:47,540 --> 00:11:49,000
>> Tiếp theo của tôi là 6.

276
00:11:49,000 --> 00:11:52,860
Từ đây, từ nơi tôi hiện nay
màu vàng có trong đó nút giữa,

277
00:11:52,860 --> 00:11:56,060
6 hiện đang bị khóa ra.

278
00:11:56,060 --> 00:11:58,830
Nếu tôi muốn đi xuống con đường đó,
Tôi có để xây dựng bản thân mình.

279
00:11:58,830 --> 00:12:02,250
Vì vậy, tôi sẽ malloc một nút mới
và có 6 điểm ở đó.

280
00:12:02,250 --> 00:12:04,250
Và sau đó, một lần nữa, tôi
lòng đam mê những con đường mòn mới đây.

281
00:12:04,250 --> 00:12:10,750
>> Vì vậy, tôi malloc một nút mới để từ
rằng số con đường node-- 9-- và sau đó bây giờ

282
00:12:10,750 --> 00:12:13,584
nếu tôi đi du lịch năm 1769, và tôi nhìn xuống.

283
00:12:13,584 --> 00:12:15,500
Không có gì hiện
phun sơn có.

284
00:12:15,500 --> 00:12:16,930
Tôi có thể viết Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Và tôi đã chèn
Dartmouth vào Trie.

286
00:12:20,710 --> 00:12:23,450
>> Vì vậy, đó là chèn
điều vào Trie.

287
00:12:23,450 --> 00:12:25,384
Bây giờ chúng tôi muốn tìm kiếm những điều.

288
00:12:25,384 --> 00:12:27,050
Làm thế nào để chúng tôi tìm kiếm những thứ trong Trie?

289
00:12:27,050 --> 00:12:29,170
Vâng, đó là khá nhiều những ý tưởng tương tự.

290
00:12:29,170 --> 00:12:33,620
Bây giờ chúng ta chỉ cần sử dụng các chữ số của khóa
để xem liệu chúng ta có thể di chuyển từ gốc

291
00:12:33,620 --> 00:12:37,170
đến nơi mà chúng ta muốn đi trong Trie.

292
00:12:37,170 --> 00:12:41,620
>> Nếu chúng ta đánh một kết thúc chết vào thời điểm bất kỳ, sau đó
chúng ta biết rằng yếu tố đó không thể tồn tại

293
00:12:41,620 --> 00:12:44,500
hoặc người nào khác con đường đó sẽ
đã được giải tỏa.

294
00:12:44,500 --> 00:12:45,930
Nếu chúng ta làm cho nó tất cả các cách để
Cuối cùng, tất cả chúng ta cần phải làm

295
00:12:45,930 --> 00:12:48,471
là nhìn xuống và thấy nếu đó là
các yếu tố chúng tôi đang tìm kiếm.

296
00:12:48,471 --> 00:12:49,335
Nếu có, thành công.

297
00:12:49,335 --> 00:12:52,610
Nếu không, không.

298
00:12:52,610 --> 00:12:54,940
>> Vì vậy, hãy tìm kiếm
Harvard ở Trie này.

299
00:12:54,940 --> 00:12:56,020
Chúng tôi bắt đầu từ gốc rễ.

300
00:12:56,020 --> 00:12:58,228
Và, một lần nữa, chúng ta sẽ
tạo ra một con trỏ traversal

301
00:12:58,228 --> 00:12:59,390
để làm di chuyển của chúng tôi đối với chúng tôi.

302
00:12:59,390 --> 00:13:02,080
Từ gốc chúng ta biết rằng
nơi đầu tiên chúng ta cần phải đi là 1,

303
00:13:02,080 --> 00:13:03,390
chúng ta có thể làm điều đó?

304
00:13:03,390 --> 00:13:03,982
Vâng, chúng tôi có thể.

305
00:13:03,982 --> 00:13:04,690
Nếu an toàn tồn tại.

306
00:13:04,690 --> 00:13:06,660
Chúng tôi có thể đến đó.

307
00:13:06,660 --> 00:13:08,440
>> Bây giờ, địa điểm tiếp theo chúng ta cần phải đi là 6.

308
00:13:08,440 --> 00:13:10,557
Có 6 con đường tồn tại từ đây?

309
00:13:10,557 --> 00:13:11,140
Vâng, nó.

310
00:13:11,140 --> 00:13:12,690
Chúng tôi có thể đi xuống trong 6 đường.

311
00:13:12,690 --> 00:13:13,905
Và chúng ta kết thúc ở đây.

312
00:13:13,905 --> 00:13:16,130
>> Chúng ta có thể đi xuống 3 đường đi từ đây?

313
00:13:16,130 --> 00:13:18,450
Vâng, khi nó quay ra,
có, mà tồn tại quá.

314
00:13:18,450 --> 00:13:20,790
Và chúng ta có thể nhận được trên 6 đường đi từ đây?

315
00:13:20,790 --> 00:13:21,982
Vâng, chúng tôi có thể.

316
00:13:21,982 --> 00:13:24,002
>> Chúng tôi đã không hoàn toàn trả lời
các câu hỏi được nêu ra.

317
00:13:24,002 --> 00:13:25,710
Vẫn có một nhiều hơn
bước, mà bây giờ là

318
00:13:25,710 --> 00:13:28,520
chúng ta cần phải nhìn xuống và
xem đó là actually--

319
00:13:28,520 --> 00:13:32,660
nếu chúng ta đang tìm kiếm Harvard, là
những gì chúng tôi tìm thấy sau khi chúng tôi cạn kiệt phím?

320
00:13:32,660 --> 00:13:35,430
Trong ví dụ này chúng ta sử dụng ở đây,
những năm qua luôn bốn chữ số.

321
00:13:35,430 --> 00:13:40,280
Nhưng bạn có thể sử dụng ví dụ nơi
bạn đang lưu trữ một từ điển các từ.

322
00:13:40,280 --> 00:13:44,060
>> Và do đó, thay vì có 10 con trỏ
cho vị trí của tôi, bạn có thể có 26.

323
00:13:44,060 --> 00:13:46,040
Một cho mỗi chữ cái của bảng chữ cái.

324
00:13:46,040 --> 00:13:50,350
Và có một số từ như dơi,
mà là một tập hợp con của hàng loạt, ví dụ.

325
00:13:50,350 --> 00:13:53,511
Và do đó, ngay cả khi bạn nhận được đến
cuối khóa và bạn nhìn xuống,

326
00:13:53,511 --> 00:13:55,260
bạn có thể không nhìn thấy gì
bạn đang tìm kiếm.

327
00:13:55,260 --> 00:13:58,500
>> Vì vậy, bạn luôn phải đi qua
toàn bộ con đường và sau đó

328
00:13:58,500 --> 00:14:01,540
nếu bạn là thành công có thể
để đi qua toàn bộ con đường,

329
00:14:01,540 --> 00:14:03,440
nhìn xuống và làm một xác nhận cuối cùng.

330
00:14:03,440 --> 00:14:05,120
Có phải đó là những gì tôi đang tìm kiếm?

331
00:14:05,120 --> 00:14:07,740
Vâng, tôi nhìn xuống sau khi bắt đầu
ở đầu và đi 1636.

332
00:14:07,740 --> 00:14:08,240
Tôi nhìn xuống.

333
00:14:08,240 --> 00:14:09,400
Tôi thấy Harvard.

334
00:14:09,400 --> 00:14:11,689
Vì vậy, có, tôi đã thành công.

335
00:14:11,689 --> 00:14:13,980
Điều gì nếu những gì tôi đang tìm kiếm
không có trong Trie, mặc dù.

336
00:14:13,980 --> 00:14:17,200
Nếu tôi đang tìm Princeton,
được thành lập năm 1746.

337
00:14:17,200 --> 00:14:20,875
Và do đó, năm 1746 sẽ trở thành chìa khóa của tôi
để điều hướng thông qua các Trie.

338
00:14:20,875 --> 00:14:22,040
Vâng, tôi bắt đầu từ gốc rễ.

339
00:14:22,040 --> 00:14:24,760
Và nơi đầu tiên tôi muốn
để đi xuống con đường 1.

340
00:14:24,760 --> 00:14:25,590
Tôi có thể làm điều đó?

341
00:14:25,590 --> 00:14:26,490
Vâng tôi có thể.

342
00:14:26,490 --> 00:14:28,730
>> Tôi có thể đi xuống con đường 7 từ đó?

343
00:14:28,730 --> 00:14:29,230
Vâng, tôi có thể.

344
00:14:29,230 --> 00:14:30,750
Mà tồn tại quá.

345
00:14:30,750 --> 00:14:32,460
Nhưng tôi có thể đi xuống 4 đường đi từ đây?

346
00:14:32,460 --> 00:14:35,550
Điều đó giống như đặt câu hỏi, có thể
Tôi đi xuống mà hơi vuông

347
00:14:35,550 --> 00:14:37,114
mà tôi đã đánh dấu màu vàng?

348
00:14:37,114 --> 00:14:38,030
Có gì ở đó.

349
00:14:38,030 --> 00:14:38,610
Bên phải.

350
00:14:38,610 --> 00:14:41,310
>> Không có con đường phía trước xuống con đường 4.

351
00:14:41,310 --> 00:14:46,480
Nếu Princeton là ở Trie này, mà 4
sẽ được giải tỏa cho chúng ta rồi.

352
00:14:46,480 --> 00:14:49,130
Và vào thời điểm này
chúng tôi đã đạt đến một kết thúc chết.

353
00:14:49,130 --> 00:14:50,250
Chúng tôi không thể đi xa hơn nữa.

354
00:14:50,250 --> 00:14:53,440
Và vì vậy chúng tôi có thể nói, dứt khoát, không có.

355
00:14:53,440 --> 00:14:56,760
Princeton không tồn tại trong Trie này.

356
00:14:56,760 --> 00:14:58,860
>> Vì vậy, điều này có nghĩa là tất cả?

357
00:14:58,860 --> 00:14:59,360
Bên phải.

358
00:14:59,360 --> 00:15:01,000
Có rất nhiều xảy ra ở đây.

359
00:15:01,000 --> 00:15:02,500
Có con trỏ khắp nơi.

360
00:15:02,500 --> 00:15:04,249
Và, như bạn có thể nhìn thấy
chỉ từ các sơ đồ,

361
00:15:04,249 --> 00:15:07,010
có rất nhiều các nút đó
được loại bay xung quanh.

362
00:15:07,010 --> 00:15:13,480
Nhưng chú ý mỗi khi chúng ta muốn
kiểm tra xem có điều gì đó trong Trie,

363
00:15:13,480 --> 00:15:15,000
chúng tôi chỉ có để làm cho 4 di chuyển.

364
00:15:15,000 --> 00:15:17,208
>> Mỗi lần chúng tôi muốn
chèn một cái gì đó trong Trie,

365
00:15:17,208 --> 00:15:20,440
chúng ta phải làm cho 4 di chuyển, có thể
mallocing một số thứ trên đường đi.

366
00:15:20,440 --> 00:15:23,482
Tuy nhiên, như chúng ta đã thấy khi chúng ta chèn
Dartmouth vào Trie,

367
00:15:23,482 --> 00:15:25,940
đôi khi một số con đường
có thể đã được xóa cho chúng tôi.

368
00:15:25,940 --> 00:15:30,520
Và như vậy, chúng tôi Trie lớn dần và
lớn hơn, chúng tôi có làm việc ít hơn mỗi khi

369
00:15:30,520 --> 00:15:32,270
để chèn những điều mới
bởi vì chúng tôi đã đã

370
00:15:32,270 --> 00:15:35,746
xây dựng rất nhiều các trung gian
chi nhánh trên đường đi.

371
00:15:35,746 --> 00:15:38,370
Nếu chúng ta chỉ có bao giờ phải nhìn vào
4 điều, 4 chỉ là một hằng số.

372
00:15:38,370 --> 00:15:41,750
Chúng tôi thực sự được tiếp cận loại
chèn thời gian liên tục

373
00:15:41,750 --> 00:15:44,501
và tra cứu thời gian liên tục.

374
00:15:44,501 --> 00:15:47,500
Sự thỏa hiệp, dĩ nhiên, là rằng
Trie này, như bạn có thể cho biết,

375
00:15:47,500 --> 00:15:49,030
là rất lớn.

376
00:15:49,030 --> 00:15:51,040
Mỗi một trong các nút
chiếm rất nhiều không gian.

377
00:15:51,040 --> 00:15:52,090
>> Nhưng đó là sự đánh đổi.

378
00:15:52,090 --> 00:15:55,260
Nếu chúng ta muốn thực sự nhanh chóng
chèn, xóa thực sự nhanh chóng,

379
00:15:55,260 --> 00:15:59,630
và tra cứu thực sự nhanh chóng, chúng ta phải
có rất nhiều dữ liệu bay xung quanh.

380
00:15:59,630 --> 00:16:03,590
Chúng ta phải dành rất nhiều không gian
và bộ nhớ cho rằng cấu trúc dữ liệu

381
00:16:03,590 --> 00:16:04,290
tồn tại.

382
00:16:04,290 --> 00:16:05,415
>> Và đó là sự đánh đổi.

383
00:16:05,415 --> 00:16:07,310
Nhưng có vẻ như chúng tôi
có thể tìm thấy nó.

384
00:16:07,310 --> 00:16:09,560
Chúng ta có thể thấy rằng
Chén thánh của cấu trúc dữ liệu

385
00:16:09,560 --> 00:16:12,264
với chèn nhanh chóng,
xóa, và tra cứu.

386
00:16:12,264 --> 00:16:14,430
Và có lẽ đây sẽ là một
cấu trúc dữ liệu thích hợp

387
00:16:14,430 --> 00:16:18,890
để sử dụng cho bất cứ thông tin
chúng tôi đang cố gắng để lưu trữ.

388
00:16:18,890 --> 00:16:21,860
Tôi Doug Lloyd, đây là CS50.

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