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

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

דף זה עוסק בעצים אדומים-שחורים. עץ אדום-שחור הוא סוג של עץ חיפוש בינרי, אלא שכל צומת מכיל עוד מידע המתאר את "צבעו". על ידי שימוש במידע זה, אפשר לגרום לעץ להיות בעל גובה לוגריתמי - כלומר, שהמרחק מהשורש לכל עלה הוא $\displaystyle O(\log(n))$ , כאשר $\displaystyle n$ הוא מספר הצמתים בעץ.

כדאי לדעת:

בספר הקורס, הפרק "Red-Black Trees" עוסק בנושאים אלה.

מימוש C++

std::set, std::map

עצים לוגריתמיים ומאוזנים

נניח שבעץ חיפוש בינרי יש $\displaystyle n$ צמתים.

הגדרה:

עץ הוא לוגריתמי אם המרחק הארוך ביותר משורש לעלה הוא $\displaystyle O(\log(n))$ .

את המשפט הבא אפשר להוכיח באופן דומה לחסם התחתון על מיון מבוסס-השוואות.

משפט:

לכל עץ בעל $\displaystyle n$ צמתים יש מסלול משורש לעלה באורך $\displaystyle \Omega (\log(n))$ .

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

הגדרה:

עץ הוא מאוזן אם הוא לוגריתמי.

כדאי לדעת:

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

הגדרות

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

Node
	# The key this node holds.
1	key
	
	# Parent.
2	parent
	
	# Left child.
3	l-child
	# Right child.
4	r-child
	
	# The color. This is the only addition to the
	#	node of a binary search tree.
5	color
	
	
# 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	nd.color = red
	
5	return nd

הגדרה:

אינווריאנטות עץ אדום שחור:

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

כדאי לדעת:

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

דוגמה:

להלן דוגמה לעץ שחור אדום תקין (כלומר אחד שמקיים את שתי האינווריאנטות):

תכונות

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

הגדרה:

הגובה השחור של עץ אדום-שחור, $\displaystyle h_{b}$ , מוגדר כמספר הצמתים השחורים המקסימלי משורש לעלה.

המשפט הבא מראה ש $\displaystyle h=\Theta (h_{b})$ .

משפט:

אם אורך המסלול מהשורש לעלה כלשהו הוא $\displaystyle h$ , אז $\displaystyle h_{b}\leq h\leq 2\cdot h_{b}+1$ .

הוכחה: נתבונן ברצף הצמתים השחורים במסלול כלשהו. מספר הצמתים השחורים הוא $\displaystyle h_{b}$ . מספר הצמתים האמיתי במסלול הוא לכל הפחות מספר זה, ולכן $\displaystyle h_{b}\leq h$ . מצד שני, כמה צמתים יכולים להיות לכל היותר במסלול? לאחר כל צומת שחור ייתכן שמופיע צומת אדום (מה שיביא אותנו ל $\displaystyle 2\cdot h_{b}$ ); בנוסף, ייתכן שמופיע עוד צומת אדום לפני הצומת השחור הראשון.

המשפט הבא מראה ש $\displaystyle h_{b}=\Theta (\log(n))$ .

משפט:

אם מספר הצמתים הוא $\displaystyle n$ , אז $\displaystyle 2^{h_{b}}-1\leq n\leq 2^{2\cdot h_{b}}-1$ .

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

משפט:

אם המרחק מהשורש לעלה כלשהו הוא $\displaystyle h$ , ומספר הצמתים הוא $\displaystyle n$ , אז $\displaystyle h=\Theta (\log(n))$ .

הוכחה: משני המשפטים הקודמים שהוכחנו:

$\displaystyle h=\Theta (h_{b})$
$\displaystyle h_{b}=\Theta (\log(n))$ לכן המשפט כאן נובע מטרנזיטיבות.

הנה הסיבה מדוע זו תכונה חיובית:

משפט:

בעץ אדום-שחור, הפעולות Find, Min, Max, Successor, וPredecessor - כולן $\displaystyle O(\log(n))$ .

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

הכנסה

הקדמה

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

הבעיה

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

# Inserts a key (k) to a tree (t).
Insert(t, k)
	# This code, except for the last line, is identical 
	#	to that of Insert in BST.

1	++t.size

2	parent = Nil
3	nd = t.root

4	while nd != Nil
5		parent = nd

6		nd = k red node.
7	new-nd = Make-Node(k)

8	if parent == Nil
9		t.root = New_nd
10	else 
11		if k <parent.key
12			parent.l-child = new-nd
13		else
14			parent.r-child = new-nd

	# Ah-ha! Here's something new.
