[Powered by Google Translate] איך היית לייצג את כל בני המשפחה שלך במחשב? אנחנו יכולים פשוט להשתמש ברשימה, אבל יש היררכיה ברורה כאן. 

נניח שאנחנו מתחילים עם סבתא רבא שלך, אליס. יש לה 2 בנים, בוב והסבא שלך, צ'רלי. צ'רלי יש 3 ילדים, הדוד שלך, דייב, הדודה שלך, חווה, והאבא שלך, פרד. אתה הבן היחיד של פרד. 

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

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

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

עץ בינארי הוא סוג מסוים של עץ, בכל צומת שיש לו, לכל היותר, 2 ילדים. הנה struct של צומת של עץ בינארי בג בכל צומת יש כמה נתונים הקשורים אליו ו 2 מצביעים לצומת אחרים. 

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

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

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

כך זה היה נראה אם ​​פנינו לכל צומת structs C. שים לב שאם ילד נעדר המצביע הוא ריק. איך לבדוק אם 7 הם בעץ? אנחנו מתחילים בשורש. שבע הם יותר מ 6, אז אם זה בעץ, זה חייב להיות לצד ימין. ואז, זה פחות מ 8, ולכן הוא חייב להישאר. הנה, מצאו 7. עכשיו, תבדקו עבור 5. חמש הם פחות מ 6, אז זה חייב להיות בצד השמאל. חמש גדולים מ 2, אז זה חייב להיות נכון, והוא גם עולה על 4, אז זה חייב להיות נכון שוב. עם זאת, אין כאן ילדה. המצביע הוא ריק. משמעות הדבר הוא כי 5 הם לא בעץ שלנו. 

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

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

כמה מהר הן פעולות על עץ חיפוש? זכור כי Bigohnotation מבקש לספק גבול עליון. במקרה הגרוע ביותר, העץ שלנו יכול להיות פשוט רשימה מקושרת כלומר הכנסה ש, מחיקה, וחיפוש יכול לקחת זמן פרופורציונלי למספר צומת בעץ. זה O (n). 

לדוגמה, להלן עץ חיפוש חוקי. עם זאת, אם אנו מנסים למצוא 9, יש לנו לחצות כל צומת. אין זה טוב יותר מאשר רשימה מקושרת. באופן אידיאלי, הייתי רוצה שכל צומת של עץ החיפוש שלנו יש 2 ילדים. בדרך זו, הכנסה, מחיקה וחיפוש היה לוקח, במקרה הגרוע, O (logn) זמן. העץ מקודם יכול להיות יותר מאוזן, כמו זה. כעת, במבט את כל ערך לוקח לכל היותר 3 שלבים. עץ זה הוא מאוזן, משמעות היא שיש לו עומק מינימאלי ביחס למספר צומת. 

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

השם שלי הוא Bannus אן דר Kloot. זה CS50.