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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Đôi khi, khi xây dựng một
chương trình, bạn có thể muốn sử dụng một

3
00:00:10,890 --> 00:00:13,190
cấu trúc dữ liệu được biết đến như một từ điển.

4
00:00:13,190 --> 00:00:17,960
Một bản đồ từ điển phím, trong đó có
dây thông thường, với các giá trị, số nguyên,

5
00:00:17,960 --> 00:00:21,900
ký tự, một con trỏ đến một số đối tượng,
bất cứ điều gì chúng ta muốn.

6
00:00:21,900 --> 00:00:26,510
Nó chỉ giống như từ điển thông thường
từ bản đồ thông qua các định nghĩa.

7
00:00:26,510 --> 00:00:29,440
>> Từ điển cung cấp cho chúng tôi với
khả năng lưu trữ thông tin

8
00:00:29,440 --> 00:00:32,750
kết hợp với một cái gì đó
và nhìn nó lên sau đó.

9
00:00:32,750 --> 00:00:36,620
Vì vậy, làm thế nào để chúng tôi thực sự thực hiện một
từ điển, nói, mã C mà chúng ta có thể

10
00:00:36,620 --> 00:00:38,460
sử dụng trong một chương trình của chúng tôi?

11
00:00:38,460 --> 00:00:41,790
Vâng, có rất nhiều cách mà
chúng ta có thể thực hiện một cuốn từ điển.

12
00:00:41,790 --> 00:00:45,930
>> Đối với một, chúng ta có thể sử dụng một mảng mà chúng ta
tự động chỉnh lại kích thước hoặc chúng ta có thể sử dụng một

13
00:00:45,930 --> 00:00:49,150
danh sách liên kết, bảng băm
hoặc một cây nhị phân.

14
00:00:49,150 --> 00:00:52,250
Nhưng bất cứ điều gì chúng ta lựa chọn, chúng ta nên
hãy chú ý đến hiệu quả và

15
00:00:52,250 --> 00:00:54,300
hiệu suất của việc thực hiện.

16
00:00:54,300 --> 00:00:57,930
Chúng ta nên suy nghĩ về các thuật toán sử dụng
để chèn và tìm kiếm các mục vào

17
00:00:57,930 --> 00:00:59,120
cấu trúc dữ liệu của chúng tôi.

18
00:00:59,120 --> 00:01:03,060
>> Bây giờ, chúng ta hãy giả sử chúng ta có
muốn sử dụng chuỗi như là chìa khóa.

19
00:01:03,060 --> 00:01:07,290
Hãy nói về một khả năng,
một cấu trúc dữ liệu gọi là một Trie.

20
00:01:07,290 --> 00:01:11,210
Vì vậy, đây là một hình ảnh đại diện
của một Trie.

21
00:01:11,210 --> 00:01:14,590
>> Như hình ảnh cho thấy, một Trie
là một cấu trúc dữ liệu cây với

22
00:01:14,590 --> 00:01:16,050
các nút liên kết với nhau.

23
00:01:16,050 --> 00:01:19,420
Chúng ta thấy rằng có rõ ràng là một gốc
nút với một số liên kết mở rộng để

24
00:01:19,420 --> 00:01:20,500
các nút khác.

25
00:01:20,500 --> 00:01:23,040
Nhưng những gì hiện mỗi nút bao gồm?

26
00:01:23,040 --> 00:01:26,700
Nếu chúng ta giả định rằng chúng ta giữ phím
bằng ký tự chữ cái, và

27
00:01:26,700 --> 00:01:30,150
chúng tôi không quan tâm về vốn,
đây là một định nghĩa của một nút

28
00:01:30,150 --> 00:01:31,100
sẽ đủ.

29
00:01:31,100 --> 00:01:34,130
>> Một đối tượng có kiểu là cấu trúc
nút có hai phần

30
00:01:34,130 --> 00:01:35,740
gọi là dữ liệu và trẻ em.

31
00:01:35,740 --> 00:01:39,200
Chúng tôi đã để lại một phần dữ liệu như một bình luận
được thay thế bằng một thành phần

32
00:01:39,200 --> 00:01:43,190
khai khi cấu trúc nút là
kết hợp trong một chương trình C.

