[Powered by Google Translate] [חיפוש בינארי] [פטריק שמידט - אוניברסיטת הרווארד] [זה CS50. - CS50.TV] 

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

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

מה שהרגע עשה היה בעצם חיפוש בינארי. כפי ששם מרמז זה, הוא מבצע חיפוש האסטרטגיה שלה בעניין בינארי. מה זה אומר? ובכן, בהתחשב ברשימה של פריטים ממוינים, אלגוריתם החיפוש הבינארי מקבל החלטה בינארית - שמאל או ימין, גדול יותר או קטן יותר, בסדר אלפביתי לפני או אחרי - בכל נקודה. עכשיו שיש לנו שם זה הולך יחד עם אלגוריתם חיפוש זה, בואו נסתכל על דוגמה נוספת, אבל הפעם עם רשימה של מספרים ממוינים. אומר שאנחנו מחפשים את המספר 144 ברשימה זו של מספרים ממוינים. בדיוק כמו קודם, אנו מוצאים את המספר שנמצא באמצע - אשר במקרה זה הוא 13 - 144 ולראות אם הוא גדול או קטן מ 13. מאז זה באופן ברור יותר מ 13, אנו יכולים להתעלם מכל מה שהוא 13 או פחות ואתרכז רק במחצית השנייה. מאז יש לנו עכשיו עוד מספר הפריטים עזב, אנחנו פשוט לבחור מספר שקרוב לאמצע. במקרה זה אנחנו בוחרים 55. אנחנו יכולים לבחור 89 באותה קלות. אוקיי. שוב, 144 הוא יותר מ 55, ולכן אנחנו הולכים לצד ימין. למזלנו, באמצע המספר הבא הוא 144, זה שאנחנו מחפשים. אז כדי למצוא את 144 באמצעות חיפוש בינארי, אנחנו נוכל למצוא אותו רק 3 שלבים. אם הייתי משתמש חיפוש יניארי כאן, זה היה לוקח לנו 12 מדרגות. כעניין של עובדה, מאחר ושיטת חיפוש זה חצי מספר הפריטים יש להסתכל בכל שלב, היא תמצא את הפריט שהוא מחפש בערך ביומן של מספר הפריטים ברשימה. עכשיו שאנחנו כבר ראינו 2 דוגמאות, בואו נסתכל חלק pseudocode לפונקציה רקורסיבית שמיישמת חיפוש בינארי. התחילו מלמעלה, אנחנו רואים שאנחנו צריכים למצוא פונקציה שלוקחת 4 טענות: מפתח, מערך, דקות, ומקסימום. המפתח הוא המספר שאנחנו מחפשים, אז 144 בדוגמא הקודמת. מערך הוא הרשימה של מספרים שאנו מחפשים. דקות ומקס הם המדדים של עמדות המינימום ומקסימום שאנו בודקים כעת. לכן, כאשר אנחנו מתחילים, דקות תהיינה אפס והמקסימום יהיה המדד המרבי של המערך. כפי שאנו לצמצם את החיפוש, אנו נעדכן דקות ומקסימום להיות רק בטווח שאנחנו עדיין מסתכלים פנימה 

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

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

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

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

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

דבר נוסף שאנו יכולים לעשות הוא להדפיס את כל המספרים על ידי ביצוע inorder חצייה. Inorder חציית פירושו להדפיס את הכל בעץ משנה שמאל אחרי הדפסת הצומת עצמו ולאחר מכן על ידי הדפסה כל דבר בימין עץ המשנה. לדוגמה, בואו ניקח עץ החיפוש האהוב שלנו ולהדפיס את המספרים לפי סדר מיון. אנחנו מתחילים בשורש של 13, אך לפני ההדפסה שיש לנו 13 להדפיס הכל בתת העץ שמאלי. אז אנחנו הולכים 5. אנחנו עדיין צריכים ללכת עמוק יותר בתוך העץ עד שנמצאנו את הצומת השמאלית ביותר, שהוא אפס. לאחר ההדפסה אפס, אנחנו חוזרים עד 1 ולהדפיס את זה. אז אנחנו הולכים לימין עץ המשנה, שהוא 2, ולהדפיס את זה. עכשיו שאנחנו עושים עם זה עץ משנה, אנחנו יכולים לחזור עד 3 ולהדפיס אותו. ממשיכים לגבות, אנחנו מדפיסים 5 ואחר כך 8. עכשיו שיש לנו בכל השאירו עץ משנה, אנחנו יכולים להדפיס 13 ולהתחיל לעבוד על עץ המשנה נכון. אנו מדלגים אל 34, אבל לפני ההדפסה 34 אנחנו צריכים להדפיס את עץ המשנה השמאלי שלה. אז אנחנו מדפיסים 21; אז אנחנו מקבלים להדפיס 34 ולבקרו ימניים עץ המשנה. מאז 55 אין תת עץ שמאלי, אנחנו להדפיס אותו ולהמשיך לעץ משנה זכותה. 144 יש תת עץ שמאלי, ולכן אנחנו מדפיסים 89, ואחריו 144, ולבסוף הימני ביותר הצומת של 233. יש לך את זה; כל המספרים מודפסים בהוראה מהנמוכה ביותר לגבוה ביותר. 

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

