[השמעת מוסיקה] דאג LLOYD: אז אנחנו כבר התקדמו קרובים יותר ויותר שגביע קדוש של נתונים מבנים, אחד שאנחנו יכולים להכניס ל, למחוק מ, ולהסתכל למעלה בזמן קבוע. תקין. זה סוג של המטרה. אנחנו רוצים להיות מסוגלים לעשות דברים מאוד, מאוד מהר. 

יש לנו מצאנו את זה כאן כש על ניסיונות אנחנו מדברים? ובכן, בואו נסתכל. אז ראינו כמה מבני נתונים שונים שתטפל במיפוי של מה שנקרא זוגות מפתח-ערך, מיפוי כמה פיסת המידע לכמה פיסת מידע אחרת כך שאנחנו יודעים איפה למצוא מידע במבנה. 

אז למערך, למשל, מפתח הוא מדד האלמנט או מערך מיקום 0 או 1 מערך וכן הלאה. והערך הוא נתונים שקיים במיקום זה. אז מה מאוחסן במערך 0? מה מאוחסן במערך 1 לעומת רק 0 ו -1, אשר יהיו המפתחות. 

עם שולחן חשיש זה סוג של אותו הרעיון. עם שולחן חשיש, יש לנו חשיש זה פונקציה שיוצרת קודי חשיש. אז המפתח הוא קוד Hash של נתונים. והערך, במיוחד דיברנו על שרשור בוידאו על שולחנות חשיש, היא שהרשימה המקושרת של נתונים שhashes לhashcode ש. תקין. מה לגבי גישה אחרת בשיטה זו, אם כי? מה לגבי שיטה שבי המפתח מובטח להיות ייחודי, בניגוד לשולחן חשיש, שבו אנחנו יכולים בסופו של עם שתי חתיכות של נתונים נתקל באותה hashcode. ואז אנחנו צריכים להתמודד עם כי גם על ידי חיטוט או יותר רצוי שרשור לתקן את הבעיה. 

אז עכשיו אנחנו יכולים להבטיח שהמפתח שלנו יהיה ייחודי. ומה אם היה הערך שלנו רק משהו קל כאמת ושקר שאומר לנו אם או לא כי פיסת מידע קיים במבנה? בוליאני יכול להיות פשוט כמו קצת. באופן מעשי זה כנראה בית אחד יותר סביר מאשר קצת. אבל זה הרבה יותר קטן אחסון אולי מחרוזת 50 תווים, לדוגמה. 

אז מנסה, בדומה לחשיש שולחנות, המשלב מערכים ורשימה מקושרים, מנסה לשלב מערכים, מבנים, ומצביעים יחד כדי לאחסן נתונים ב דרך מעניינת זה די שונה מ כל מה שראינו עד כה. עכשיו אנו משתמשים בנתונים כמפת דרכים כדי לנווט מבנה נתונים זה. ואם אנחנו יכולים לעקוב אחרי מפת הדרכים, אם אנחנו לא יכולים בצע את הנתונים מ התחלה ועד הסוף, אנחנו יודע אם הנתונים ש קיים באיירי. 

ואם אנחנו לא יכולים לעקוב אחר המפה מכלומר לסיים בכל, הנתונים אינם יכולים להתקיים. שוב, את המפתחות כאן הם מובטח להיות ייחודי. וכך בניגוד לשולחן חשיש, שלעולם לא צריך להתמודד עם התנגשויות כאן. ואין שתי חתיכות של נתונים יש בדיוק את אותו מפת הדרכים אלא אם כן נתונים זהים. 

אם להכניס ג'ון, אז אנו מחפשים ג'ון. זה שני חלקים זהים של הנתונים, נכון, אנחנו מחפשים דרך. אבל חוץ מזה, כל שתי פיסות מידע הן מובטח לי מפות דרכים ייחודיות באמצעות מבנה נתונים זה. ואנחנו הולכים להעיף מבט על חזותי של זה ברגע. 

