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

נתון עץ חיפוש בינרי שבו יש צומת שהמפתח בו $\displaystyle x$ וכן צומת שהמפתח בו $\displaystyle y$. נניח $\displaystyle y<x$.

1. האם בהכרח הצומת של $\displaystyle y$ הוא צאצא של הצומת של $\displaystyle x$?
2. רוצים לפתח שיטה לקבוע חד-חד משמעית האם $\displaystyle y$ הוא צאצא של הצומת של $\displaystyle x$ בזמן $\displaystyle O(1)$. נניח בנוסף שממשק הצומת הורחב, וכולל גם את In-Order-Num(nd) המחזיר את סדרו של nd במעבר in-order,‏ Post-Order-Num(nd) המחזיר את סדרו של nd במעבר post-order, וDescendants(nd), המחזיר את מספר הצאצאים הכולל בתת העץ של nd (כולל nd עצמו; לדוגמה אם לnd אין ילדים, אז מספר הצאצאים הוא 1).
   1. אנא הראה שאף פונקציה בנפרד איננה מספיקה לקבוע חד-משמעית יחס זה.
   2. אנא מצא שילוב פונקציות שיספיק לקביעה חד משמעית.