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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

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

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


הצמתים ה"חשודים"[עריכה]

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

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

אפשרות א'[עריכה]

נתבונן בצאצאים של (אם יש לו).


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

Dsa binary search tree succ 1.png

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


שימו לב:

ייתכנו כמובן מצבים בהם לצומת אין צאצאים ימניים. במקרים אלה, אין צומת כמתואר כאן.

אפשרות ב'[עריכה]

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

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

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


Dsa binary search tree succ path up.png

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

Dsa binary search tree succ path up 1.png

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

Dsa binary search tree succ path up 2.png


שימו לב:

ייתכנו כמובן מצבים בהם לצומת אין הורים ימניים. במקרים אלה, אין צומת כמתואר כאן.

נמשיך בקטע המסלול השני, ונניח ש הוא צומת בקטע זה (כמוראה בתרשים הבא). בוודאי אינו הצומת שאנו מחפשים - ככלות הכל, מפתחו גדול מ. מסיבה זו, בודאי שכל צאצא ימני של אינו הצומת שאנו מחפשים.


Dsa binary search tree succ path up 3.png

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

Dsa binary search tree succ path up 4.png

באופן דומה, נעבור לקטע המסלול הרביעי, ונניח ש הוא צומת בקטע זה (כמוראה בתרשים הבא). בוודאי אינו הצומת שאנו מחפשים - ככלות הכל, מפתחו גדול מ. מסיבה זו, בודאי שכל צאצא ימני של אינו הצומת שאנו מחפשים.

Dsa binary search tree succ path up 5.png

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



משפט:

נניח ש הוא הורה של . אז , וכן כל צומת שהוא צאצא של בכוון ההפוך לזה של , מכיל מפתח גדול מ או קטן מ.


היחס בין הצמתים ה"חשודים"[עריכה]

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

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

פסוודו-קוד[עריכה]

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


# 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




משפט:

סיבוכיות הפעולה היא במקרה הגרוע, כאשר הוא גובה העץ.