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

מבנה נתונים ואלגוריתמים

 

 

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

 

               struct t_red_black_node {
                   enum { red, black } colour;
                   void *item;
                   struct t_red_black_node *left,
                                    *right,
                                    *parent;
                   }

 

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

 

הגדרת עץ אדום-שחור

עץ אדום-שחור הוא עץ בינארי אשר ממלא את הדרישות הבאות:

 

1.      כל צומת הוא שחור או אדום.

2.      כל עלה (צומת NULL) הוא שחור.

3.      אם צומת הוא אדום, אזי שני ילדיו שחורים.

4.      כל מסלול פשוט מצומת לעלה שהוא צאצא שלו מכיל את אותו מספר של צמתים שחורים.

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

                       של יותר מצומת שחור אחד.

 

 

 

 

 


עץ אדום-שחור בסיסי

 

 

 

 

 

 

 

 

עץ אדום שחור בסיסי בתוספת צמתי פיקוח

(sentinel). יישומים של אלגוריתמים של עץ אדום-שחור

יכללו בדרך כלל צמתי פיקוח המציינים את ההגעה לעלה.

 

אלו צמתי NULL שחורים מסוג שני.

 

 

 

 

 

 

 

 

 

 

 

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

הגובה השחור של הצומת, המסומן כ-bh(x). ניתן להוכיח את הלמה הבאה:

 

למה:

עץ אדום שחור בעל n צמתים פנימיים הוא בעל גובה מקסימלי של 2log(n+1).

 

הדבר ממחיש מדוע עצים אלו אידיאליים כעצי חיפוש: זמן החיפוש הוא תמיד O(logn).

 

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

 

סיבובים

סיבוב הוא פעולה מקומית בעץ חיפוש אשר משמרת את סדר המפתחות במעבר in-order.

 

שים לב כי בשני העצים מעבר in-order נותן:

 A x B y C

 

 

 

 

 

 

 


זהו קוד אפשרי לסיבוב לשמאל:

 

               left_rotate( Tree T, node x ) {
                   node y;
                   y = x->right;
                   /* Turn y's left sub-tree into x's right sub-tree */
                   x->right = y->left;
                   if ( y->left != NULL )
                       y->left->parent = x;
                   /* y's new parent was x's parent */
                   y->parent = x->parent;
                   /* Set the parent to point to y instead of x */
                   /* First see whether we're at the root */
                   if ( x->parent == NULL ) T->root = y;
                   else
                       if ( x == (x->parent)->left )
                           /* x was on the left of its parent */
                           x->parent->left = y;
                       else
                           /* x must have been on the right */
                           x->parent->right = y;
                   /* Finally, put x on y's left */
                   y->left = x;
                   x->parent = y;
                   }

 

 

הכנסה

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

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

 

               rb_insert( Tree T, node x ) {
                   /* Insert in the tree in the usual way */
                   tree_insert( T, x );
                   /* Now restore the red-black property */
                   x->colour = red;
                   while ( (x != T->root) && (x->parent->colour == red) ) {
                      if ( x->parent == x->parent->parent->left ) {
                          /* If x's parent is a left, y is x's right 'uncle' */
                          y = x->parent->parent->right;
                          if ( y->colour == red ) {
                              /* case 1 - change the colours */
                              x->parent->colour = black;
                              y->colour = black;
                              x->parent->parent->colour = red;
                              /* Move x up the tree */
                              x = x->parent->parent;
                              }
                          else {
                              /* y is a black node */
                              if ( x == x->parent->right ) {
                                  /* and x is to the right */ 
                                  /* case 2 - move x up and rotate */
                                  x = x->parent;
                                  left_rotate( T, x );
                                  }
                              /* case 3 */
                              x->parent->colour = black;
                              x->parent->parent->colour = red;
                              right_rotate( T, x->parent->parent );
                              }
                          }
                      else {
                          /* repeat the "if" part with right and left
                             exchanged */
                      }
                   /* Colour the root black */
                   T->root->colour = black;
                   }

 

דוגמא לפעולת הכנסה

 

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

 

מושגים

 

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

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

 

 

המשך ל: עצי AVL                     חזור ל: תוכן עניינים