עץ אדום שחור

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

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

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

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

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

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

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

מבנה הנתונים המקורי הומצא בשנת 1972 על ידי רודולף באייר אשר קרא לו "עץ B בינארי סימטרי" (באנגלית: symmetric binary B-tree) ואת שמו המקורי קיבל במאמר שנכתב על ידי רוברט סדגוויק וליאונידס גויבס בשנת 1978.

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

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

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

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

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

חלק מהמימושים דורשים מאפיין נוסף: 6. השורש הוא שחור. מאפיין זה לעיתים מושמט מכיוון שצבע השורש תמיד יכול להשתנות מאדום לשחור אך לא תמיד להפך והשפעתו על ניתוח הסיבוכיות זניחה, אך מסבכת את ההסבר על "גלגול" בצורה משמעותית).^[1]

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

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

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

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

• פעולת החיפוש (Search) מתבצעת בדיוק כמו בעץ חיפוש בינארי סטדנרטי בסבוכיות ${\displaystyle \ O(\log n)}$ואינה דורשת התאמות.
• הכנסה (Insert), והסרה (Remove) של צמתים לעץ מתבצעות בדומה לעץ חיפוש בינארי בסבוכיות ${\displaystyle \ O(\log n)}$(ראה קוד בהמשך), ולאחר מכן יש לבצע "איזון" לעץ.
• "איזון העץ" (rebalancing) : ביצוע ${\displaystyle \ O(\log n)}$החלפות צבע למספר צמתים, ולכל היותר 3 (2 להכנסה) פעולות רוטציה מתבצע בסיבוכיות ${\displaystyle \ O(\log n)}$ במקרה הגרוע, אך במקרה הממוצע לוקח ${\displaystyle \ O(1)}$בלבד.

שינוי המבנה נקרא רוטציה. קיימים שני סוגים של רוטציה: רוטציה ימנית (Right-Rotate), ורוטציה שמאלית (Left-Rotate).

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

פעולת הרוטציה היא פעולת עזר, ניתן להבינה באמצעות הדוגמה הבאה:

נתון צומת אב N ולו שני בנים: L שמאלי, R ימני. ל־L ישנם שני בנים: S שמאלי, Y ימני.

לאחר רוטציה ימנית L יהפוך להיות האב, S יישאר בנו השמאלי, N יהה בנו הימיני ול N יהיו שני בנים: R ימני, Y שמאלי.

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

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

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

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

פסודו קוד (לא מדויק, ישוכתב בקרוב):

1. הכנסת איבר חדש X לעץ – על פי אלגוריתם סטנדרטי של הכנסה לעץ חיפוש בינארי (X יהפוך לעלה חדש של העץ).
2. צביעת X באדום.
3. כל עוד X אינו השורש וגם אביו של X אדום בצע:
   1. אם הדוד אדום בצע:
      1. צביעת הדוד של X בשחור.
      2. צביעת האבא של X בשחור.
      3. צביעת הסבא של X באדום.
      4. כעת X מצביע לסבא של X.
   2. אחרת (הדוד שחור או לא קיים) בצע:
      1. אם האבא של X הוא בן שמאלי בצע:
         1. אם X הוא בן ימני בצע:
            1. כעת X מצביע לאבא של X.
            2. רוטציה שמאלית ל-X.
         2. צביעת אבא של X בשחור.
         3. צביעת סבא של X באדום.
         4. רוטציה ימנית לסבא של X.
      2. אחרת (אבא של X בן ימני) בצע:
         1. אם X הוא בן שמאלי בצע:
            1. X מצביע לאבא של X.
            2. רוטציה ימנית ל-X.
         2. צביעת אבא של X בשחור.
         3. צביעת סבא של X באדום.
         4. רוטציה שמאלית לסבא של X.
4. צביעת השורש בשחור.

אם לצומת שנמחקת יש בדיוק 2 ילדים : ניתן להחליף את הצומת עם הצומת היורשת שלו (הבן השמאלי ביותר, בתת-עץ הימני), ולמחוק אותה. [מכיוון שהיורש הוא שמאלי ביותר,אין לו בנים שמאלים]

אם לצומת שנמחקת יש בדיוק ילד אחד, ניתן לצבוע את הבן בשחור, ולשים את הבן במקום הצומת שנמחקת. [הילד חייב היה להיות אדום, והאב היה שחור לפי מאפין 3, ומאפין 5]

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

אם לצומת שנמחקת אין ילדים והוא אדום, מחק אותו.

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

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

מבנה זה דומה לעץ 2-3-4, יפורט בהמשך

מבנה זה דומה לעץ AVL, יפורט בהמשך

מדיה וקבצים בנושא עץ אדום שחור בוויקישיתוף

• אוסף מצגות, הדגמות ותרגילים עם פתרונות בנושא עצי אדום-שחור
• הרצאה של רוברט סדג'וויק על גרסה חדשה (2008) של עצי אדום שחור
• הדגמה ויזואלית אינטראקטיבית של הכנסות והוצאות בעץ אדום שחור
• עץ אדום שחור, באתר MathWorld (באנגלית)