33
00:01:43,190 --> 00:01:47,040
Một phần dữ liệu của một nút có thể là một
Giá trị boolean để cho biết hoặc

34
00:01:47,040 --> 00:01:51,160
không nút đại diện cho việc hoàn thành
của một phím từ điển hoặc nó có thể là một

35
00:01:51,160 --> 00:01:54,240
chuỗi đại diện cho định nghĩa
của một từ trong từ điển.

36
00:01:54,240 --> 00:01:58,870
>> Chúng tôi sẽ sử dụng một khuôn mặt cười để chỉ
khi dữ liệu được trình bày trong một nút.

37
00:01:58,870 --> 00:02:02,310
Có 26 yếu tố trong của chúng tôi
trẻ em mảng, một chỉ số

38
00:02:02,310 --> 00:02:03,690
mỗi ký tự chữ cái.

39
00:02:03,690 --> 00:02:06,570
Chúng ta sẽ thấy được tầm quan trọng
điều này sớm.

40
00:02:06,570 --> 00:02:10,759
>> Chúng ta hãy xem xét kỹ hơn các nút gốc
trong sơ đồ của chúng tôi, mà không có dữ liệu

41
00:02:10,759 --> 00:02:14,740
liên kết với nó, như được chỉ ra bởi các
trường hợp không có các khuôn mặt cười trong

42
00:02:14,740 --> 00:02:16,110
phần dữ liệu.

43
00:02:16,110 --> 00:02:19,910
Các mũi tên kéo dài từ các bộ phận của
mảng trẻ em đại diện cho không nút

44
00:02:19,910 --> 00:02:21,640
con trỏ đến các nút khác.

45
00:02:21,640 --> 00:02:25,500
Ví dụ, mũi tên kéo dài từ
yếu tố thứ hai của trẻ em

46
00:02:25,500 --> 00:02:28,400
đại diện cho chữ B
trong một khóa từ điển.

47
00:02:28,400 --> 00:02:31,920
Và trong sơ đồ lớn hơn
chúng ta gọi nó với một B.

48
00:02:31,920 --> 00:02:35,810
>> Lưu ý rằng trong sơ đồ lớn hơn, khi chúng ta
vẽ một con trỏ đến nút khác, nó

49
00:02:35,810 --> 00:02:39,100
không quan trọng nơi đầu mũi tên
hội tụ đủ các nút khác.

50
00:02:39,100 --> 00:02:43,850
Từ điển mẫu của chúng tôi Trie chứa
hai từ, đó và zoom.

51
00:02:43,850 --> 00:02:47,040
Chúng ta hãy đi bộ qua một ví dụ về
tìm kiếm dữ liệu cho một khóa.

52
00:02:47,040 --> 00:02:50,800
>> Giả sử chúng ta muốn tìm kiếm các
giá trị tương ứng cho phòng tắm chính.

53
00:02:50,800 --> 00:02:53,610
Chúng tôi sẽ bắt đầu nhìn chúng tôi lên
tại nút gốc.

54
00:02:53,610 --> 00:02:57,870
Sau đó chúng tôi sẽ lấy chữ cái đầu tiên của chúng tôi
chính, B, và tìm thấy những tương ứng

55
00:02:57,870 --> 00:03:00,020
phát hiện trong mảng con em chúng ta.

56
00:03:00,020 --> 00:03:04,490
Chú ý rằng có chính xác 26 điểm
trong mảng, một cho mỗi thư

57
00:03:04,490 --> 00:03:05,330
bảng chữ cái.

58
00:03:05,330 --> 00:03:08,800
Và chúng tôi sẽ có những điểm đại diện cho
chữ của bảng chữ cái theo thứ tự.

59
00:03:08,800 --> 00:03:13,960
>> Chúng tôi sẽ xem xét chỉ số thứ hai sau đó,
chỉ số một, cho B. Nói chung, nếu chúng ta

60
00:03:13,960 --> 00:03:17,990
có một số chữ cái ký tự C chúng tôi
có thể xác định vị trí tương ứng

61
00:03:17,990 --> 00:03:21,520
ở trẻ em mảng sử dụng
tính toán như thế này.

