עץ אדום שחור – הבדלי גרסאות

[[קובץ:Red-black tree example.svg|שמאל|ממוזער|400px|דוגמה ל'''עץ אדום-שחור''', שהינו עץ מאוזן, אשר בו כל הקודקודים בעומק 0 ו-2 צבועים בשחור, וכל הקודקודים בעומק 1 ו-3 צבועים באדום]]

 

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

==מאפיינים==

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

 

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

 

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

* הכנסה (Insert): הכנסת איבר לעץ, בצורה שתשמור על איזונו. ניתן לבצע בזמן של <math>\ O(\log n)</math>.

* הסרה (Remove): הסרת איבר מבוקש מהעץ. ניתן לבצע בזמן של <math>\ O(\log n)</math>.

 

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

### צביעת הסבא של X באדום.

### כעת X מצביע לסבא של X.

### אם האבא של X הוא בן שמאלי בצע:

#### אם X הוא בן ימני בצע:

# צביעת השורש בשחור.

|}

 

==שימושים ויישומים==