אנחנו נעשה את זה בניסיון ליצור מבנה נתונים חדש, מיפוי זוגות ערך המפתח הבא. במקרה זה, אנחנו לא מתכוונים להשתמש משהו פשוט כמו בוליאנית. אנחנו בעצם יהיו לאחסן את המחרוזת. ומחרוזת כי הוא הולכת להיות השם של אוניברסיטה. 

והמפתח הולך להיות השנה כאשר האוניברסיטה שנוסדה. כל השנים לאוניברסיטאות הולך להיות ארבע ספרות. ולכן אנו נשתמש ארבע ספרות אלה ל לנווט מבנה נתונים זה. ואנו רואים, שוב, איך אנחנו עושים את זה רק שני. 

בסוף הדרך, אנחנו תראו את השם של האוניברסיטה המתאימה למפתח ש, ארבע ספרות אלה. הרעיון הבסיסי מאחורי איירי הוא שיש לנו מסלול מרכזי. אז תחשוב על זה כמו עץ. וזה דומה בכתיב ובמושג לעץ. בדרך כלל כאשר אנו חושבים על עצים בעולם האמיתי, יש להם שורש זה ב קרקע והם גדלים כלפי מעלה ויש להם סניפים ויש להם עלים. ובעצם הרעיון של איירי היא בדיוק אותו הדבר, מלבד השורש שמעוגן אי שם בשמים. והעלים בחלק התחתון. 

אז זה סוג של כמו לקחת עץ ורק רפרפו במהופך. אבל עדיין יש סניפים. ואלה יהיו המסלולים שלנו, אלה יהיו הקשרים שלנו מהשורש לעלים. במקרה זה, אלה שבילים, ענפים אלה מסומנים בספרות שאומרות לנו באיזו דרך ללכת מהמקום שבו אנו נמצאים. 

אם אנו רואים 0, אנחנו יורדים ענף זה, אם אנו רואים 1, אנחנו יורדים ענף זה, וכך וכן הלאה. ובכן, מה זה אומר? ובכן, זה אומר ש בכל נקודת צומת וכל צומת ב אמצע וכל סניף, יש 10 אפשריים מקומות שאנחנו יכולים ללכת. אז יש 10 מצביעים מכל מקום. 

וזה המקום שבו מנסה יכול לקבל קצת מפחיד למישהו מי לא צריכה הרבה ניסיון במדעי מחשב לפני. אבל מנסה באמת די מדהים. ואם יש לך הזדמנות לעבוד איתם ואתה מוכן לחפור-ב ולהתנסות איתם, הם באמת די מעניינים מבני נתונים לעבוד איתו. אם אנחנו רוצים להכניס אלמנט לאיירי, כל מה שאנחנו צריכים לעשות הוא לבנות את הנתיב הנכון מהשורש לעלה. הנה מה שכל צעד לאורך הדרך עשויה להיראות. אנחנו הולכים להגדיר נתונים חדשים מבנה לצומת חדשה בשם איירי. 

ובתוך הנתונים ש מבנה יש שתי חתיכות. אנחנו הולכים לאחסון שמו של אוניברסיטה. ואנחנו הולכים לאחסון מערך של מצביעים לצמתים אחרים מאותו הסוג. אז, שוב, זה סוג ש של מושג בכל מקום אנחנו, אנחנו ב 10 אפשריים מקומות שאנחנו יכולים ללכת. אם אנו רואים 0, אנחנו יורדים ענף זה. אם אנו רואים 1, ענף זה, וכן הלאה וכן הלאה וכן הלאה. אם אנחנו אומרים 9, אנחנו יורדים ענף זה. אז בכל נקודת צומת, אנחנו יכולים ללכת 10 מקומות אפשריים. אז כל צומת יש להכיל 10 מצביעים לצמתים אחרים, עד 10 צמתים אחרים. 

ונתונים שאנחנו אחסון הוא רק את השם של האוניברסיטה. אז בואו לבנות את איירי. בואו להכניס זוג של פריטים לאיירי. אז בחלקו העליון, זה צומת השורש שלנו. זה כנראה הולך להיות משהו אתה הולך בעולם להכריז. ואתה הולך בעולם לשמור על מצביע לצומת זה תמיד. 

