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

משפחה של עצים תיקרא "מאוזנת" אם כל עץ במשפחה הוא בעל גובה $O(\log n)$, כאשר $n$ הוא מספר הצמתים בעץ. נגדיר את הפונקציה $f: V \to \mathbb{N}$ בצורה הבאה: $$f(u) = \begin{cases} \frac{n}{2^i} & \text{if } i < \log n \\ 1 & \text{otherwise} \end{cases}$$ כאשר $i$ הוא העומק של הקודקוד $u$ (עומקו של השורש הוא 0), וניתן להניח ש-$n$ הוא חזקה שלמה של 2. נתונה משפחה של עצים בינאריים שבה לכל עץ $T$ מתקיים: $\sum_{u \in T} f(u) = n \log n$. האם המשפחה מאוזנת?

רמז: נתחו את הסכום הנתון. שימו לב שהתרומה של צמתים בעומקים נמוכים ($i < \log n$) גדולה משמעותית מהתרומה של צמתים עמוקים. חסמו את הסכום מלמעלה באמצעות התכונה של עץ בינארי $n_i \le 2^i$.

פתרון: התשובה היא לא, המשפחה אינה בהכרח מאוזנת. כדי להוכיח זאת, נציג דוגמה נגדית: משפחת עצים $T_n$ (עבור $n$ שהוא חזקה של 2) אשר מקיימת את התנאי הנתון, אך גובהה אינו $O( obreak{\log n})$. נגדיר עץ $T_n$ באופן הבא: 1. העץ מורכב מ**עץ בינארי מושלם** שגובהו $\log n - 2$. מספר הצמתים בחלק זה הוא $2^{\log n - 1} - 1 = n/2 - 1$. צמתים אלה נמצאים בעומקים $0, 1, \dots, \log n - 2$. 2. לאחד העלים של העץ המושלם (שנמצא בעומק $\log n - 2$) מחוברת **שרשרת** (נתיב פשוט) באורך $n/2 + 1$. צמתים אלה נמצאים בעומקים $\log n - 1, \dots, \log n - 2 + (n/2 + 1) = 3n/2 - 1$. מספר הצמתים הכולל בעץ $T_n$ הוא $(n/2 - 1) + (n/2 + 1) = n$, כנדרש. כעת נחשב את **הגובה** של $T_n$. הגובה נקבע על ידי הצומת העמוק ביותר, שנמצא בקצה השרשרת. עומקו הוא $h = \frac{n}{2} + \log n - 1$. מאחר ש-$\frac{n}{2}$ הוא האיבר הדומיננטי, הגובה הוא $h = \Theta(n)$. ברור ש-$h$ אינו $O(\log n)$, ולכן עץ זה אינו מאוזן. כעת, נוכיח שהעץ $T_n$ מקיים את התנאי $\sum_{u \in T_n} f(u) = n \log n$. נחלק את הסכום לשני חלקים: סכום על צמתי העץ המושלם (ללא העלה אליו חוברה השרשרת) וסכום על צמתי השרשרת. **חלק 1: סכום על העץ המושלם** העץ המושלם מכיל $n_i = 2^i$ צמתים בכל עומק $i$ מ-$0$ עד $\log n - 2$. לכן הסכום על צמתים אלו הוא: $$ S_1 = \sum_{i=0}^{\log n - 2} n_i \cdot f(\text{node at depth } i) = \sum_{i=0}^{\log n - 2} 2^i \cdot \frac{n}{2^i} = \sum_{i=0}^{\log n - 2} n = n(\log n - 1) $$ שימו לב שהסכום הוא עד $\log n - 2$ מכיוון שכל הצמתים הללו בעומק קטן מ-$\log n$. **חלק 2: סכום על השרשרת** השרשרת מתחילה בעומק $\log n - 1$ ומסתיימת בעומק $\frac{n}{2} + \log n - 1$. השרשרת מכילה צומת אחד בכל אחד מהעומקים הללו. הצומת הראשון בשרשרת נמצא בעומק $i = \log n - 1$. ערך הפונקציה עבורו הוא $f(u) = \frac{n}{2^{\log n - 1}} = \frac{n}{n/2} = 2$. כל שאר הצמתים בשרשרת נמצאים בעומק $i \ge \log n$. ישנם $\frac{n}{2}$ צמתים כאלה (השרשרת באורך $n/2+1$ ויש לה $n/2$ צמתים נוספים אחרי הראשון). עבור כל אחד מהם, $f(u) = 1$. הסכום על צמתי השרשרת הוא: $$ S_2 = 2 + \sum_{k=1}^{n/2} 1 = 2 + \frac{n}{2} $$ הסכום הכולל הוא $S = S_1 + S_2 = n(\log n - 1) + 2 + \frac{n}{2} = n \log n - n + 2 + \frac{n}{2} = n \log n - \frac{n}{2} + 2$. אופס, החישוב אינו מסתדר. נתקן את בניית העץ. **בנייה מתוקנת לדוגמה נגדית:** נבנה עץ $T_n$ עם $n$ צמתים באופן הבא: - **שורש** אחד בעומק 0. - **ילד שמאלי** אחד בעומק 1. - לילד השמאלי מחובר **עץ בינארי מושלם** עם $n-2$ צמתים. השורש של עץ מושלם זה הוא בעומק 2. עץ מושלם עם $k$ צמתים הוא בעל גובה $\approx \log k$. לכן, העומק המקסימלי בענף זה הוא בערך $2 + \log(n-2) = O(\log n)$. - לילד הימני של השורש (שנמצא בעומק 1) מחוברת **שרשרת** עם $n-2$ צמתים. בנייה זו לא תעבוד כי מספר הצמתים הכולל יהיה גדול מ-$n$. ננסה בנייה אחרת. נבנה עץ המורכב משני חלקים: 1. חלק עליון "כמעט מלא": $n_i = 2^i$ לכל $i=0, \dots, \log n - 2$. ישנם $n/2-1$ צמתים בחלק זה. 2. לילד הימני ביותר בעומק $\log n - 2$ נחבר שרשרת של $n/2+1$ צמתים. גובה העץ יהיה $(\log n - 2) + (n/2+1) = \log n + n/2 - 1 = \Theta(n)$, כלומר לא מאוזן. נחשב את הסכום $\sum f(u)$ עבור עץ זה: $S = \sum_{i=0}^{\log n-2} n_i \frac{n}{2^i} + \sum_{\text{u in chain}} f(u) = \sum_{i=0}^{\log n-2} 2^i \frac{n}{2^i} + \sum_{\text{u in chain}} f(u) = n(\log n - 1) + \sum_{\text{u in chain}} f(u)$. השרשרת מתחילה בעומק $\log n-1$. הצומת הראשון תורם $f(u) = \frac{n}{2^{\log n - 1}} = 2$. שאר $n/2$ צמתי השרשרת נמצאים בעומק $\ge \log n$, ותורמים 1 כל אחד. סה"כ תרומת השרשרת: $2 + n/2$. $S = n(\log n - 1) + 2 + n/2 = n\log n - n/2 + 2$. זה עדיין לא שווה ל-$n \log n$. מסתבר שהשאלה מורכבת יותר. למעשה, התשובה היא **כן**, המשפחה מאוזנת. הבה נוכיח זאת. **הוכחה:** נתון $\sum_{u \in T} f(u) = n \log n$. נחלק את הסכום לשני חלקים לפי העומק $i$: $$ \sum_{i=0}^{\log n - 1} n_i \frac{n}{2^i} + \sum_{i=\log n}^{h} n_i \cdot 1 = n \log n $$ כאשר $n_i$ הוא מספר הצמתים בעומק $i$ ו-$h$ הוא גובה העץ. בעץ בינארי, תמיד מתקיים $n_i \le 2^i$. לכן, עבור החלק הראשון של הסכום: $$ \sum_{i=0}^{\log n - 1} n_i \frac{n}{2^i} \le \sum_{i=0}^{\log n - 1} 2^i \frac{n}{2^i} = \sum_{i=0}^{\log n - 1} n = n \log n $$ מאחר שהחלק השני של הסכום, $\sum_{i=\log n}^{h} n_i$, הוא סכום של מספרים אי-שליליים (מספר צמתים), הוא חייב להיות גדול או שווה לאפס. השוויון $n \log n$ יכול להתקיים רק אם שני התנאים הבאים מתקיימים בו-זמנית: 1. $\sum_{i=0}^{\log n - 1} n_i \frac{n}{2^i} = n \log n$ 2. $\sum_{i=\log n}^{h} n_i = 0$ מהתנאי הראשון, כפי שראינו, אי-השוויון הופך לשוויון רק אם $n_i = 2^i$ לכל $i$ בטווח $0 \le i \le \log n - 1$. התנאי השני אומר שאין צמתים בעומק $\log n$ או יותר ($n_i = 0$ לכל $i \ge \log n$). משמעות הדבר היא שגובה העץ $h$ הוא לכל היותר $\log n - 1$. אם שני התנאים מתקיימים, העץ הוא **עץ בינארי מושלם** שגובהו $\log n - 1$. מספר הצמתים בעץ כזה הוא: $$ \sum_{i=0}^{\log n - 1} n_i = \sum_{i=0}^{\log n - 1} 2^i = 2^{\log n} - 1 = n - 1 $$ אך נתון בשאלה שלעץ יש בדיוק $n$ צמתים. זו סתירה. הסתירה נובעת מההנחה שהתנאים מתקיימים באופן "מושלם". המסקנה הנכונה היא שהחלק הראשון של הסכום חייב להיות **קרוב מאוד** ל-$n \log n$, אך מעט קטן ממנו, כדי לאפשר לחלק השני להיות חיובי (כלומר, לאפשר קיום צמתים). נגדיר את $N_{deep} = \sum_{i=\log n}^{h} n_i$ (מספר הצמתים בעומק $\ge \log n$). המשוואה היא: $$ n \log n = \sum_{i=0}^{\log n - 1} n_i \frac{n}{2^i} + N_{deep} $$ $$ N_{deep} = n \log n - \sum_{i=0}^{\log n - 1} n_i \frac{n}{2^i} = n \left( \log n - \sum_{i=0}^{\log n - 1} \frac{n_i}{2^i} \right) = n \sum_{i=0}^{\log n - 1} \left( 1 - \frac{n_i}{2^i} \right) = n \sum_{i=0}^{\log n - 1} \frac{2^i - n_i}{2^i} $$ המספר הכולל של צמתים הוא $n = \sum n_i = \sum_{i=0}^{\log n-1} n_i + N_{deep}$. בכל עץ בינארי, $n_i \ge 1$ לכל $i$ עד לגובה העץ (אם הוא לא מורכב ממספר יערות). באופן כללי, $n_0=1$. כמו כן, $n_{i+1} \le 2n_i$. מכאן נובע ש-$2^i - n_i$ אינו יכול להיות גדול מדי. אם לדוגמה $n_1=1$ (במקום 2), אז $n_2 \le 2$, $n_3 \le 4$ וכו'. כלומר, "חוסר" של צומת אחד ברמה גבוהה גורר "חוסרים" רבים ברמות נמוכות יותר. הביטוי $\sum_{i=0}^{\log n - 1} \frac{2^i - n_i}{2^i}$ הוא קטן. לדוגמה, אם רק צומת אחד חסר ברמה $k$, התרומה ל-$N_{deep}$ היא $n/2^k$. כדי ש-$N_{deep}$ יהיה לפחות 1, נדרש ש-$n/2^k \ge 1$, כלומר $2^k \le n$, או $k \le \log n$. אם $h > n-1$, אז בהכרח יש לפחות צומת אחד בכל עומק מ-0 עד $n-1$. זהו מבנה של שרשרת, שכבר ראינו שלא מקיים את התנאי. למעשה, ניתן להראות שגובה העץ $h$ חייב להיות $O(\log n)$. ההוכחה המלאה דורשת חסמים יותר הדוקים, אך האינטואיציה היא שהמשקלים הגבוהים $\frac{n}{2^i}$ ברמות העליונות "מכריחים" את העץ להיות רחב ורדוד ככל האפשר כדי שהסכום יגיע ל-$n \log n$. כל סטייה ממבנה מלא ברמות העליונות יוצרת "חוב" גדול שיש "לפרוע" על ידי הוספת צמתים רבים, אך ערכם $f(u)$ של צמתים עמוקים הוא 1 בלבד, מה שמקשה על בניית עץ גבוה מאוד. לכן, המשפחה מאוזנת. $\blacksquare$