עץ חיפוש בינארי - מסד נתונים מובנה המכיל צמתים, שני קישורים לצמתים אחרים, ימין ושמאל. צמתים הם אובייקט של המחלקה שיש לו נתונים, ו-NULL הוא הסימן שמסמן את סוף העץ.
הוא מכונה לעתים קרובות BST, שיש לו מאפיין מיוחד: צמתים גדולים מהשורש ממוקמים מימין לו, וקטנים יותר משמאל.
תיאוריה ומינוח כללי
בעץ חיפוש בינארי, כל צומת, למעט השורש, מחובר באמצעות קצה מכוון מצומת אחד למשנהו, הנקרא האב. כל אחד מהם יכול להיות מחובר למספר שרירותי של צמתים, הנקראים ילדים. צמתים ללא "ילדים" נקראים עלים (צמתים חיצוניים). אלמנטים שאינם עלים נקראים פנימיים. צמתים עם אותו הורה הם אחים. הצומת העליון נקרא השורש. ב-BST, הקצה אלמנט לכל צומת וודא שיש לו מאפיין מיוחד עבורו.
מינוח עצים:
- העומק של צומת הוא מספר הקצוות המוגדרים מהשורש אליו.
- גובה של צומת הוא מספר הקצוות המוגדרים ממנו ועד העלה העמוק ביותר.
- גובה העץ נקבע לפי גובה השורש.
- עץ החיפוש הבינארי הוא עיצוב מיוחד, הוא מספק את היחס הטוב ביותר בין גובה ומספר צמתים.
- Height h עם N צמתים לכל היותר O (לוג N).
תוכל להוכיח זאת בקלות על ידי ספירת הצמתים בכל רמה, החל מהשורש, בהנחה שהוא מכיל את המספר הגדול ביותר מהם: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 פתרון זה עבור h נותן h=O (לוג n).
היתרונות של עץ:
- שקף את הקשרים המבניים של הנתונים.
- משמש לייצוג היררכיות.
- הבטח התקנה וחיפוש יעילים.
- עצים הם נתונים גמישים מאוד, המאפשרים לך להזיז עצי משנה במינימום מאמץ.
שיטת חיפוש
באופן כללי, כדי לקבוע אם ערך נמצא ב-BST, התחל עץ חיפוש בינארי בשורשו וקבע אם הוא עומד בדרישות:
- להיות בשורש;
- להיות בתת-עץ השמאלי של השורש;
- בתת-עץ הימני של השורש.
אם לא מתקיים אוגר בסיס, מבצעים חיפוש רקורסיבי בתת-העץ המתאים. יש למעשה שתי אפשרויות בסיסיות:
- העץ ריק - החזר false.
- הערך נמצא בצומת השורש - החזר אמת.
יש לציין שעץ חיפוש בינארי עם סכימה מפותחת מתחיל תמיד לחפש לאורך הנתיב מהשורש לעלה. במקרה הגרוע, זה הולך עד העלה.לכן, הזמן הגרוע ביותר הוא פרופורציונלי לאורכו של השביל הארוך ביותר מהשורש לעלה, שהוא גובה העץ. באופן כללי, זה כאשר אתה צריך לדעת כמה זמן לוקח להסתכל למעלה כפונקציה של מספר הערכים המאוחסנים בעץ.
במילים אחרות, יש קשר בין מספר הצמתים ב-BST לבין גובה העץ, בהתאם ל"צורתו". במקרה הגרוע, לצמתים יש רק ילד אחד, ועץ חיפוש בינארי מאוזן הוא בעצם רשימה מקושרת. לדוגמה:
50
/
10
15
30
/
20
לעץ הזה יש 5 צמתים וגובה=5. מציאת ערכים בטווח 16-19 ו-21-29 ידרוש את הנתיב הבא מהשורש לעלה (הצומת המכיל את הערך 20), כלומר., זה ייקח זמן פרופורציונלי למספר הצמתים. במקרה הטוב, לכולם יש 2 ילדים, והעלים ממוקמים באותו עומק.
עץ החיפוש הבינארי הזה כולל 7 צמתים וגובה=3. באופן כללי, לעץ כזה (עץ מלא) יהיה גובה של לוג 2 (N) בקירוב, כאשר N הוא מספר הצמתים בעץ. הערך של לוג 2 (N) הוא מספר הפעמים (2) שניתן לחלק את N לפני שמגיעים לאפס.
לסיכום: הזמן הגרוע ביותר הדרוש לחיפוש ב-BST הוא O (גובה העץ). העץ ה"ליניארי" המקרה הגרוע ביותר הוא O(N), כאשר N הוא מספר הצמתים בעץ. במקרה הטוב, עץ "שלם" הוא O(log N).
BST תוספת בינארית
תוהה איפה צריך להיותהצומת החדש ממוקם ב-BST, אתה צריך להבין את ההיגיון, זה חייב להיות ממוקם במקום שבו המשתמש מוצא אותו. בנוסף, עליך לזכור את הכללים:
- כפילויות אינן מותרות, ניסיון להכניס ערך כפול יגרום לחריגה.
- שיטת ההוספה הציבורית משתמשת בשיטת "עוזר" רקורסיבית כדי להכניס בפועל.
- צומת המכיל ערך חדש מוכנס תמיד כעלה ב-BST.
- שיטת ההוספה הציבורית מחזירה ריק, אך שיטת העזר מחזירה BSTnode. הוא עושה זאת כדי לטפל במקרה שבו הצומת המועבר אליו הוא ריק.
באופן כללי, שיטת העזר מציינת שאם עץ החיפוש הבינארי המקורי ריק, התוצאה היא עץ עם צומת אחד. אחרת, התוצאה תהיה מצביע לאותו צומת שהועבר כארגומנט.
מחיקה באלגוריתם בינארי
כפי שניתן לצפות, מחיקת אלמנט כרוכה במציאת צומת המכיל את הערך שיש להסיר. יש כמה דברים בקוד הזה:
- BST משתמש בשיטת מחיקה עוזרת, עמוסה מדי. אם האלמנט שאתה מחפש לא נמצא בעץ, בסופו של דבר שיטת העזר תיקרא עם n==null. זה לא נחשב לשגיאה, העץ פשוט לא משתנה במקרה הזה. שיטת העזר למחוק מחזירה ערך - מצביע לעץ המעודכן.
- כאשר עלה מוסר, ההסרה מעץ החיפוש הבינארי מגדירה את מצביע הצאצא התואם של האב שלו ל- null, או את השורש ל- null אם זה שהוסר הואהצומת הוא שורש ואין לו ילדים.
- שימו לב שקריאת המחיקה חייבת להיות אחת מהאפשרויות הבאות: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), מפתח)). לפיכך, בכל שלושת המקרים נכון ששיטת המחיקה פשוט מחזירה null.
- כאשר החיפוש אחר הצומת המכיל את הערך למחיקה מצליח, קיימות שלוש אפשרויות: הצומת שיימחק הוא עלה (אין לו ילדים), הצומת שיימחק יש לו ילד אחד, יש לו שניים ילדים.
- כאשר לצומת המוסר יש ילד אחד, אתה יכול פשוט להחליף אותו בצאצא, ולהחזיר מצביע לילד.
- אם לצומת שיש למחוק יש אפס או 1 ילדים, אז שיטת המחיקה "תעקוב אחר הנתיב" מהשורש לאותו צומת. אז הזמן הגרוע ביותר הוא פרופורציונלי לגובה העץ, הן לחיפוש והן להוספת.
אם לצומת שיש להסיר יש שני ילדים, ננקטים הצעדים הבאים:
- מצא את הצומת למחיקה, עקוב אחר הנתיב מהשורש אליו.
- מצא את הערך הקטן ביותר של v בתת-עץ הימני, המשך לאורך השביל אל העלה.
- הסר באופן רקורסיבי את הערך של v, בצע את אותו הנתיב כמו בשלב 2.
- לכן, במקרה הגרוע, הנתיב מהשורש לעלה מתבצע פעמיים.
סדר מעברים
מעבר הוא תהליך שמבקר בכל הצמתים בעץ. מכיוון שעץ חיפוש בינארי C הוא מבנה נתונים לא ליניארי, אין מעבר ייחודי. לדוגמה, לפעמים מספר אלגוריתמי מעברמקובצים לשני הסוגים הבאים:
- חציית עומק;
- מעבר ראשון.
יש רק סוג אחד של מעבר רוחב - עוקף את המפלס. מעבר זה מבקר בצמתים ברמה למטה ושמאלה, למעלה וימינה.
ישנם שלושה סוגים שונים של מעברי עומק:
- עובר הזמנה מוקדמת - תחילה בקר את ההורה ולאחר מכן את הילד השמאלי והימני.
- Passing InOrder - ביקור אצל הילד השמאלי, ולאחר מכן את ההורה והילד הימני.
- עבר את PostOrder - ביקור אצל הילד השמאלי, ואז הילד הימני, ואז ההורה.
דוגמה לארבע מעברים של עץ חיפוש בינארי:
- הזמנה מראש - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
האיור מציג את סדר הביקור בצמתים. המספר 1 הוא הצומת הראשון במעבר מסוים, ו-7 הוא הצומת האחרון.
ניתן לייצג את המעברים הכלליים האלה כאלגוריתם בודד, בהנחה שכל צומת מבקר שלוש פעמים. סיור אוילר הוא טיול סביב עץ בינארי שבו מתייחסים לכל קצה כאל קיר שהמשתמש אינו יכול לחצות. בהליכה זו, כל צומת יבקר משמאל, או מתחת או מימין. סיור אוילר, המבקר בצמתים משמאל, גורם לעקוף מילת היחס. כאשר מבקרים בצמתים למטה, הם עוברים לפי הסדר. וכשמבקרים בצמתים מימין - קבלועוקף שלב אחר שלב.
ניווט וניפוי באגים
כדי להקל על הניווט בעץ, צור פונקציות שבודקות תחילה אם הן הילד השמאלי או הימני. כדי לשנות את המיקום של צומת, חייבת להיות גישה נוחה למצביע בצומת האב. יישום נכון של עץ הוא מאוד קשה, אז אתה צריך לדעת וליישם תהליכי ניפוי באגים. לעץ חיפוש בינארי עם מימוש יש לעתים קרובות מצביעים שאינם מציינים למעשה את כיוון הנסיעה.
כדי להבין את כל זה, נעשה שימוש בפונקציה שבודקת אם העץ יכול להיות נכון, ועוזרת למצוא שגיאות רבות. לדוגמה, הוא בודק אם צומת האב הוא צומת צאצא. עם assert(is_wellformed(root)) ניתן לתפוס שגיאות רבות בטרם עת. באמצעות כמה נקודות שבירה נתונות בתוך פונקציה זו, תוכל גם לקבוע בדיוק איזה מצביע שגוי.
פונקציה קונסולינאוסגאב
פונקציה זו שוטפת את כל העץ לקונסולה ולכן היא שימושית מאוד. הסדר שבו מבוצע יעד פלט העץ הוא:
- כדי לעשות זאת, תחילה עליך לקבוע איזה מידע ייפלט דרך הצומת.
- ואתה גם צריך לדעת כמה רחב וגבוה העץ הוא כדי לקחת בחשבון כמה מקום להשאיר.
- הפונקציות הבאות מחשבות מידע זה עבור העץ וכל תת-עץ. מכיוון שאתה יכול לכתוב לקונסולה רק שורה אחר שורה, תצטרך גם להדפיס את העץ שורה אחר שורה.
- עכשיו אנחנו צריכים עוד דרך לסגתכל העץ, לא רק שורה אחר שורה.
- בעזרת פונקציית ה-dump, ניתן לקרוא את העץ ולשפר משמעותית את אלגוריתם הפלט, בכל הנוגע למהירות.
עם זאת, פונקציה זו תהיה קשה לשימוש על עצים גדולים.
Copy constructor and destructor
מכיוון שעץ אינו מבנה נתונים טריוויאלי, עדיף ליישם בנאי העתקה, הרס ואופרטור הקצאה. קל ליישם את ההורס באופן רקורסיבי. עבור עצים גדולים מאוד, הוא יכול להתמודד עם "הצפת ערמות". במקרה זה, הוא מנוסח באופן איטרטיבי. הרעיון הוא להסיר את העלה המייצג את הערך הקטן ביותר מכל העלים, כך שהוא נמצא בצד שמאל של העץ. כריתת העלים הראשונים יוצרת עלים חדשים, והעץ מתכווץ עד שלבסוף הוא מפסיק להתקיים.
ניתן ליישם את בנאי ההעתקה גם באופן רקורסיבי, אך היזהר אם נזרק חריג. אחרת, העץ הופך במהירות לבלבול ונוטה לשגיאות. לכן הגרסה האיטרטיבית מועדפת. הרעיון הוא לעבור על העץ הישן והעץ החדש, כמו שעשיתם בהרס, לשבט את כל הצמתים שנמצאים בעץ הישן אבל לא את החדשים.
בשיטה זו, יישום עץ החיפוש הבינארי נמצא תמיד במצב בריא וניתן להסירו על ידי המשמיד גם במצב לא שלם. אם מתרחש חריג, כל מה שאתה צריך לעשות הוא להורות למשמיד למחוק את העץ הגמור למחצה. מפעיל משימהניתן ליישם בקלות באמצעות העתקה והחלפה.
יצירת עץ חיפוש בינארי
עצי חיפוש בינאריים אופטימליים הם יעילים להפליא אם מנוהלים כראוי. כמה כללים לעצי חיפוש בינאריים:
- לצומת אב יש לכל היותר 2 צמתים צאצאים.
- צומת הילד השמאלי תמיד קטן מהצומת האב.
- צומת צאצא חוקי תמיד גדול או שווה לצומת האב.
המערך שישמש לבניית עץ החיפוש הבינארי:
- מערך בסיס שלם של שבעה ערכים בסדר לא ממוין.
- הערך הראשון במערך הוא 10, אז השלב הראשון בבניית העץ הוא יצירת צומת שורש בן 10, כפי שמוצג כאן.
- עם קבוצה של צמתי שורש, כל הערכים האחרים יהיו ילדים של הצומת הזה. בהתייחס לכללים, הצעד הראשון שיש לעשות כדי להוסיף 7 לעץ הוא להשוות אותו לצומת השורש.
- אם הערך 7 קטן מ-10, הוא יהפוך לצומת הצאצא השמאלי.
- אם הערך 7 גדול או שווה ל-10, הוא יזוז ימינה. מכיוון שידוע ש-7 הוא פחות מ-10, הוא מוגדר כצומת הצאצא השמאלי.
- בצע השוואות באופן רקורסיבי עבור כל רכיב.
- בעקבות אותה תבנית, בצע את אותה השוואה מול הערך ה-14 במערך.
- השוואת הערך 14 לצומת השורש 10, בידיעה ש-14 הוא הילד הנכון.
- הולך דרך המערך,הגיע ל-20.
- התחל בהשוואת המערך עם 10, הגדול מביניהם. אז עברו ימינה והשוו את זה ל-14, הוא מעל גיל 14 ואין לו ילדים מימין.
- עכשיו יש ערך של 1. לפי אותה תבנית כמו הערכים האחרים, השווה בין 1 ל-10, זז שמאלה והשוואה ל-7 ולבסוף לילד השמאלי 1 של הצומת ה-7.
- אם הערך הוא 5, השווה אותו ל-10. מכיוון ש-5 הוא פחות מ-10, עברו שמאלה והשוו אותו ל-7.
- כדי לדעת ש-5 הוא פחות מ-7, המשך במורד העץ והשווה 5 לערך 1.
- אם ל-1 אין ילדים ו-5 גדול מ-1, אז 5 הוא צאצא חוקי של צומת אחד.
- לבסוף הכנס את הערך 8 לעץ.
- כאשר 8 הוא פחות מ-10, הזיזו אותו שמאלה והשוו אותו ל-7, 8 גדול מ-7, אז הזיזו אותו ימינה והשלימו את העץ, מה שהופך את 8 לילד של 7.
קבלת והערכה של האלגנטיות הפשוטה של עצי חיפוש בינאריים אופטימליים. כמו נושאים רבים בתכנות, הכוח של עצי חיפוש בינאריים נובע מהיכולת שלהם לפתור נתונים לרכיבים קטנים וקשורים. מעתה ואילך, תוכל לעבוד עם מערך הנתונים המלא בצורה מאורגנת.
בעיות חיפוש בינאריות פוטנציאליות
עצי חיפוש בינאריים הם נהדרים, אבל יש כמה אזהרות שכדאי לזכור. הם בדרך כלל יעילים רק אם הם מאוזנים. עץ מאוזן הוא עץ שבוההבדל בין הגבהים של תתי העצים של כל צומת בעץ הוא לכל היותר אחד. בואו נסתכל על דוגמה שעשויה לעזור להבהיר את הכללים. הבה נדמיין שהמערך מתחיל וניתן למיון.
אם תנסה להפעיל אלגוריתם עץ חיפוש בינארי על העץ הזה, הוא יפעל בדיוק כאילו הוא רק חוזר דרך המערך עד שיימצא הערך הרצוי. כוחו של החיפוש הבינארי טמון ביכולת לסנן במהירות ערכים לא רצויים. כאשר עץ אינו מאוזן, הוא לא יספק את אותן היתרונות כמו עץ מאוזן.
חשוב מאוד לבחון את הנתונים שהמשתמש עובד איתם בעת יצירת עץ חיפוש בינארי. אתה יכול לשלב שגרות כגון אקראית של מערכים לפני יישום עץ חיפוש בינארי עבור מספרים שלמים כדי לאזן אותו.
דוגמאות לחישוב חיפוש בינארי
אנחנו צריכים לקבוע איזה סוג של עץ יתקבל אם 25 יוכנס לעץ החיפוש הבינארי הבא:
10
/
/
5 15
/ /
/ /
2 12 20
בעת הכנסת x לעץ T שעדיין אינו מכיל x, המפתח x תמיד ממוקם בעלה חדש. בקשר לכך, העץ החדש ייראה כך:
10
/
/
5 15
/ /
/ /
2 12 20
25
איזה סוג של עץ תקבל אם תכניס 7 לעץ החיפוש הבינארי הבא?
10
/
/
5 15
/ /
/ /
2 12 20
תשובה:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
ניתן להשתמש בעץ חיפוש בינארי לאחסון כל אובייקט. היתרון בשימוש בעץ חיפוש בינארי במקום ברשימה מקושרת הוא שאם העץ מאוזן בצורה סבירה ודומה יותר לעץ "מלא" מאשר לעץ "ליניארי", ניתן ליישם את ההוספה, החיפוש וכל פעולות המחיקה לרוץ ב O(log N) זמן.