אתה הולך להגיד, שורש שווה, ואתה הולך malloc עצמך צומת איירי. ואתה אף פעם לא הולך לגעת שורש שוב. בכל פעם שאתה רוצה להתחיל לנווט, אתה מגדיר מצביע אחר שווה לשורש, כגון טראב, אשר אני הדוגמא להשתמש בהרבה של קטעי הווידאו שלי כאן בערימות ותורים ורשימות קישור וכן הלאה. 

אתה מגדיר את מצביע אחר נקרא טראב לחצייה. ואתה משתמש טראב לנווט באמצעות מבנה נתונים. אז בואו לראות איך זה עשוי להיראות. אז עכשיו, מה ש אין צומת נראית? ובכן, בדיוק כמו הנתונים שלנו הכרזת מבנה מצויינים, יש לנו מחרוזת, ש במקרה זה הוא ריק. אין כאן שום דבר. 

ומערך של 10 מצביעים. ועכשיו, אנחנו רק יש לי צומת 1 באיירי זה. אין שום דבר אחר בזה. אז כל 10 של אלה מצביעי הצבע על null. זה מה שמצביע אדום. 

בואו נכניס את המחרוזת הרווארד. בואו נכניס את האוניברסיטה הרווארד לאיירי זה, ש נוסד בשנת 1,636. אנחנו רוצים להשתמש במפתח, 1636, כדי לספר לנו איפה אנחנו הולך לחנות הרווארד באיירי. עכשיו, איך ייתכן שאנחנו עושים את זה? 

זה אולי נראה משהו כזה. אנחנו מתחילים בשורש. ויש לנו 10 המקומות האלה אנחנו יכולים ללכת. השורש הוא בדיוק כמו כל צומת אחרת של איירי. ישנם 10 מקומות שאנחנו יכולים ללכת מכאן. 

איפה אנחנו כנראה רוצים ללכת אם המפתח הוא 1,636? יש באמת שתי אפשרויות. תקין. אנחנו יכולים לבנות את המפתח מ מימין לשמאל ולהתחיל עם 6. או שאנחנו יכולים לבנות את המפתח מ משמאל לימין ומתחיל עם 1. 

זה כנראה יותר אינטואיטיבי כבן אדם להבין אנחנו רק הולכים משמאל לימין. ולכן אם אני רוצה להכניס הרווארד לאיירי זה, אני כנראה רוצה להתחיל על ידי הפעלה בשורש, מסתכל על 10 האפשרויות שלי מולי, ואומר אני רוצה ללכת במורד השביל 1. אוקיי. 

עכשיו, הדרך 1 היא null כיום. אז אם אני רוצה להמשיך את הדרך ש להכניס את האלמנט הזה לאיירי, אני חייב malloc צומת חדשה, יש לי 1 להצביע שם, ואז אני טוב ללכת. 

אז אני בעצם אני ב שבו נקודה שאני עומד בשורש של העץ או איירי ויש 10 סניפים. אבל יש כל ענף שער מול זה. תקין. כי אין דבר אחר שיש. אין מעבר בטוח. זה אומר שאין שום דבר את כל סניפים אלה. אם אני רוצה להתחיל בניין משהו, אני רוצה להסיר את השער. אני רוצה להסיר את השער מול מספר 1. ואני רוצה ללכת במורד ש. ואני רוצה לבנות מקום אחר בשבילי ללכת. 

וזה מה שעשיתי כאן. אז 1 כבר לא מצביע על null. אני כבר אמרתי שהוא בטוח לרדת כאן עכשיו. אני בניתי צומת אחר. וכשאני מגיע לצומת ש, אני יש החלטה אחרת לעשות. לאן אני הולך מכאן? 

ובכן, אני כבר ירדתי 1. אז עכשיו אני כנראה רוצה לרדת 6. תקין. שוב, יש לי 10 מקומות שאני יכול לבחור. אז בואו עכשיו נלך את מספר 6. אז לנקות את השער מול מספר 6. ואני הולך לשם. ואני בונה צומת אחר. ואני כבר הגעתי לנקודת צומת אחרת. 

