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

משפט כללי

כדי לפתור את התשובה, נוכיח ראשית את המשפט הפשוט הבא:

משפט: בעץ חיפוש בינרי בעל מפתחות שונים זה מזה, נניח שצומת $\displaystyle a$ מחזיק מפתח כלשהו. אז: הצאצאים השמאליים של $\displaystyle a$ מכילים כולם מפתחות קטנים ל$\displaystyle a$. יש עוד צמתים עם מפתחות קטנים מ$\displaystyle a$ מעבר לכך אם ורק אם $\displaystyle a$ הוא צאצא ימני (לאו דווקא ישיר) של צומת כלשהו.

להלן דוגמה למה שהמשפט אומר.

דוגמה: בתרשים הבא, $\displaystyle a$ אינו צאצא ימני של אף צומת. צמתי המפתחות הקטנים ממנו (הצבועים באפור), כולם בתת העץ הימני שלו. מיקום צמתים בעלי מפתחות קטנים מצומת נתון - לא צאצא ימני. לעומת זאת, בתרשים הבא, $\displaystyle a$ הוא צאצא ימני (לא ישיר) של $\displaystyle b$. צמתי המפתחות הקטנים ממנו (הצבועים באפור), בתת העץ הימני שלו וגם בתת העץ השמאלי של $\displaystyle b$. מיקום צמתים בעלי מפתחות קטנים מצומת נתון - צאצא ימני.

עכשיו תורכם: השתמש בתכונת הBST כדי להוכיח את המשפט.

הקשר ללא מידע נוסף

מהמשפט הכללי ברור שאי אפשר לקבוע האם הצומת של $\displaystyle y$ הוא צאצא של הצומת של $\displaystyle x$. ייתכן שהצומת של $\displaystyle y$ הוא צאצא שמאלי של הצומת של $\displaystyle x$, אך אם הצומת של $\displaystyle x$ הוא צאצא ימני של צומת כלשהו, ייתכן שהצומת של $\displaystyle y$ הוא צאצא שמאלי של אותו הצומת.

הקשר עם מידע נוסף

ראשית, ברור שכל אחד בנפרד מסדרו של צומת במעבר in-order,‏ post-order,‏ או מספר צאצאיו, אינו מספיק כדי לקבוע יחס צאצא-אב.

נתבונן שוב במקרה בו צומת $\displaystyle a$ הוא צאצא ימני של צומת $\displaystyle b$.

מיקום צמתים בעלי מפתחות קטנים מצומת נתון - צאצא ימני.

1. אם $\displaystyle y<x$, אז $\displaystyle y$ יודפס לפני $\displaystyle x$ במעבר in-order בכל מקרה. אבל אם $\displaystyle x=a$, אז $\displaystyle y$ יכול להיות צאצא שמאלי של $\displaystyle x$, או צאצא שמאלי של הורה של $\displaystyle x$ (לדוגמה $\displaystyle b$).
2. באופן דומה, אם $\displaystyle y<x$, אז $\displaystyle y$ יודפס לפני $\displaystyle x$ במעבר post-order בכל מקרה. אבל שוב, אם $\displaystyle x=a$, אז $\displaystyle y$ יכול להיות צאצא שמאלי של $\displaystyle x$, או צאצא שמאלי של הורה של $\displaystyle x$ (לדוגמה $\displaystyle b$).
3. כפי שהתרשים מראה, אם $\displaystyle x<y$, אין בהכרח שום קשר בין מספר האיברים בתת-העץ של $\displaystyle x$ לבין זה של $\displaystyle y$.

לעומת זאת, השילוב של סדר post-order וdescendants מספיק.

משפט: נגדיר: $\displaystyle p_{l}$ הוא מספר הpost-order של ילדו השמאלי של $\displaystyle x$. $\displaystyle d_{l}$ הוא מספר הdescendants של ילדו השמאלי של $\displaystyle x$. אז כל צומת בתת העץ השמאלי הוא בעל מספר post-order ב$\displaystyle \left\{p_{l}-d_{l}+1,\ldots ,p_{l}\right\}$.

הוכחה: מספרי הpost-order של ילדו השמאלי של $\displaystyle x$ הם $\displaystyle d_{l}$ מספרים עוקבים, שהאחרון שבהם הוא $\displaystyle p_{l}$.

מהמשפט האחרון ברור כיצד יש למצוא האם צומת כלשהו nd-y הוא צאצא של צומת כלשהו nd-x, בהנחה שתוכן הראשון הוא $\displaystyle y$, תוכן השני הוא $\displaystyle x$, ו$\displaystyle y<x$:

1. אם לnd-x אין ילד שמאלי - התשובה שלילית.
2. אחרת:
   1. קובעים כ$\displaystyle p_{l}$ את Postorder-Num(nd.l-child).
   2. קובעים כ$\displaystyle d_{l}$ את Descendants(nd.l-child).
   3. בודקים האם {Postorder-Num(nd-y) גדול או שווה ל$\displaystyle p_{l}-d_{l}+1$.

עכשיו תורכם: חשוב האם שילובי פונקציות שונים יפתרו את הבעיה גם כן.