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
דאג LLOYD: אז אנחנו כבר התקדמו קרובים
יותר ויותר שגביע קדוש של נתונים

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
אז המפתח הוא קוד Hash של נתונים.

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
יודע אם הנתונים ש
קיים באיירי.

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
הרעיון הבסיסי מאחורי איירי
הוא שיש לנו מסלול מרכזי.

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
אתה מגדיר מצביע אחר
שווה לשורש, כגון טראב,

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
>> אתה מגדיר את מצביע אחר
נקרא טראב לחצייה.

128
00:06:13,320 --> 00:06:15,890
ואתה משתמש טראב לנווט
באמצעות מבנה נתונים.

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
נוסד בשנת 1,636.

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
>> איפה אנחנו כנראה רוצים
ללכת אם המפתח הוא 1,636?

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
אני חייב malloc צומת חדשה, יש לי 1
להצביע שם, ואז אני טוב ללכת.

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
אני כבר ירדתי 1,636.

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
לכן בשלב זה, כל מה שאני
באמת צריך לעשות הוא לומר, על אישור.

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
אני פיניתי אותו בעבר כש
היה החדרת הרווארד ב1,636.

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
בואו להכניס Dartmouth לזה
איירי, שנוסדה בשנת 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
אני יכול לכתוב Dartmouth.

285
00:12:16,930 --> 00:12:20,710
ואני כבר הוכנס
Dartmouth לאיירי.

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
ובכן, אני מסתכל למטה לאחר שהחלתי
בראש והולכים 1,636.

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
וכך הופך 1,746 המפתח שלי
כדי לנווט את איירי.

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
אבל כפי שראינו כאשר אנו מוכנסים
Dartmouth לאיירי,

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