שוב, יש לי 10 בחירות לשם אני יכול ללכת. אני כבר עברתי 1-6. אז עכשיו כנראה אני רוצה ללכת עד 3. 3, אין לאן אני יכול ללכת. אז אני צריך לפנות את הדרך ולבנות את עצמי חלל חדש. ולאחר מכן מ3, שבו אני רוצה ללכת? אני רוצה לרדת 6. 

ושוב, לא היה לי ל לנקות את הדרך לעשות את זה. אז עכשיו אני השתמשתי המפתח שלי להכניס ליצור צמתים ולהתחיל לבנות את איירי זה. אני כבר התחלתי בשורש. אני כבר ירדתי 1,636. ועכשיו אני בחלק התחתון יש בצומת ש. וייתכן שתוכל ל רואה את זה על המסך שלך. 

זה מודגש בצהוב. זה המקום שבי אני כרגע. המפתח שלי נעשה. אחרי שמיציתי כל עמדה במפתח שלי. אז אני לא יכול ללכת יותר. לכן בשלב זה, כל מה שאני באמת צריך לעשות הוא לומר, על אישור. זה כמו סוג של מחפש למטה בקרקע, אם אתה מדמיין את עצמך כסוג של דרך עם חיבורים שונים. סוג של מסתכל למטה וסוג של לרסס ציור הרווארד על הקרקע. זה השם של זה. יודע שזה מה שבמיקום זה. אם אנחנו מתחילים בשורש ואנחנו יורדים 1 ולאחר מכן 6 ולאחר מכן 3 ולאחר מכן 6, איפה אנחנו? ובכן, אם אנחנו מסתכלים למטה ואנו רואים בהרווארד, ולאחר מכן אנו יודעים כי הרווארד היה נוסד בשנת 1636 המבוססים על הדרך אנחנו יישום מבנה נתונים זה. אז זה היה בתקווה פשוטה. אנחנו הולכים לעשות שתי הוספות יותר. ואני מקווה שזה יעזור ל רואה את זה עשה עוד פעמיים. 

עכשיו, בואו נכניס אוניברסיטה אחרת. בואו להכניס ייל לאיירי זה. ייל נוסד בשנת 1701. אז נתחיל ב שורש, כמו תמיד אנחנו עושים. ואנו קובעים מצביע חציה. אנחנו הולכים להשתמש בזה כדי לעבור. הדבר הראשון שאנחנו רוצים לעשות זה ללכת במורד השביל 1. זה הספרה הראשונה של המפתח שלנו. למרבה המזל, אם כי, אנחנו לא צריך לעשות את כל עבודה זה זמן. הנתיב 1 כבר נוקה. אני פיניתי אותו בעבר כש היה החדרת הרווארד ב1,636. אז אני יכול לעבור בשלום מטה 1 ורק ללכת לשם. אם ניתן להעביר את 1. 

עכשיו, אם כי, אני רוצה ללכת ל7. אני פיניתי את הדרך בשעת 6. אני יודע בבטחה שאני יכול להמשיך במורד השביל 6. אבל אני צריך להמשיך בדרך 7. אז מה אני צריך לעשות? ובכן, בדיוק כמו לפני, אני רק צריך כדי לנקות את השער, לצאת מהדרך, ולבנות צומת חדשה מהדרך 7. בדיוק ככה. 

אז עכשיו אני כבר עברתי 1 ולאחר מכן 7. ועכשיו שמתי לב, אני סוג של על subbranch החדש זה. תקין. כל דבר אחר מ -16 ב, לא אכפת לי עליו. אני לא עושה שום דבר 16. אני עושה 17 דברים. 

אז עכשיו מ -17 ב, יש לי ל סוג של להבה שבילים חדשים כאן. הספרה הבאה המפתח שלי היא 0. אני בבירור לא יכול להגיע לשום מקום. אני פשוט נבנה צומת זו. אז אני יודע שאין נתיבים קדימה מכאן. אז אני צריך לעשות אחד בעצמי. 