62
00:03:21,520 --> 00:03:25,140
Chúng ta có thể sử dụng cho trẻ em lớn hơn
mảng nếu chúng tôi muốn cung cấp cái nhìn lên của

63
00:03:25,140 --> 00:03:28,380
phím với một phạm vi rộng hơn của nhân vật,
như toàn bộ

64
00:03:28,380 --> 00:03:29,880
Ký tự ASCII thiết lập.

65
00:03:29,880 --> 00:03:32,630
>> Trong trường hợp này, con trỏ
ở trẻ em mảng của chúng tôi tại

66
00:03:32,630 --> 00:03:34,320
chỉ số một không phải là null.

67
00:03:34,320 --> 00:03:36,600
Vì vậy, chúng tôi sẽ tiếp tục tìm kiếm
lên phòng tắm chính.

68
00:03:36,600 --> 00:03:40,130
Nếu chúng ta từng gặp phải một con trỏ null
ở vị trí thích hợp ở trẻ em

69
00:03:40,130 --> 00:03:43,230
mảng trong khi chúng tôi đi qua các nút,
sau đó chúng tôi sẽ phải nói rằng chúng ta có

70
00:03:43,230 --> 00:03:45,630
không thể tìm thấy bất cứ điều gì cho khóa đó.

71
00:03:45,630 --> 00:03:49,370
>> Bây giờ, chúng ta sẽ lấy lá thư thứ hai của
chính của chúng tôi, A, và tiếp tục sau

72
00:03:49,370 --> 00:03:52,400
con trỏ theo cách này cho đến khi chúng tôi
đến cuối quan trọng của chúng tôi.

73
00:03:52,400 --> 00:03:56,530
Nếu chúng ta đạt được kết thúc của khóa mà không
đánh bất kỳ kết thúc chết, con trỏ null,

74
00:03:56,530 --> 00:03:59,730
như trường hợp ở đây, sau đó chúng tôi chỉ
phải kiểm tra một điều nữa.

75
00:03:59,730 --> 00:04:02,110
Là chìa khóa này thực sự
trong từ điển?

76
00:04:02,110 --> 00:04:07,660
>> Nếu như vậy, chúng ta nên tìm một giá trị, cũng một
biểu tượng mặt cười trong sơ đồ của chúng tôi nơi

77
00:04:07,660 --> 00:04:08,750
từ kết thúc.

78
00:04:08,750 --> 00:04:12,270
Nếu có cái gì đó khác với lưu trữ
dữ liệu, sau đó chúng tôi có thể trả lại.

79
00:04:12,270 --> 00:04:16,500
Ví dụ, sở thú quan trọng không phải là trong
từ điển, mặc dù chúng ta có thể có

80
00:04:16,500 --> 00:04:19,810
đến cuối khóa này mà không bao giờ
đánh một con trỏ null, trong khi chúng tôi

81
00:04:19,810 --> 00:04:21,089
lặp qua các Trie.

82
00:04:21,089 --> 00:04:25,436
>> Nếu chúng ta cố gắng tìm kiếm các phòng tắm khóa,
thứ hai để chỉ số mảng nút cuối cùng của,

83
00:04:25,436 --> 00:04:28,750
tương ứng với chữ cái H, sẽ
đã tổ chức một con trỏ null.

84
00:04:28,750 --> 00:04:31,120
Vì vậy, phòng tắm không có trong từ điển.

85
00:04:31,120 --> 00:04:34,800
Và do đó, một Trie độc ​​đáo ở chỗ các phím
không bao giờ được lưu trữ một cách rõ ràng trong

86
00:04:34,800 --> 00:04:36,650
cấu trúc dữ liệu.

87
00:04:36,650 --> 00:04:38,810
Vì vậy, làm thế nào để chúng ta chèn một cái gì đó
vào một Trie?

88
00:04:38,810 --> 00:04:41,780
>> Chúng ta hãy chèn phím
sở thú vào Trie của chúng tôi.

89
00:04:41,780 --> 00:04:46,120
Hãy nhớ rằng một khuôn mặt cười tại một nút
có thể tương ứng trong mã để đơn giản

90
00:04:46,120 --> 00:04:50,170
Giá trị boolean để chỉ ra rằng vườn thú
có trong từ điển hoặc nó có thể

