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

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

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

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

נניח שבעץ חיפוש בינרי יש $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

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

תבנית:הארה

תכונות

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

המשפט הבא מראה ש$h=\mathrm{\Theta }(h_b)$.

תבנית:הוכחה

המשפט הבא מראה ש$h_b=\mathrm{\Theta }(\log (n))$.

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

תבנית:הוכחה

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

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

הכנסה

הקדמה

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

הבעיה

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

# 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 לעץ אדום-שחור תקין.

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

תיקון

הפונקציה הבאה, תבנית:קוד בשורה, מתקנת את אינווריאנטה 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

תבנית:שימו לב

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

Red-Root-Child מקרה

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

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

תבנית:משפט

Red-Uncle מקרה

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

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

תבנית:משפט

מקרה Zig-Zig

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

Zig-Zag מקרה

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

מחיקה

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

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

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