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

כעת נראה כיצד למצוא את הצומת הבא (successor באנגלית) והקודם (predecessor באנגלית). נניח לרגע שבעץ אין שני מפתחות זהים. אם אנו נמצאים בצומת כלשהו שמפתחו הוא $\displaystyle k$:

• הצומת הבא הוא הצומת שמפתחו הוא הקטן ביותר מבין המפתחות הגדולים מ$\displaystyle k$.
• הצומת הקודם הוא הצומת שמפתחו הוא הגדול ביותר מבין המפתחות הקטנים מ$\displaystyle k$.

מטעמי סימטריה, נדבר רק על הצומת הבא.

הצמתים ה"חשודים"

נניח שאנו בצומת שמפתחו $\displaystyle k$. איפה יכול להיות הצומת שמפתחו הוא הקטן ביותר מבין אלה שגדולים מ$\displaystyle k$? יש שתי אפשרויות:

• אפשרות א' - הצומת המבוקש הוא צאצא של הצומת בעל המפתח $\displaystyle k$.
• אפשרות ב' - לצומת המבוקש ולצומת בעל המפתח $\displaystyle k$ יש הורה משותף (או שהצומת המבוקש הוא בעצמו הורה של $\displaystyle k$).

אפשרות א'

נתבונן בצאצאים של $\displaystyle k$ (אם יש לו).

ברור למדי שהצאצאים היחידים הרלוונטיים הם הצאצאים הימניים; השמאליים הרי קטנים מ$\displaystyle k$.

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

שימו לב: ייתכנו כמובן מצבים בהם לצומת אין צאצאים ימניים. במקרים אלה, אין צומת $\displaystyle a$ כמתואר כאן.

אפשרות ב'

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

• אפס או יותר צמתים בכוון שמאלה ומעלה, ולאחר מכן
• אפס או יותר צמתים בכוון ימינה ומעלה, ולאחר מכן
• אפס או יותר צמתים בכוון שמאלה ומעלה, ולאחר מכן
• וכולי וכולי.

התרשים הבא מראה מסלול אפשרי.

נניח ש$\displaystyle x_{1}$ הוא צומת בקטע הראשון של המסלול (כמוראה בתרשים הבא). $\displaystyle x_{1}$ בוודאי אינו הצומת שאנו מחפשים - ככלות הכל, מפתחו קטן מ$\displaystyle k$. מסיבה זו, בודאי שכל צאצא שמאלי של $\displaystyle x_{1}$ אינו הצומת שאנו מחפשים.

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

שימו לב: ייתכנו כמובן מצבים בהם לצומת אין הורים ימניים. במקרים אלה, אין צומת $\displaystyle b$ כמתואר כאן.

נמשיך בקטע המסלול השני, ונניח ש$\displaystyle x_{2}$ הוא צומת בקטע זה (כמוראה בתרשים הבא). $\displaystyle x_{2}$ בוודאי אינו הצומת שאנו מחפשים - ככלות הכל, מפתחו גדול מ$\displaystyle b$. מסיבה זו, בודאי שכל צאצא ימני של $\displaystyle x_{2}$ אינו הצומת שאנו מחפשים.

נעבור לקטע המסלול השלישי, ונניח ש$\displaystyle x_{3}$ הוא צומת בקטע זה (כמוראה בתרשים הבא). $\displaystyle x_{3}$ בוודאי אינו הצומת שאנו מחפשים - ככלות הכל, מפתחו קטן מ$\displaystyle k$. מסיבה זו, בודאי שכל צאצא שמאלי של $\displaystyle x_{3}$ אינו הצומת שאנו מחפשים.

באופן דומה, נעבור לקטע המסלול הרביעי, ונניח ש$\displaystyle x_{4}$ הוא צומת בקטע זה (כמוראה בתרשים הבא). $\displaystyle x_{4}$ בוודאי אינו הצומת שאנו מחפשים - ככלות הכל, מפתחו גדול מ$\displaystyle b$. מסיבה זו, בודאי שכל צאצא ימני של $\displaystyle x_{4}$ אינו הצומת שאנו מחפשים.

לאחר מעט מחשבה, קל לראות שאפשר להוכיח (פורמלית, באינדוקציה) את המשפט הבא.

משפט: נניח ש$\displaystyle x_{i}$ הוא הורה של $\displaystyle b$. אז $\displaystyle x_{i}$, וכן כל צומת שהוא צאצא של $\displaystyle x_{i}$ בכוון ההפוך לזה של $\displaystyle b$, מכיל מפתח גדול מ$\displaystyle b$ או קטן מ$\displaystyle k$.

היחס בין הצמתים ה"חשודים"

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

לכן, אם יש ל$\displaystyle k$ בן ימני, בהכרח הצומת המבוקש הוא הצאצא השמאלי ביותר של אותו הבן הימני. לחלופין, אם אין בן ימני, יש צורך למצא את ההורה הימני הראשון של $\displaystyle k$.

פסוודו-קוד

הפסוודו-קוד הבא הוא תרגום ישיר של הרעיונות שהוצגו עד כה.

# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the "next" node.
Successor(nd)
1	if nd.r-child != Nil
2		return Min(nd.r_child)
	
3	parent = nd.parent

4	while parent != Nil and nd == parent.r-child
5		nd = parent
6		parent = parent.parent
	
7	return parent


# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the "previous" node.
Predecessor(nd)
1	if nd.l-child != Nil
2		return Max(nd.l_child)
	
3	parent = nd.parent

4	while parent != Nil and nd == parent.l-child
5		nd = parent
6		parent = parent.parent
	
7	return parent

משפט: סיבוכיות הפעולה היא $\displaystyle \Theta (h)$ במקרה הגרוע, כאשר $\displaystyle h$ הוא גובה העץ.