91
00:04:50,170 --> 00:04:53,710
tương ứng với thêm thông tin mà chúng tôi
muốn liên kết với các sở thú chính,

92
00:04:53,710 --> 00:04:56,860
như định nghĩa của
từ hay cái gì khác.

93
00:04:56,860 --> 00:05:00,350
Trong một số cách, quá trình này để chèn
một cái gì đó vào một Trie tương tự như

94
00:05:00,350 --> 00:05:02,060
tìm kiếm một cái gì đó trong một Trie.

95
00:05:02,060 --> 00:05:05,720
>> Chúng tôi sẽ bắt đầu với nút gốc một lần nữa,
con trỏ sau tương ứng với

96
00:05:05,720 --> 00:05:07,990
các chữ cái của chính chúng tôi.

97
00:05:07,990 --> 00:05:11,310
May mắn thay, chúng tôi có thể theo dõi con trỏ
tất cả các cách cho đến khi chúng tôi đến

98
00:05:11,310 --> 00:05:12,770
cuối khóa.

99
00:05:12,770 --> 00:05:16,480
Từ sở thú là một tiền tố của từ
zoom, mà là một thành viên của

100
00:05:16,480 --> 00:05:19,440
từ điển, chúng ta không cần phải
phân bổ các nút mới.

101
00:05:19,440 --> 00:05:23,140
>> Chúng ta có thể sửa đổi các nút để chỉ ra rằng
con đường của các nhân vật dẫn đến

102
00:05:23,140 --> 00:05:25,360
nó đại diện cho một chìa khóa trong từ điển của chúng tôi.

103
00:05:25,360 --> 00:05:28,630
Bây giờ, hãy thử chèn
BATH chìa khóa vào Trie.

104
00:05:28,630 --> 00:05:32,260
Chúng tôi sẽ bắt đầu tại nút gốc
và theo con trỏ một lần nữa.

105
00:05:32,260 --> 00:05:35,620
Nhưng trong tình huống này, chúng ta đánh một người chết
kết thúc trước khi chúng tôi có thể đến được với các

106
00:05:35,620 --> 00:05:36,940
cuối khoá.

107
00:05:36,940 --> 00:05:40,980
Bây giờ, chúng tôi sẽ cần phải phân bổ một số mới
các nút sẽ cần phải phân bổ một mới

108
00:05:40,980 --> 00:05:43,660
nút cho mỗi còn lại
thư của chính chúng tôi.

109
00:05:43,660 --> 00:05:46,740
>> Trong trường hợp này, chúng ta chỉ cần
để phân bổ một nút mới.

110
00:05:46,740 --> 00:05:50,590
Sau đó chúng tôi sẽ cần phải thực hiện các chỉ số H
tham khảo nút mới này.

111
00:05:50,590 --> 00:05:54,070
Một lần nữa, chúng ta có thể sửa đổi các nút để
chỉ ra rằng con đường của ký tự

112
00:05:54,070 --> 00:05:57,120
dẫn đến nó đại diện cho một
quan trọng trong từ điển của chúng tôi.

113
00:05:57,120 --> 00:06:00,730
Chúng ta hãy suy luận về các tiệm cận
phức tạp của thủ tục của chúng tôi cho các

114
00:06:00,730 --> 00:06:02,110
hai hoạt động.

115
00:06:02,110 --> 00:06:06,420
>> Chúng tôi nhận thấy rằng trong cả hai trường hợp số
của các bước thuật toán của chúng tôi đã được

116
00:06:06,420 --> 00:06:09,470
tỷ lệ thuận với số lượng
ký tự trong từ khóa.

117
00:06:09,470 --> 00:06:10,220
Đó là đúng.

118
00:06:10,220 --> 00:06:13,470
Khi bạn muốn tìm một từ trong một
Trie bạn chỉ cần lặp qua

119
00:06:13,470 --> 00:06:17,100
các chữ cái một cho đến khi bạn có
đến cuối của từ hoặc

120
00:06:17,100 --> 00:06:19,060
nhấn một kết thúc chết trong Trie.

121
00:06:19,060 --> 00:06:22,470
>> Và khi bạn muốn chèn một phím
cặp giá trị vào một Trie sử dụng

