מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/חסם תחתון על אורך המסלול הארוך ביותר/תשובה

הוכחה א'

נגדיר את אורך המסלול הארוך ביותר כ$\displaystyle h$, ונשאל את השאלה הבאה: בעץ שגובהו (אורך המסלול הארוך ביותר משורש לעלה) $\displaystyle h$, כמה צמתים אפשר לשים לכל היותר?

נשים לב שאם יש צומת שאין לו שני ילדים, אפשר לבנות עץ גדול יותר על ידי הוספת ילד אליו. מכאן נקבל שהעץ המכיל את מספר הצמתים המקסימאלי מבין הצמתים שגובהם $\displaystyle h$, הוא עץ שבו כל מסלול משורש לעלה הוא בגובה $\displaystyle h$, ולכל צומת (למעט העלים) יש שני ילדים.

בעץ כזה, ברמה הראשונה יש 1 צומת, ברמה הבאה 2 צמתים, וברמה ה$\displaystyle i$ יש $\displaystyle 2^{i-1}$ צמתים. נקבל שמספר הצמתים הוא $\displaystyle \sum _{i=1}^{h}2^{i-1}=2^{h}-1$. זה המספר המקסימאלי של הצמתים. לכן, עבור כל עץ שגובהו h ומספר צמתיו $\displaystyle n$, בהכרח מתקיים $\displaystyle n\leq 2^{h}-1\leq 2^{h}$. מלקיחת $\displaystyle \log$ משני האגפים נקבל $\displaystyle h=\Omega (\log(n))$.

הוכחה ב' (מבוססת על מגבלות דחיסה)

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

נגדיר את אורך המסלול הארוך ביותר כ$\displaystyle h$

נניח ש$\displaystyle a_{1},\ldots a_{n}$ היא קבוצת שמות שידועה לשולח ולמקבל. השולח רוצה להודיע על שם אחד מתוך הקבוצה הידועה. לדוגמה, קבוצת השמות יכולה להיות רשימת המתמודדים על נשיאות ארה"ב, וכתב עיתון מעוניין לשלוח למערכת את שם הזוכה.

משפט: בכל שיטת קידוד, יש הודעה אחת לפחות שארכה $\displaystyle \Omega (\log(n))$.

(הטענה נובעת משיקולים קומבינטוריים דומים מאד לאלה של החסם התחתון על מיון מבוסס-השוואות שראינו.)

מצד שני, כל עץ חיפוש בינרי יכול לשמש לקידוד צומת. השולח מחפש את הצומת בעץ, מהצומת למטה (כפי שראינו בחיפוש בעץ בינרי). בכל צומת, אם הוא פונה שמאלה הוא מסמן 0, ואם פונה ימינה, הוא מסמן 1. השולח משדר את רצף הביטים למקבל. ברור שהמקבל יכול מתוך רצף הביטים (והעץ) למצא את הצומת המתאים.

נשים לב שמספר הביטים שנשלח הוא בדיוק מספר הקשתות מצומת השורש לצומת הנבחר. לכן, יש לפחות מסלול אחד שארכו $\displaystyle \Omega (\log(n))$.