אז אני malloc צומת חדשה ויש לי יש 0 נקודות. ואז עוד פעם אחת, אני malloc צומת חדשה ויש לי נקודה אחת שם. שוב, אני כבר מותש המפתח שלי, 1701. אז אני מסתכל למטה ואני לרסס לצייר ייל. זה השם של צומת זו. 

ואז עכשיו אם אי פעם אני צריך לראות אם ייל הוא באיירי זה, אני מתחיל בשורש, אני יורד 1701, ומסתכל למטה. ואם אני רואה ספריי ייל צייר על האדמה, ואז אני יודע ייל קיימת באיירי זה. בואו נעשה עוד אחד. בואו להכניס Dartmouth לזה איירי, שנוסדה בשנת 1769. 

התחל בשורש שוב. הספרה הראשונה שלי של המפתח שלי היא 1. אני יכול לעבור בשלום את הדרך ש. שכבר קיים. הספרה הבאה של המפתח שלי היא 7. אני יכול לעבור בשלום את הדרך ש. זה קיים גם כן. 

הבא שלי הוא 6. מכאן, מהמקום שבי אני כרגע בצהוב שם בצומת האמצע, 6 נעולים מרגע זה. אם אני רוצה ללכת במסלול הזה, אני צריך לבנות את זה בעצמי. אז אני malloc צומת חדשה ויש לי יש נקודה 6. ואז, שוב, אני לוהט שבילים חדשים כאן. 

אז אני malloc צומת חדשה, כך שמ כי מספר node-- נתיב 9-- ואז עכשיו אם אני נוסע 1769, ואני מסתכל למטה. אין שום דבר כרגע ריסס שם. אני יכול לכתוב Dartmouth. ואני כבר הוכנס Dartmouth לאיירי. 

אז זה הכנסה דברים לאיירי. עכשיו אנחנו רוצים לחפש את דברים. איך לחפש דברים באיירי? ובכן, זה פחות או יותר על אותו הרעיון. עכשיו אנחנו רק להשתמש בספרות של המפתח כדי לראות אם אנחנו יכולים לנווט מהשורש לאן שאנחנו רוצים ללכת באיירי. 

אם נקלע למבוי סתום בכל נקודה, ואז אנו יודעים כי אלמנט שלא ניתן קיים או אחר הדרך שהיית כבר נוקה. אם אנחנו עושים את זה כל הדרך ל הסוף, כל מה שאנחנו צריכים לעשות הוא להסתכל למטה ולראות אם זה האלמנט שאנחנו מחפשים. אם כן, הצלחה. אם זה לא, להיכשל. 

אז בואו לחפש הרווארד באיירי זה. אנחנו מתחילים בשורש. ושוב, אנחנו הולכים ליצור מצביע חציה לעשות המהלכים שלנו בשבילנו. מהשורש אנחנו יודעים ש המקום הראשון שאנחנו צריכים ללכת הוא 1, אנחנו יכולים לעשות את זה? כן אנחנו יכולים. אם קיים בבטחה. אנחנו יכולים ללכת לשם. 

עכשיו, המקום הבא שאנחנו צריכים ללכת הוא 6. האם הנתיב 6 קיים מכאן? כן, היא עושה. אנחנו יכולים ללכת במורד השביל 6. ואנחנו בסופו כאן. 

אנחנו יכולים ללכת במורד השביל 3 מכאן? ובכן, כפי שמתברר, כן, זה קיים גם. ואנחנו יכולים לקבל בדרך 6 מכאן? כן אנחנו יכולים. 

יש לנו לא ממש ענה על השאלה עדיין. יש עדיין אחד יותר צעד, שהוא עכשיו אנחנו צריכים להסתכל למטה ו לראות אם זה מעשה-- אם אנחנו מחפשים הרווארד, הוא ש מה אנו מוצאים אחרי שממצים את המפתח? בדוגמא אנו משתמשים כאן, השנים הם תמיד ארבע ספרות. אבל ייתכן שאתה משתמש בו הדוגמא אתה מאחסן מילון של מילות. 

