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

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

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

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

הגדרות

עץ חיפוש בינרי (או 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, קל לחפש צומת עם מפתח נתון בעץ. מתחילים בשורש, ויורדים (אם יש צורך) שמאלה או ימינה בהתאם לייחס בין המפתח בצומת לערך המבוקש.

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

# 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

תבנית:משפט

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

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

הכנסה

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

# 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

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

נניח שאנו מחזיקים (מצביע ל)צומת תבנית:קוד בשורה. כיצד נוכל למצוא את (המצביע ל)צומת בעל המפתח הקטן ביותר בתת-העץ שלו? לפי תכונת ה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

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

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

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

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

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

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

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

אפשרות א'

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

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

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

אפשרות ב'

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

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

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

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

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

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

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

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

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

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

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

לכן, אם יש ל$k$ בן ימני, בהכרח הצומת המבוקש הוא הצאצא השמאלי ביותר של אותו הבן הימני. לחלופין, אם אין בן ימני, יש צורך למצא את ההורה הימני הראשון של $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

מחיקה

הקדמה

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

פעולת ה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

תבנית:מבנה תבנית

תבנית:משפט

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

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

מעבר 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.

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

סיכום

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

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

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס