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

יהי $T$ עץ בינארי עם $n$ צמתים. נסמן ב־$L_v$ את תת העץ ששורשו הבן השמאלי של $v$ ונסמן ב־$R_v$ את העץ ששורשו הבן הימני של $v$. קודקוד יקרא 'מאוזן' אם מתקיים התנאי הבא: $||L_v| - |R_v|| \le 5$ כאשר $|X|$ מסמן את מספר הקודקודים בעץ $X$. כתוב/י אלגוריתם יעיל למציאת כל הקודקודים $v$ בעץ $T$ שהם עצמם אינם מאוזנים, אבל כך שכל צאצאיהם כן מאוזנים. מה הסיבוכיות של האלגוריתם?

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

פתרון: כדי למצוא את כל הצמתים המבוקשים, נשתמש ב**אלגוריתם רקורסיבי** המבוסס על סריקת העץ. הסריקה המתאימה ביותר היא **סריקה תת-סדרית (post-order traversal)**, מכיוון שכדי לקבוע את תכונותיו של צומת $v$ (גודל תתי-העצים שלו והאם צאצאיו מאוזנים), עלינו לעבד תחילה את ילדיו. נגדיר פונקציה רקורסיבית, `CheckBalance(v)`, אשר רצה על תת-העץ ששורשו $v$. הפונקציה תחזיר זוג ערכים: `(size, all_balanced)`. 1. `size`: מספר הצמתים הכולל בתת-העץ ששורשו $v$. 2. `all_balanced`: ערך בוליאני המציין האם *כל* הצמתים בתת-העץ ששורשו $v$ (כולל $v$ עצמו) הם 'מאוזנים'. בנוסף, האלגוריתם ישתמש ברשימה גלובלית, `result_nodes`, כדי לאסוף את כל הצמתים שעונים על תנאי הבעיה. **תיאור האלגוריתם:** הפונקציה `CheckBalance(v)` תפעל באופן הבא: 1. **מקרה בסיס:** אם הצומת $v$ הוא `null` (כלומר, הגענו מעבר לעלה), הפונקציה תחזיר `(0, true)`. תת-עץ ריק הוא בגודל 0, והתנאי שכל צמתיו מאוזנים מתקיים באופן ריק. 2. **שלב רקורסיבי:** א. קוראים לפונקציה באופן רקורסיבי על הבן השמאלי והימני: - `(left_size, left_subtree_is_balanced) = CheckBalance(v.left)` - `(right_size, right_subtree_is_balanced) = CheckBalance(v.right)` ב. לאחר חזרת הקריאות הרקורסיביות, יש בידינו את גודל תתי-העצים של $v$ ואת המידע האם כל אחד מתתי-העצים הללו מכיל רק צמתים מאוזנים. נבדוק את התנאי המבוקש בשאלה עבור הצומת הנוכחי $v$: - **האם $v$ אינו מאוזן?** התנאי הוא $||left\_size| - |right\_size|| > 5$. - **האם כל צאצאיו של $v$ מאוזנים?** צאצאיו של $v$ הם כל הצמתים בתתי-העצים שלו. התנאי הזה מתקיים אם ורק אם `left_subtree_is_balanced` וגם `right_subtree_is_balanced` הם `true`. - אם שני התנאים מתקיימים, נוסיף את הצומת $v$ לרשימה `result_nodes`. ג. כעת, נחשב את הערכים שהפונקציה צריכה להחזיר עבור הצומת $v$ עצמו: - `my_size = 1 + left_size + right_size`. - `is_v_balanced = ||left_size| - |right_size|| <= 5`. - תת-העץ של $v$ מכיל רק צמתים מאוזנים אם ורק אם $v$ עצמו מאוזן וגם כל אחד מתתי-העצים שלו מכיל רק צמתים מאוזנים. לכן: `my_subtree_is_balanced = is_v_balanced AND left_subtree_is_balanced AND right_subtree_is_balanced`. ד. הפונקציה תחזיר את הזוג `(my_size, my_subtree_is_balanced)`. האלגוריתם הראשי יאתחל רשימה ריקה `result_nodes` ויקרא ל-`CheckBalance` על שורש העץ $T$. בסיום, הרשימה `result_nodes` תכיל את כל הצמתים המבוקשים. **ניתוח סיבוכיות:** * **סיבוכיות זמן:** האלגוריתם מבקר בכל צומת בעץ פעם אחת בדיוק. בכל צומת מבוצע מספר קבוע של פעולות (חיסור, השוואה, חיבור, פעולות בוליאניות). לכן, **סיבוכיות הזמן** היא $O(n)$, כאשר $n$ הוא מספר הצמתים בעץ. * **סיבוכיות מקום:** סיבוכיות המקום תלויה בעומק מחסנית הקריאות הרקורסיביות, שהוא פרופורציונלי לגובה העץ, $h$. במקרה הגרוע (עץ מנוון), גובה העץ הוא $O(n)$. לכן, **סיבוכיות המקום** היא $O(h)$, שבמקרה הגרוע היא $O(n)$.