וכך, במקום 10 מצביעים למיקום שלי, אולי יש לך 26. אחת עבור כל אות של אלף בית. ויש כמה מילות כמו עטלף, אשר היא קבוצת משנה של אצווה, למשל. ולכן גם אם אתה מקבל ל סוף מפתח ואתה מסתכל למטה, אתה לא יכול לראות את מה ש שאתה מחפש. 

אז אתה תמיד צריך לעבור הנתיב כולו ולאחר מכן אם היו יכול בהצלחה לעבור את כל הדרך, להסתכל למטה ולעשות אישור סופי. האם זה מה שאני מחפש? ובכן, אני מסתכל למטה לאחר שהחלתי בראש והולכים 1,636. אני מסתכל למטה. אני רואה בהרווארד. אז, כן, הצלחתי. מה אם מה שאני מחפש לא באיירי, אם כי. מה אם אני מחפש פרינסטון, אשר נוסד בשנת 1746. וכך הופך 1,746 המפתח שלי כדי לנווט את איירי. ובכן, אני מתחיל בשורש. והמקום הראשון שאני רוצה להולך במורד השביל 1. האם אני יכול לעשות את זה? כן אני יכול. 

אני יכול ללכת במורד השביל 7 משם? כן, אני יכול. שקיים גם. אבל אני יכול ללכת במורד השביל 4 מכאן? זה כמו לשאול את השאלה, יכול אני ממשיך במורד שכיכר קטנה כי אני כבר מודגש בצהוב? אין שם כלום. תקין. 

אין דרך קדימה במורד השביל 4. אם פרינסטון היה באיירי זה, כי 4 היה כבר פינה לנו. ולכן בשלב זה אנחנו כבר הגענו למבוי סתום. אנחנו לא יכולים ללכת יותר. וכך אנו יכולים לומר, בודאות, לא. פרינסטון אינו קיים באיירי זה. 

אז מה כל זה אומר? תקין. יש הרבה קורה כאן. יש מצביעים בכל המקום. ו, כפי שאתה יכול לראות רק מהתרשים, יש הרבה צמתים ש הם סוג של עפים. אבל שמתי לב בכל פעם שאנחנו רוצים לבדוק אם משהו היה באיירי, רק היינו צריך לעשות 4 מהלכים. 

בכל פעם שאנחנו רוצים הכנס משהו באיירי, אנחנו צריכים לעשות 4 מהלכים, אולי mallocing כמה דברים בדרך. אבל כפי שראינו כאשר אנו מוכנסים Dartmouth לאיירי, לפעמים חלק מהנתיב אולי כבר פינה לנו. וכך כאיירי מקבלת וגדול יותר גדול יותר, יש לנו לעשות פחות עבודה בכל זמן להכניס דברים חדשים כי יש לנו כבר נבנה הרבה ביניים ענפים לאורך הדרך. אם אנחנו היחידים שצריכים להסתכל על 4 דברים, 4 הוא רק קבוע. אנחנו באמת סוג של התקרבות הכנסת זמן קבועה ובדיקת זמן קבועה. האיזון, כמובן, הוא ש איירי זה, כמו שאתה יכול לומר, הוא עצום. כל אחד מצומת אלה תופס הרבה מקום. 

אבל זה האיזון. אם אנחנו רוצים באמת מהירים הכנסה, מחיקה מהירה באמת, ובדיקה מהירה באמת, יש לנו ל יש הרבה נתונים עפים. אנחנו צריכים להפריש הרבה מקום וזיכרון שלמבנה הנתונים להתקיים. 

ואז זה האיזון. אבל זה נראה כאילו אנחנו אולי מצא אותה. אנו יכולים למצוא ש גביע קדוש של מבני נתונים עם החדרה מהירה, מחיקה, ובדיקה. ואולי זה יהיה מבנה הנתונים מתאים לשימוש עבור כל מידע ש אנחנו מנסים חנות. אני דאג לויד, זה cs50.