122
00:06:22,470 --> 00:06:26,250
thủ tục, chúng tôi đã thảo luận, trường hợp xấu nhất
sẽ có bạn bố trí một nút mới

123
00:06:26,250 --> 00:06:27,550
cho mỗi thư.

124
00:06:27,550 --> 00:06:31,290
Và chúng tôi sẽ giả định rằng phân bổ
là một thời gian hoạt động liên tục.

125
00:06:31,290 --> 00:06:35,850
Vì vậy, nếu chúng ta giả định rằng chiều dài chính là
bao quanh bởi một hằng số cố định, cả hai

126
00:06:35,850 --> 00:06:39,400
chèn và tìm kiếm là không đổi
hoạt động thời gian cho một Trie.

127
00:06:39,400 --> 00:06:42,930
>> Nếu chúng ta không làm cho giả định này
độ dài khoá được bao quanh bởi một cố định

128
00:06:42,930 --> 00:06:46,650
liên tục, sau đó chèn và nhìn lên,
trong trường hợp xấu nhất, được tuyến tính trong

129
00:06:46,650 --> 00:06:48,240
độ dài của khoá.

130
00:06:48,240 --> 00:06:51,800
Nhận thấy rằng số lượng các mặt hàng được lưu trữ
trong Trie không ảnh hưởng đến cái nhìn lên

131
00:06:51,800 --> 00:06:52,820
hoặc thời điểm chèn.

132
00:06:52,820 --> 00:06:55,360
Nó chỉ ảnh hưởng bởi
độ dài của khoá.

133
00:06:55,360 --> 00:06:59,300
>> Ngược lại, thêm các mục vào, nói,
một bảng băm có xu hướng làm

134
00:06:59,300 --> 00:07:01,250
tương lai nhìn lên chậm hơn.

135
00:07:01,250 --> 00:07:04,520
Trong khi điều này nghe có vẻ hấp dẫn lúc đầu,
chúng ta nên ghi nhớ rằng một

136
00:07:04,520 --> 00:07:08,740
phức tạp tiệm cận thuận lợi không
có nghĩa là trong thực tế dữ liệu

137
00:07:08,740 --> 00:07:11,410
cấu trúc nhất thiết phải
ngoài sỉ nhục.

138
00:07:11,410 --> 00:07:15,860
Chúng ta cũng phải xem xét để lưu trữ một
từ trong một Trie chúng ta cần, trong điều tồi tệ nhất

139
00:07:15,860 --> 00:07:19,700
trường hợp, một số nút tương ứng
với chiều dài của từ chính nó.

140
00:07:19,700 --> 00:07:21,880
>> Cố gắng có xu hướng sử dụng rất nhiều không gian.

141
00:07:21,880 --> 00:07:25,620
Đó là trái ngược với một bảng băm,
nơi chúng tôi chỉ cần một nút mới vào

142
00:07:25,620 --> 00:07:27,940
lưu trữ một số cặp giá trị quan trọng.

143
00:07:27,940 --> 00:07:31,370
Bây giờ, một lần nữa trong lý thuyết, không gian lớn
tiêu thụ không có vẻ như một lớn

144
00:07:31,370 --> 00:07:34,620
đối phó, nhất là hiện đại
máy tính có gigabyte và

145
00:07:34,620 --> 00:07:36,180
GB bộ nhớ.

146
00:07:36,180 --> 00:07:39,200
Nhưng nó quay ra rằng chúng ta vẫn còn
phải lo lắng về việc sử dụng bộ nhớ và

147
00:07:39,200 --> 00:07:42,540
tổ chức vì lợi ích của
hiệu suất, kể từ khi máy tính hiện đại

148
00:07:42,540 --> 00:07:46,960
có cơ chế tại chỗ dưới
mui xe để tăng tốc độ truy cập bộ nhớ.

149
00:07:46,960 --> 00:07:51,180
>> Nhưng các cơ chế làm việc hiệu quả nhất khi
truy cập bộ nhớ được thực hiện trong nhỏ gọn

150
00:07:51,180 --> 00:07:52,810
khu vực hoặc khu vực.

151
00:07:52,810 --> 00:07:55,910
Và các nút của một Trie có thể cư trú
bất cứ nơi nào trong đống đó.

