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

דף זה עוסק בעצי חיפוש בינריים.

עץ חיפוש בינרי, או BST‏ (binary search tree),‏ הוא מבנה נתונים שימושי מאד לשמירת קבוצת מפתחות כאשר:

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

כדאי לדעת: #תוכל לראות את הפסוודו-קוד המלא למבנה זה עצי חיפוש בינריים - פסוודו-קוד. בספר הקורס, הפרק "Binary Search Trees" (תתי פרקים 1-3) מכסה נושאים אלה.

מימוש C++ std::set, std::map

הגדרות

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

1. מפתח
2. (מצביע ל)אב
3. (מצביע ל)בן השמאלי
4. (מצביע ל)בן הימני

להלן הפסוודו-קוד לצומת:

Node
	# The key this node holds.
1	key

	# Parent.
2	parent

	# Left child.
3	l-child
	# Right child.
4	r-child


# Makes a node with a given key (k)
Make-Node(k)
1	nd = Node()

2	nd.key = k

3	nd.parent = nd.l-child = nd.r-child = Nil

4	return nd

למבנה המתאר את העץ עצמו יש שני שדות:

1. (מצביע ל)צומת השורש
2. שדה המציין את גודל העץ (כלומר, את מספר הצמתים בו)

להלן הפסוודו-קוד לעץ:

Binary-Search-Tree
	# The root (shoresh).
1	root
	# Number of nodes.
2	size


# Makes an empty BST.	
Make-Binary-Search-Tree()
1	t = Binary-Search-Tree()

2	t.root = Nil
3	t.size = 0

4	return t

הגדרה: עץ חיפוש בינרי חייב לקיים את תכונת הBST - לכל צומת x: אם y הוא צומת בתת העץ ה שמאלי של x, אז y.key $\leq$ x.key. אם y הוא צומת בתת העץ ה ימני של x.key $\leq$ y.key.

כדאי לדעת: זו אינה ההגדרה היחידה האפשרית לתכונת הBST. להלן שתי הגדרות אחרות אפשריות. הגדרה: עץ חיפוש בינרי חייב לקיים את תכונת הBST - לכל צומת x: אם y הוא צומת בתת העץ ה שמאלי של x, אז y.key $\leq$ x.key. אם y הוא צומת בתת העץ ה ימני של x.key $<$ y.key. הגדרה: עץ חיפוש בינרי חייב לקיים את תכונת הBST - לכל צומת x: אם y הוא צומת בתת העץ ה שמאלי של x, אז y.key $<$ x.key. אם y הוא צומת בתת העץ ה ימני של x.key $\leq$ y.key. ההבדלים הנגזרים משלוש ההגדרות קטנים למדי.

דוגמה: התרשים הבא מראה שני עצי חיפוש בינריים לקבוצת המפתחות $\displaystyle \{2,3,5,5,7,8\}$: עץ חיפוש בינרי.

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

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

דוגמה: בתרשים הקודם, A הוא בעל גובה 3, וB הוא בעל גובה 4.

חיפוש

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

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

# Searches a tree (t) for a key (k).
# Returns a (pointer to a) node containing an equivalent key to k
#	if t has one; Nil otherwise.
Find(t, k)
1	nd = t.root

2	while nd != Nil
3		if k < nd.key
4			nd = nd.l-child
5		else if k > nd.key
6			nd = nd.r-child
7		else
8			return nd
		
9	return Nil

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

נוכל לכתוב פונקציה Member, המקבלת עץ ומפתח, ומחזירה האם המפתח נמצא בקבוצת האיברים של העץ.

# Searches a tree (t) for a key (k).
# Returns whether the tree contains the key.
Member(t, k)
1	return Find(t, k) != Nil

הכנסה

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

דוגמה: אם מכניסים את 4 לעץ בA שבתרשים הבא, מקבלים את B. הכנסה לעץ חיפוש בינרי.

# Inserts a key (k) to a tree (t).
Insert(t, k)
1	++t.size
	
2	parent = Nil
3	nd = t.root
	
4	while nd != Nil
5		parent = nd
		
6		nd = k < nd.key ? nd.l-child : nd.r-child
		
7	new-nd = Make-Node(k)
	
8	if parent == Nil
9		t.root = New_nd
10		return
 
