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 LLOYD: ดังนั้นเราได้รับอีกนิดใกล้ชิด
และใกล้ชิดที่ศักดิ์สิทธิ์ grail ของข้อมูล

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
ที่ hashes เพื่อ hashcode ที่

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
ซึ่งแตกต่างจากตารางแฮชที่เราจะทำได้
จบลงด้วยสองชิ้นของข้อมูล

30
00:01:25,410 --> 00:01:27,200
มี hashcode เดียวกัน

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
ทราบว่าข้อมูลที่
ที่มีอยู่ในของ Trie

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
และเพื่อให้เราจะใช้บรรดาสี่ตัวเลขไป
นำทางผ่านโครงสร้างข้อมูลนี้

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
ของมหาวิทยาลัยที่สอดคล้อง
การที่สำคัญที่ผู้ที่ตัวเลขสี่หลัก

71
00:03:30,250 --> 00:03:34,390
ความคิดพื้นฐานหลัง Trie
คือเรามีเส้นทางภาคกลาง

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
และโดยทั่วไปความคิดของ
Trie คือตรงเดียวกัน

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
ถ้าเราต้องการที่จะแทรกองค์ประกอบ
เข้า Trie ทั้งหมดที่เราต้องทำ

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
เรากำลังจะไปกำหนดข้อมูลใหม่
โครงสร้างโหนดใหม่ที่เรียกว่า Trie

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
ดังนั้นขอสร้าง Trie

116
00:05:41,060 --> 00:05:44,860
ลองใส่คู่
ของรายการลงใน Trie ของเรา

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 ตัวเองโหนด Trie

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
ซึ่งเป็นตัวอย่างที่ผม
ใช้ในหลายวิดีโอของฉัน

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 โหนดใน Trie นี้

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
ลองใส่มหาวิทยาลัย
ฮาร์วาร์เข้า Trie นี้ซึ่ง

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
จะเก็บในฮาร์วาร์ของ Trie

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
รากก็เหมือนกับการใด ๆ
โหนดอื่น ๆ ของ Trie

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
ดังนั้นถ้าผมต้องการที่จะแทรก
ฮาร์วาร์เข้า Trie นี้

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 เส้นทางขณะนี้เป็นโมฆะ

163
00:07:31,810 --> 00:07:35,920
ดังนั้นถ้าผมต้องการที่จะดำเนินการต่อไปตามเส้นทางที่
ที่จะแทรกเข้าไปในองค์ประกอบนี้ Trie ที่

164
00:07:35,920 --> 00:07:42,040
ฉันต้อง malloc โหนดใหม่มี 1
ชี้มีแล้วฉันดีไป

165
00:07:42,040 --> 00:07:46,460
>> ดังนั้นผมจึงรู้สึกโดยทั่วไปที่
จุดที่ฉันยืนอยู่

166
00:07:46,460 --> 00:07:50,270
ที่รากของต้นไม้หรือที่
Trie และมี 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 ไม่ได้ชี้ให้เป็นโมฆะ

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
ดังนั้นตอนนี้ผมเคยใช้ที่สำคัญของฉันที่จะแทรกสร้าง
โหนดและเริ่มสร้าง Trie นี้

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
นั่นคือสิ่งที่ฉันกำลัง am

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
เพื่อที่จุดนี้ทั้งหมดที่ฉัน
จริงๆต้องทำคือการพูดว่าตกลง

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
ลองใส่เยลเข้า Trie นี้

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
>> และดังนั้นตอนนี้ถ้าผมจำเป็นต้องดูว่าเยล
ที่อยู่ใน Trie นี้ผมเริ่มต้นที่ราก

263
00:11:24,660 --> 00:11:27,060
ผมลงไป 1,701 และมองลงมา

264
00:11:27,060 --> 00:11:30,030
และถ้าผมเห็นสเปรย์เยล
วาดลงบนพื้นดินแล้ว

265
00:11:30,030 --> 00:11:32,200
ฉันรู้ว่ามีอยู่ในเยล Trie นี้

266
00:11:32,200 --> 00:11:32,950
ขอทำอีกครั้งหนึ่ง

267
00:11:32,950 --> 00:11:36,430
ลองใส่ดาร์ทเมาท์ในนี้
Trie ซึ่งก่อตั้งขึ้นในปี 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
จากที่นี่จากที่ฉันกำลัง am
สีเหลืองที่มีในโหนดกลาง

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
และฉันได้ใส่
ดาร์ทเมาท์เข้าของ Trie

286
00:12:20,710 --> 00:12:23,450
>> ดังนั้นที่ใส่
สิ่งที่เป็นของ Trie

287
00:12:23,450 --> 00:12:25,384
ตอนนี้เราต้องการที่จะค้นหาสิ่งที่

288
00:12:25,384 --> 00:12:27,050
เราจะค้นหาวิธีสำหรับสิ่งที่อยู่ใน Trie หรือไม่

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
การที่เราต้องการที่จะไปในของ Trie

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
>> ถ้าอย่างนั้นเราค้นหา
ฮาร์วาร์ใน Trie นี้

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
เราต้องดูและลง
ดูว่าที่ actually--

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
เกิดอะไรขึ้นถ้าสิ่งที่ฉันกำลังมองหา
ไม่ได้อยู่ใน Trie แม้ว่า

336
00:14:13,980 --> 00:14:17,200
เกิดอะไรขึ้นถ้าฉันกำลังมองหาพรินซ์ตัน
ซึ่งก่อตั้งขึ้นใน 1746

337
00:14:17,200 --> 00:14:20,875
และเพื่อ 1746 จะกลายเป็นกุญแจสำคัญของฉัน
เพื่อนำทางผ่านของ Trie

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
หากพรินซ์ตันอยู่ใน Trie นี้ว่า 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
พรินซ์ตันไม่อยู่ใน Trie นี้

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
แต่แจ้งให้ทราบทุกครั้งที่เราอยากจะทุกคน
ตรวจสอบว่าสิ่งที่อยู่ใน Trie ที่

363
00:15:13,480 --> 00:15:15,000
เราจะต้องทำให้การเคลื่อนไหว 4

364
00:15:15,000 --> 00:15:17,208
>> เวลาที่เราทุกคนต้องการที่จะ
ใส่อะไรบางอย่างใน Trie ที่

365
00:15:17,208 --> 00:15:20,440
เราจะต้องทำให้การเคลื่อนไหว 4 อาจจะเป็น
mallocing สิ่งบางอย่างไปพร้อมกัน

366
00:15:20,440 --> 00:15:23,482
แต่ที่เราเห็นเมื่อเราใส่
ดาร์ทเมาท์เข้า Trie ที่

367
00:15:23,482 --> 00:15:25,940
บางครั้งบางส่วนของเส้นทาง
แล้วอาจจะมีการเคลียร์สำหรับเรา

368
00:15:25,940 --> 00:15:30,520
และเพื่อให้เป็น Trie ของเราได้รับที่ใหญ่กว่าและ
ใหญ่กว่าที่เรามีจะทำงานน้อยลงทุกครั้ง

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
ถ่วงดุลอำนาจของหลักสูตรการที่
Trie นี้ที่คุณอาจจะสามารถบอกได้

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