152
00:07:55,910 --> 00:07:58,390
Nhưng đây là những đánh đổi
rằng chúng ta phải xem xét.

153
00:07:58,390 --> 00:08:01,440
>> Hãy nhớ rằng, khi lựa chọn một dữ liệu
cấu trúc cho một công việc nào đó, chúng tôi

154
00:08:01,440 --> 00:08:04,420
nên suy nghĩ về những gì các loại
hoạt động của cấu trúc dữ liệu cần

155
00:08:04,420 --> 00:08:07,140
hỗ trợ và bao nhiêu hiệu suất
của mỗi người

156
00:08:07,140 --> 00:08:09,080
hoạt động các vấn đề với chúng tôi.

157
00:08:09,080 --> 00:08:11,300
Các hoạt động này thậm chí có thể
mở rộng ra ngoài chỉ

158
00:08:11,300 --> 00:08:13,430
cơ bản nhìn lên và chèn.

159
00:08:13,430 --> 00:08:17,010
Giả sử chúng ta muốn thực hiện một loại
chức năng tự động hoàn tất, nhiều

160
00:08:17,010 --> 00:08:18,890
như công cụ tìm kiếm Google.

161
00:08:18,890 --> 00:08:22,210
Có nghĩa là, trả lại tất cả các phím và
có khả năng giá trị mà

162
00:08:22,210 --> 00:08:24,130
có một tiền tố nhất định.

163
00:08:24,130 --> 00:08:27,050
>> Một Trie là duy nhất hữu ích
cho hoạt động này.

164
00:08:27,050 --> 00:08:29,890
Nó đơn giản để lặp qua
các Trie cho mỗi nhân vật của

165
00:08:29,890 --> 00:08:30,950
tiền tố.

166
00:08:30,950 --> 00:08:33,559
Cũng giống như một cái nhìn lên hoạt động,
chúng ta có thể theo con trỏ

167
00:08:33,559 --> 00:08:35,400
nhân vật của nhân vật.

168
00:08:35,400 --> 00:08:38,659
Sau đó, khi chúng tôi đến cuối
tiền tố, chúng ta có thể lặp qua

169
00:08:38,659 --> 00:08:42,049
phần còn lại của cấu trúc dữ liệu
từ bất kỳ của các phím ngoài

170
00:08:42,049 --> 00:08:43,980
thời điểm này có tiền tố.

171
00:08:43,980 --> 00:08:47,670
>> Nó cũng dễ dàng để có được bảng liệt kê này
trong thứ tự chữ cái từ

172
00:08:47,670 --> 00:08:50,970
các yếu tố của mảng trẻ em
được sắp xếp theo thứ tự abc.

173
00:08:50,970 --> 00:08:54,420
Vì vậy, hy vọng bạn sẽ xem xét
hiến cố gắng thử.

174
00:08:54,420 --> 00:08:56,085
Tôi Kevin Schmid, và đây là CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, đây là sự khởi đầu
của sự suy giảm.

177
00:09:00,790 --> 00:09:01,350
Tôi xin lỗi.

178
00:09:01,350 --> 00:09:01,870
Xin lôi.

179
00:09:01,870 --> 00:09:02,480
Xin lôi.

180
00:09:02,480 --> 00:09:03,130
Xin lôi.

181
00:09:03,130 --> 00:09:03,950
>> Tấn công bốn.

182
00:09:03,950 --> 00:09:04,360
Tôi ra.

183
00:09:04,360 --> 00:09:05,280
Xin lôi.

184
00:09:05,280 --> 00:09:06,500
Xin lôi.

185
00:09:06,500 --> 00:09:07,490
Xin lôi.

186
00:09:07,490 --> 00:09:12,352
Xin lỗi vì làm cho người người
có chỉnh sửa này điên.

187
00:09:12,352 --> 00:09:13,280
>> Xin lôi.

188
00:09:13,280 --> 00:09:13,880
Xin lôi.

189
00:09:13,880 --> 00:09:15,080
Xin lôi.

190
00:09:15,080 --> 00:09:15,680
Xin lôi.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Tốt lắm.

192
00:09:16,280 --> 00:09:17,530
Đã được thực sự thực hiện tốt.

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