אם אנחנו יכולים להוסיף דברים, אנחנו טובים יותר להיות מסוגלים למחוק דברים גם כן. לרוע מזלנו, המחיקה היא קצת יותר מסובכת - לא הרבה, אבל רק קצת. יש 3 תרחישים שונים שאנחנו צריכים לשקול בעת מחיקת אלמנטים מעצי חיפוש בינאריות. ראשית, במקרה הקל ביותר הוא שהאלמנט הוא צומת עלה. במקרה זה, אנחנו פשוט למחוק אותו ולהמשיך בעסק שלנו. אומר שאנחנו רוצים למחוק את 7 כי אנחנו רק הוספנו. ובכן, אנחנו פשוט למצוא אותו, להסיר אותו, וזהו. המקרה הבא הוא אם הצומת יש רק 1 ילד. כאן אנו יכולים למחוק את הצומת, אבל קודם צריכים לוודא כדי לחבר את עץ המשנה שנותר עתה ללא הורים להורה של הצומת אנחנו פשוט נמחקנו. אומר שאנחנו רוצים למחוק 3 מהעץ שלנו. אנחנו לוקחים את אלמנט הילד של צומת ולצרף אותו להורה של הצומת. במקרה זה, אנחנו מצרפים עכשיו 1 עד 5. זה עובד ללא בעיה משום שאנו יודעים, על פי רכוש עץ החיפוש בינארי, כל מה שבעץ המשנה השמאלי של 3 היה פחות מ 5. עכשיו ש3 עץ משנה שלו נלקח לטיפול, אנו יכולים למחוק אותו. המקרה השלישי והאחרון הוא מורכב ביותר. זהו מקרה כאשר הצומת שאנו רוצים למחוק יש 2 ילדים. על מנת לעשות זאת, יש לנו קודם למצוא את הצומת שיש הערך הגדול ביותר הבא, להחליף שתיים, ולאחר מכן למחוק את הצומת בשאלה. שים לב לצומת שיש הערך הגדול ביותר הבא לא יכול להיות 2 ילדים עצמו מאז הילד השמאלי שלה יהיה מועמד טוב יותר לגודלה הבא. לכן, מחיקת צומת עם 2 ילדים מסתכמת בהחלפה של 2 צומת, ולאחר מכן מחיקה מתבצעת על ידי 1 של 2 כללים שפורט לעיל. לדוגמה, אניח שאנחנו רוצים למחוק את צומת השורש, 13. הדבר הראשון שאנו עושים זה למצוא את הערך הגדול ביותר בעץ הבא אשר, במקרה זה, הוא 21. אז אנחנו מחליפים את 2 צומת, מה שהופכים 13 עלה ו21 צומת הקבוצה המרכזית. עכשיו אנחנו יכולים פשוט למחוק 13. 

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

יש לך את זה. עכשיו אתה יודע על חיפוש בינארי ועצי חיפוש בינאריות. אני פטריק שמידט, וזה CS50. [CS50.TV] דרך ברורה אחת היא לסרוק את הרשימה מ... [צפצוף] ... מספר הפריטים ... yep [צוחק] לפרסם ... צומת של 234 ... augh. >> יש! זה היה -