שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2013 - עצים בינאריים

א. כתוב/י אלגוריתם שמקבל כקלט (מצביע לשורש של) עץ בינארי עם $n$ קדקודים ומחזיר תשובה "כן" אם העץ הוא עץ חיפוש ו"לא" אחרת. מה הסיבוכיות? ב. כתוב/י אלגוריתם שמקבל כקלט (מצביע לשורש של) עץ בינארי עם $n$ קדקודים ומחזיר תשובה "כן" אם העץ הוא עץ AVL ו"לא" אחרת. מה הסיבוכיות?

רמז: א. סריקה תוכית (in-order) של עץ חיפוש בינארי תקין מבקרת בקדקודים בסדר ערכים עולה. ב. עץ AVL הוא בראש ובראשונה עץ חיפוש בינארי, ועליו לקיים בנוסף את תכונת האיזון בכל קדקוד. ניתן לבדוק כל תכונה בנפרד.

פתרון: א. אלגוריתם לבדיקה האם עץ בינארי הוא עץ חיפוש: התכונה המרכזית של **עץ חיפוש בינארי (BST)** היא שסריקה תוכית (in-order) של העץ מבקרת בקדקודים בסדר עולה (ממוין). לכן, ניתן לכתוב אלגוריתם רקורסיבי המבצע סריקה תוכית, ובכל צעד מוודא שהערך בקדקוד הנוכחי גדול מהערך בקדקוד הקודם שבו ביקרנו. האלגוריתם יפעל כך: 1. נאתחל משתנה גלובלי או מצביע `previous` שיחזיק את הערך של הקדקוד האחרון שבו ביקרנו בסריקה. נאתחל אותו לערך קטן מכל ערך אפשרי בעץ (למשל, מינוס אינסוף). 2. נפעיל פונקציה רקורסיבית על שורש העץ. 3. בפונקציה הרקורסיבית עבור קדקוד `u`: א. אם `u` הוא `null`, נחזיר "כן". ב. נפעיל את הפונקציה רקורסיבית על תת-העץ השמאלי של `u`. אם הקריאה חזרה עם "לא", נחזיר "לא". ג. נבדוק אם הערך של `u` גדול מהערך של `previous`. אם לא, העץ אינו עץ חיפוש, ונחזיר "לא". ד. נעדכן את `previous` לערך של `u`. ה. נפעיל את הפונקציה רקורסיבית על תת-העץ הימני של `u`. נחזיר את התוצאה של קריאה זו. דרך חלופית היא להעביר לכל קריאה רקורסיבית את טווח הערכים המותר (`min`, `max`) עבור הקדקוד הנוכחי. **סיבוכיות:** * **סיבוכיות זמן:** האלגוריתם מבצע סריקה מלאה של העץ, כאשר כל קדקוד מבוקר פעם אחת בדיוק. לכן, סיבוכיות הזמן היא $O(n)$, כאשר $n$ הוא מספר הקדקודים בעץ. * **סיבוכיות מקום:** סיבוכיות המקום תלויה בעומק מחסנית הקריאות הרקורסיביות, שהוא שווה לגובה העץ, $h$. במקרה הגרוע (עץ מנוון הדומה לרשימה מקושרת), $h=O(n)$. במקרה הממוצע או עבור עץ מאוזן, $h=O(\log n)$. לכן, סיבוכיות המקום היא $O(h)$ או $O(n)$ במקרה הגרוע. ב. אלגוריתם לבדיקה האם עץ בינארי הוא עץ AVL: **עץ AVL** הוא עץ חיפוש בינארי המקיים תכונה נוספת: **תכונת האיזון**. תכונה זו קובעת שלכל קדקוד בעץ, הפרש הגבהים בין תת-העץ השמאלי שלו לתת-העץ הימני שלו (הנקרא **גורם האיזון**) הוא לכל היותר 1 בערכו המוחלט. לכן, האלגוריתם צריך לבדוק את שני התנאים: 1. האם העץ הוא עץ חיפוש בינארי. 2. האם העץ מקיים את תכונת האיזון. ניתן לשלב את שתי הבדיקות במעבר רקורסיבי אחד על העץ (סריקה סופית - post-order). נכתוב פונקציה רקורסיבית שתחזיר עבור כל קדקוד את גובהו, או ערך מיוחד (למשל, -1) אם תת-העץ שלו אינו עץ AVL חוקי. הפונקציה `checkAVL(u)` תפעל כך: 1. מקרה בסיס: אם `u` הוא `null`, נחזיר 0 (גובה של עלה "דמיוני"). 2. נקרא רקורסיבית `leftHeight = checkAVL(u.left)` ו-`rightHeight = checkAVL(u.right)`. 3. אם אחת הקריאות החזירה -1, פירוש הדבר שתת-עץ אינו חוקי, ולכן נחזיר מיד -1. 4. נבדוק את **תכונת האיזון** בקדקוד `u`: אם $|leftHeight - rightHeight| > 1$, נחזיר -1. 5. נבדוק את **תכונת עץ החיפוש הבינארי**: - אם קיים בן שמאלי, נוודא שערכו קטן מערך `u`. - אם קיים בן ימני, נוודא שערכו גדול מערך `u`. - *חשוב*: בדיקה זו אינה מספיקה. היא אינה מבטיחה שכל הקדקודים בתת-העץ השמאלי קטנים מ-`u`. לכן, גישה פשוטה יותר היא להפריד את הבדיקות: ראשית לוודא שהעץ הוא עץ חיפוש בינארי (כמו בסעיף א'), ורק אז להפעיל רקורסיה נפרדת הבודקת את תכונת האיזון. **אלגוריתם מפוצל (מומלץ):** 1. הרץ את האלגוריתם מסעיף א' לבדוק אם העץ הוא עץ חיפוש בינארי. אם לא, החזר "לא". 2. אם כן, הרץ פונקציה רקורסיבית הבודקת את תכונת האיזון ומחשבת גובה. הפונקציה `getHeightAndCheckBalance(u)` תחזיר את גובה תת-העץ או ערך מיוחד (כמו -1) אם הוא אינו מאוזן. לכל קדקוד `u`, היא תקרא לעצמה על הבנים, תקבל את גובהם, תבדוק את הפרש הגבהים, ואם הוא תקין, תחזיר את גובה `u` (`1 + max(leftHeight, rightHeight)`). 3. אם הקריאה הראשונית ל-`getHeightAndCheckBalance` על השורש מחזירה ערך שאינו שלילי, העץ הוא עץ AVL. אחרת, לא. **סיבוכיות:** * **סיבוכיות זמן:** בדיקת היותו עץ חיפוש בינארי היא $O(n)$. בדיקת תכונת האיזון דורשת גם היא מעבר על כל קדקודי העץ, ולכן סיבוכיותה $O(n)$. הסיבוכיות הכוללת היא $O(n) + O(n) = O(n)$. * **סיבוכיות מקום:** בדומה לסעיף א', סיבוכיות המקום היא $O(h)$ (גובה העץ) עקב עומק הרקורסיה. במקרה הגרוע $O(n)$.