15	Insert-Fixup(new-nd)

שימו לב:

צומת חדש תמיד אדום.

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

דוגמה:

הכנסת המפתח 2 לעץ, יוצרת בעיה:

משפט:

הכנסה אינה יכולה להפר את אינווריאנטות עץ חיפוש בינרי או את אינווריאנטה 2 לעץ אדום-שחור תקין.

תיקון

הפונקציה הבאה, Insert-Fixup, מתקנת את אינווריאנטה 1 ע"י "דחיפת" הפרת מעלה בעץ, כל עוד הצומת ואביו אדומים:

Insert-Fixup(t, nd)
1	while nd != t.root and nd.parent.color == red
2		if Is-Child-Of-Red-Root(nd)
3			Insert-Fixup-Child-Of-Red-Root(nd)
4			return
5		else if Has-Red-Uncle(nd)
6			Insert-Fixup-Red-Uncle(nd)
7			nd = nd.parent.parent
8		else if Is-Zig-Zig(nd)
9			Insert-Fixup-Zig-Zig(nd)
10			return
11		else
12			Insert-Fixup-Zig-Zag(nd)
13			return

שימו לב:

שים לב שהלולאה יכולה לפעול לכל היותר

\displaystyle \log(n)

פעמים.

עתה נראה את ארבעת המקרים המתוארים בפונקציה.

Red-Root-Child מקרה

מקרה זה פשוט מאד: nd הוא בנו (הישיר) של השורש האדום. פשוט הופכים את השורש לשחור.

דוגמה:

להלן דוגמה למקרה ולפתרון המתאים:

כדאי לדעת:

האותיות היווניות(

\displaystyle \alpha

,‏

\displaystyle \beta

,‏ ו

\displaystyle \gamma

) מציינות תתי-עצים לא ידועים, שיכולים להיות משהו החל מתת-עץ ריק ועד תת-עץ ענק.

משפט:

אם B הוא עץ תקין למעט הפרה של אינווריאנטה 1 בדיוק בB, אז הטרנספורמציה גורמת לB להיות תקין.

Red-Uncle מקרה

מקרה זה מתקיים כאשר המקרה הקודם אינו חל, וה"דוד" של nd הוא אדום. הפתרון הוא להפוך את האב והדוד לשחורים, ואת הסב לאדום.

דוגמה:

להלן דוגמה למקרה ולפתרון המתאים:

שימו לב:

הפתרון אמנם פותר את הבעיה אצל nd, אבל יכול ליצור הפרה של אינווריאנטה 11 אצל סבו. זו הסיבה שממשיכים בלולאה.

משפט:

אם C הוא עץ תקין למעט הפרה של אינווריאנטה 1 בB, אז הטרנספורמציה הופכת את C לתקין, אך אולי יוצרת הפרה של אינווריאנטה 1 אצל אביו של C.

מקרה Zig-Zig

מקרה זה חל כאשר המקרים הקודמים אינם חלים, ובנוסף, nd הוא בן שמאלי של בן שמאלי, או בן ימני של בן ימני.

שימו לב:

אם מקרה זה נבדק ע"י Insert-Fixup, אז

\displaystyle \delta

אינו תת-עץ בעל שורש אדום.

דוגמה:

להלן דוגמה למקרה ולפתרון המתאים:

משפט:

אם C הוא עץ תקין למעט הפרה של אינווריאנטה 1 בB, אז הטרנספורמציה הופכת את C לתקין, ואינה מייצרת אף הפרעה אצל אביו של C.

Zig-Zag מקרה

מקרה זה חל כאשר אף אחד ממקרים הקודמים אינו חל.

שימו לב:

אם מקרה זה מבוצע ע"י Insert-Fixup, אז

\displaystyle \delta

איננה תת עץ בעל שורש אדום, וכן A הוא בן שמאלי של בן ימני או בן ימני של בן שמאלי.

דוגמה:

להלן דוגמה למקרה ולפתרון המתאים:

משפט:

אם C הוא עץ תקין למעט הפרה של אינווריאנטה 1 בB, אז הטרנספורמציה מייצרת עץ תקין, ואיננה מייצרת הפרה אצל אביו של C.

מחיקה

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

כדאי לדעת:

אינטואיטיווית, התיקון להכנסה הוא "דחיפה" למעלה של "אדמומיות יתרה". באותו אופן, התיקון למחיקה הוא "דחיפה"

למעלה של "שחירות יתרה".

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

הפרק הקודם:
עצי חיפוש בינריים

עצים אדומים-שחורים

הפרק הבא:
טבלאות ערבול