11	if k < parent.key
12		parent.l-child = new-nd
13	else
14		parent.r-child = new-nd
			
15	new-nd.parent = parent

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

מינימום ומקסימום

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

להלן הפסוודו-קוד המתאים.

# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the minimum node in the subtree of nd.
Min(nd)
1	while nd.l-child != Nil
2		nd = nd.l-child
	
3	return nd


# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the maximum node in the subtree of nd.
Max(nd)
1	while nd.r-child != Nil
2		nd = nd.r-child
	
3	return nd

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

מציאת הצומת הבא והקודם

כעת נראה כיצד למצוא את הצומת הבא (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$ הוא גובה העץ.

מחיקה

הקדמה

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

פעולת הsplice

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

דוגמה: התרשים הבא מראה כיצד להוציא את הצומת בעל המפתח 7: splice בעץ חיפוש בינרי.

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

# Splices (removes) a node (nd) from a tree (t).
# The node (nd) must not have two children.
Splice(t, nd)
1	child = nd.l_child == Nil ? nd.r-child : nd.l-child

2	parent = nd.parent

3	if child != Nil
4		child.parent = parent

5	if parent == Nil
6		t.root = child
7		return
	
8	if nd.key < parent.key
9		parent.l-child = child
10	else 
11		parent.r-child = child

האלגוריתם

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

משפט: אם לצומת יש בן ימני, אז לצאצא השמאלי ביותר של בנו הימני אין בן שמאלי.

כלומר, יוצא שתמיד נוכל להשתמש בפעולת splice:

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

# Erases a node (nd) from a tree (t).
Delete(t, nd)
1	--t.size	

2	if nd.l-child == Nil or nd.r-child == Nil
3		Splice(t, nd)
4		return
	
5	spliced = Min(nd.r-child)

6	Splice(t, spliced)

7	nd.key = spliced.key

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

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

פעולות למעבר על כל איברי העץ

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

מעבר Pre-Order

בצורת מעבר זו, כאשר מגיעים לצומת:

1. ראשית מדפיסים את (איבר) הצומת עצמו
2. לאחר מכן עוברים על תת העץ השמאלי שלו
3. לאחר מכן עוברים על תת-העץ הימני שלו

Pre-Order(nd)
1	if nd == Nil
2		return

3	Print(nd.value)

4	Pre-Order(nd.l-child)
5	Pre-order(nd.r-child)

התרשים הבא מראה את סדר המעבר בצומת:

מעבר pre-order.

מעבר Post-Order

בצורת מעבר זו, כאשר מגיעים לצומת:

1. ראשית עוברים על תת-העץ השמאלי שלו
2. לאחר מכן עוברים על תת העץ הימני שלו
3. לאחר מכן מדפיסים את (איבר) הצומת עצמו

Post-Order(nd)
1	if nd == Nil
2		return

4	Post-Order(nd.l-child)
5	Post-order(nd.r-child)

3	Print(nd.value)

התרשים הבא מראה את סדר המעבר בצומת:

מעבר post-order.

מעבר In-Order

בצורת מעבר זו, כאשר מגיעים לצומת:

1. ראשית עוברים על תת-העץ השמאלי שלו
2. לאחר מכן מדפיסים את (איבר) הצומת עצמו
3. לאחר מכן עוברים על תת העץ הימני שלו

In-Order(nd)
1	if nd == Nil
2		return

3	In-Order(nd.l-child)

4	Print(nd.value)

5	In-order(nd.r-child)

התרשים הבא מראה את סדר המעבר בצומת:

מעבר in-order.

בשיעורי הבית תתבקש להוכיח שצורת מעבר זו תדפיס את כל איברי העץ בסדר עולה.

סיכום

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

• אם $\displaystyle h$ ו$\displaystyle n$ באותו סדר גודל, הרי שקיבלנו מבנה נתונים שאינו יעיל משמעותית מרשימה מקושרת.
• אם נוכל לנהל את המבנה כך ש$\displaystyle h$ יהיה קטן יחסית ל$\displaystyle n$, נקבל מבנה נתונים יעיל. הפרק עצים אדומים-שחורים עוסק בכך.

הפרק הקודם: תורים

עצי חיפוש בינריים תרגילים

הפרק הבא: עצים אדומים-שחורים