עץ בינארי הוא אמצעי לאחסון נתונים. אנו אומרים כי עץ בינארי הוא מבנה נתונים מופשט (Abstract Data Type, ADT), אותו נוכל לממש בתכנית מחשב בדרכים שונות.

14.1 הגדרת עץ בינארי, ומושגים נוספים בהקשר של עץ בינארי

14.2 + 14.3 יצוג עץ בתכנית מחשב, ופונ' רקורסיבית להוספת ערך לעץ

תרגול עצמי בסיסי בנושא בניית עץ חיפוש בינארי

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

14.3.2 בניית עץ חיפוש בלולאה

14.3.3 בניית עץ חיפוש בלולאה בעזרת מצביע למצביע

תרגול עצמי בסיסי בנושא עץ חיפוש בינארי ומצביע למצביע

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

את הערכים הוסיפו באמצעות פונ' הכנסה לעץ המקבלת מצביע למצביע.

14.3.4 עלות בניית עץ חיפוש בינארי

14.4 ביקור בעץ בינארי (בפרט לשם הדפסתו)

תרגול עצמי בסיסי בנושא ביקור בעץ בינארי

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

עתה התכנית מציגה את הערכים החיוביים בלבד בעץ.

14.5 חיפוש ערך מבוקש בעץ בינארי כללי ובעץ חיפוש בינארי

14.5.1 חיפוש ערך בעץ שאינו עץ חיפוש

תרגול עצמי בסיסי בנושא ביקור בעץ שאינו עץ חיפוש

כתבו תכנית הקוראת סדרת ערכים עד קבלת הערך אפס ובונה מהם עץ.

אופן בניית העץ יהיה הבא:

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

עתה התכנית קוראת ערך נוסף, ומציגה כמה פעמים הערך מופיע בעץ.

14.5.2 חיפוש ערך בעץ חיפוש בינארי

תרגול עצמי בסיסי בנושא חיפוש ערך בעץ חיפוש

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

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

14.6 ספירת מספר הצמתים בעץ בינארי

תרגול עצמי בסיסי בנושא ספירת צמתים בעץ בינארי

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

עתה התכנית סופרת ומציגה, כמה עלים יש בעץ.

14.7 מציאת עומק עץ

תרגול עצמי בסיסי בנושא מציאת מקסימום בעץ

כתבו תכנית הקוראת סדרת ערכים עד קבלת הערך אפס ובונה מהם עץ.

אופן בניית העץ יהיה הבא:

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

עתה התכנית מזמנת פונ' המוצאת את עומקו של העץ. התכנית מציגה את הנתון.

14.8 האם עץ בינארי מקיים שלכל צומת פנימי יש שני ילדים?

תרגול עצמי בסיסי בנושא: בדיקת עץ

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

עתה זמנו פונ' שבודקת האם כל צומת בעץ מקיים ש:

א. אם לצומת יש ילד שמאלי, אזי הערך בילדו השמאלי מחלק את הערך בצומת

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

הפונ' תחזיר את הערך true אם כל הצמתים בעץ מקיימים את התכונה, ואת הערך false אחרת.

התכנית הרשית תציג פלט בהתאם לערך שהפונ' מחזירה.

14.9 האם עץ בינארי מקיים שעבור כל צומת סכום הערכים בבת-העץ השמאלי קטן או שווה מסכום הערכים בתת-העץ הימני

לבעיה זאת אציג שני פתרונות:

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

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

נתחיל בפתרון הנאיבי יותר, ואחר נתקדם גם לפתרון המורכב יותר.

14.9.1 הפתרון הנאיבי

דיון בזמן הריצה של התכנית (הנאיבית, שראינו מעל)

14.9.2 הפתרון המתוחכם (והיעיל)

תרגול עצמי (לא כ"כ בסיסי, ולא כ"כ קל, אך מודרך) בנושא החזרת מידע מתת-עץ מיטבי בצורה יעילה (בזמן ליניארי)

14.10 שחרור עץ בינארי

14.11 מחיקת ערך מעץ חיפוש בינארי

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

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

תרגול עצמי בסיסי בנושא: 'קודם בעץ' של ערך

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

כתבו תכנית הבונה עץ חיפוש בינארי, ואחר קוראת מספר.

אם המספר אינו מצוי בעץ היא מודיעה על כך.

אם המספר מצוי בעץ בצומת שאין לו שני ילדים היא נותנת הודעה שניה.

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

לסיום, הפונ' משחררת את העץ.

עתה נפנה להצגת האלגוריתם

על שלושת המקרים השונים שוא כולל:

• מחיקת ערך המצוי בעלה
• מחיקת ערך המצוי בצומת עם ילד יחיד
• מחיקת ערך המצוי בצומת עם שני ילדים

קוד הפונ' למחיקת ערך מעץ חיפוש בינארי, וסימולציית הרצה של התכנית

תרגול עצמי בנושא מחיקה מעץ חיפוש בינארי

14.12 עלות הפעולות: הוספה, חיפוש, מחיקה על עץ חיפוש בינארי (לעומת על מערך ממוין)

14.13 תרגילים

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

14.14 בחן את עצמך

כי כמו שכבר נאמר: 'קשה באימונים, קל בקרב'