עץ אדום שחור

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דוגמה לעץ אדום-שחור, שהינו עץ מאוזן, אשר בו כל הקודקודים בעומק 0 ו-2 צבועים בשחור, וכל הקודקודים בעומק 1 ו-3 צבועים באדום

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

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

הסבר פשוט[עריכת קוד מקור | עריכה]

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

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

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

רקע היסטורי[עריכת קוד מקור | עריכה]

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

טרמינולוגיה[עריכת קוד מקור | עריכה]

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

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

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

מאפיינים[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

פעולות[עריכת קוד מקור | עריכה]

  • הכנסה (Insert): הכנסת איבר לעץ, בצורה שתשמור על איזונו. ניתן לבצע בזמן של \ O(\log n).
  • הסרה (Remove): הסרת איבר מבוקש מהעץ. ניתן לבצע בזמן של \ O(\log n).

"תיקון העץ" הוא \ O(\log n) במקרה הגרוע, אך בניתוח לשיעורין הוא לוקח \ O(1) בלבד.

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

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

רוטציה[עריכת קוד מקור | עריכה]

רוטציה

נתון צומת אב X שלו שני בנים: שמאלי Z וימני Y. גם ל-Y שני בנים: שמאלי A וימני B, כנ"ל עם Z שבניו בהתאמה C ו-D.

לאחר רוטציה ימנית, X יהיה בנו השמאלי של Y, כאשר A יהפוך להיות בנו הימני של X.

לעומת זאת, לאחר רוטציה שמאלית, X יהיה בנו הימני של Z, כאשר D יהיה בנו השמאלי של X.

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

במחיקת צומת משתמשים באלגוריתם מסובך עוד יותר, אך גם הוא מתבצע ב-\ O(\log n) פעולות.

שימושים ויישומים[עריכת קוד מקור | עריכה]

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]