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

יהיו $i, j$ זוג פרמטרים בצמצום. נסמן ב-$L_c$ את העץ השנירו הבן השמאלי של הקודקוד ה-$c$, ונסמן ב-$R_c$ את הקודקוד הימני. כמדדים ניתנים בהנחות התוכנית, אם $|L_c| - |R_c| \leq 5$ הבחנה. נסמן את משפחת הקודקודים בעץ $X$. מחוברים/אלגוריתמים יעילים למניעת כל הקודקודים בעץ $T$ בעץ חקירה המוגדר בעץ $X$. מה הסיבוכיות של האלגוריתם?

רמז: נתחו את תכונת האיזון של העץ כדי לחסום את גובהו. מהי נוסחת הנסיגה לגובה המקסימלי של עץ עם $n$ קודקודים המקיים את התכונה הנתונה?

פתרון: השאלה מנוסחת באופן שאינו ברור לחלוטין, אך ניתן להסיק כי מדובר בעץ חיפוש בינארי עם תכונת איזון מיוחדת, והמטרה היא לקבוע את סיבוכיות הזמן של אלגוריתם יעיל הפועל עליו, כגון חיפוש איבר. התכונה הנתונה היא שלכל קודקוד $c$ בעץ, ההפרש בין מספר הקודקודים בתת-העץ השמאלי ($|L_c|$) לבין מספר הקודקודים בתת-העץ הימני ($|R_c|$) הוא לכל היותר 5. כלומר: $||L_c| - |R_c|| \leq 5$. עץ בעל תכונה זו הוא סוג של **עץ מאוזן-משקלית** (Weight-Balanced Tree). הסיבוכיות של פעולות עיקריות בעץ חיפוש בינארי, כמו חיפוש, הכנסה ומחיקה, תלויה בגובה העץ, $h$. נוכיח כי תכונת האיזון הנתונה מבטיחה שהגובה יהיה לוגריתמי במספר הקודקודים, $n$, כלומר $h = O(\log n)$. **הוכחת גובה לוגריתמי:** יהי עץ המקיים את התכונה, ויהי $c$ קודקוד כלשהו בעץ. נסמן את מספר הקודקודים הכולל בתת-העץ ששורשו $c$ ב-$n_c$. מתקיים: $n_c = |L_c| + |R_c| + 1$. נניח, ללא הגבלת הכלליות, כי $|L_c| \geq |R_c|$. מהתנאי הנתון, $|L_c| - |R_c| \leq 5$, ולכן $|L_c| \leq |R_c| + 5$. נציב זאת בנוסחה לגודל תת-העץ: $n_c = |L_c| + |R_c| + 1 \leq (|R_c| + 5) + |R_c| + 1 = 2|R_c| + 6$. מכאן נובע כי גודל תת-העץ הקטן יותר, $|R_c|$, הוא לפחות $\frac{n_c - 6}{2}$. כעת נמצא חסם עליון על גודל תת-העץ הגדול יותר, $|L_c|$: $|L_c| = n_c - 1 - |R_c| \leq n_c - 1 - \frac{n_c - 6}{2} = \frac{2n_c - 2 - n_c + 6}{2} = \frac{n_c + 4}{2}$. כלומר, בכל קודקוד $c$, גודל כל אחד מתתי-העצים שלו הוא לכל היותר כחצי מגודל תת-העץ הכולל של $c$. אם נסמן ב-$h(n)$ את הגובה המקסימלי של עץ עם $n$ קודקודים המקיים את התכונה, נקבל את **נוסחת הנסיגה** הבאה: $h(n) \leq 1 + h(\lfloor \frac{n+4}{2} \rfloor)$ זוהי נוסחת נסיגה שפתרונה הוא $h(n) = O(\log n)$, מכיוון שבכל ירידה ברקורסיה גודל הבעיה (מספר הקודקודים) נחלק בקירוב ב-2. **מסקנה:** כיוון שגובה העץ חסום לוגריתמית, **סיבוכיות הזמן** של אלגוריתם יעיל לחיפוש, הכנסה או מחיקה היא $O(h) = O(\log n)$. אם כוונת השאלה הייתה לסרוק את כל הקודקודים בעץ (למשל, באמצעות **DFS** או **BFS**), הסיבוכיות הייתה $O(n)$, אך אז תכונת האיזון לא הייתה רלוונטית. ההקשר מרמז שהכוונה היא לפעולה התלויה בגובה העץ. $\blacksquare$