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

נוספו 48 בתים ,  לפני 7 שנים
עיצוב, הגהה
מ (r2.7.3) (בוט מוסיף: da:Rød-sort træ)
(עיצוב, הגהה)
ב[[מדעי המחשב]], '''עץ אדום-שחור''' (ב[[אנגלית]]: '''Red-Black Tree''') הינו [[מבנה נתונים]] מסוג [[עץ (תורת הגרפים)|עץ]] [[עץ חיפוש|חיפוש]] [[עץ בינארי|בינארי]] [[עץ מאוזן|מאוזן]].
 
'''עץ אדום-שחור''' הוא מבנה נתונים מורכב יחסית, אך בשל היותו [[עץ מאוזן|מאוזן]] הוא שומר על [[סיבוכיות]] [[סיבוכיות זמן|זמן ריצה]] טובה, יעילה ומעשית עבור הפעולות השונות הנתמכות: "הכנסה", "הוצאה" ו"חיפוש" בזמן של '''(<math>\ O(\log n''')</math>. במקרה הגרוע ביותר (כאשר <math>n</math> הוא מספר האיברים בעץ בעת ביצוע הפעולה).
 
שמו של העץ נובע מהתכונה הבאה שלו: בסיומה של כל פעולה (הכנסה, הוצאה, חיפוש) העץ מאוזן, כאשר כל הקודקודים בעלי עומק זוגי מסומנים/צבועים בצבע אחד (שחור), וכל יתר הקודקודים (בעלי עומק אי-זוגי) צבועים בצבע אחר (אדום). או במילים אחרות: בכל רגע נתון, עבור כל קודקוד הצבוע בצבע אחד - מתקיים כי כל הקודקודים הסמוכים אליו צבועים בצבע אחר.
==מאפיינים==
עץ אדום שחור הוא עץ בינארי בו לכל צומת קיים שדה המגדיר צבע, שערכו אדום או שחור. בנוסף לדרישות הרגילות של עצי חיפוש בינאריים, עץ אדום שחור מקיים גם את הדרישות הבאות:
:1. צומת הוא שחור או אדום (אחד מן השניים).
:2. השורש הוא שחור (כלל זה לעתים מושמט מכיוון שצבע השורש תמיד יכול להשתנות מאדום לשחור אך לא תמיד להפך, אך השפעתו על ניתוח הסיבוכיות קטנה בכל מקרה)
:3. כל העלים שחורים.
:4. שני ילדיו של צומת אדום הם שחורים.
:5. כל [[מסלול (תורת הגרפים)|מסלול פשוט]] מצומת מסוים לכל אחד מהצאצאים העלים שלו מכיל אותו מספר של צמתים שחורים.
 
אילוצים אלו כופים הגדרה משמעותית על עצים אדומים שחורים: אורכו של המסלול הארוך ביותר מהשורש לכל אחד מן העלים הוא לכל היותר פעמיים אורכו של המסלול הקצר ביותר מהשורש לאחד העלים. התוצאה היא שהעץ מספיק מאוזן כדי לשמור על [[סיבוכיות]] טובה של הפעולות השונות, מכיוון שפעולות אלה דורשות במקרה הגרוע ביותר זמן יחסי לגובה העץ, הגבלת גובה העץ מגבילה גם את סיבוכיות הפעולות.
 
==פעולות==
* הכנסה (Insert): הכנסת איבר לעץ, בצורה שתשמור על איזונו. ניתן לבצע בזמן של ((<math>\ O(\log(N n)</math>.
* הסרה (Remove): הסרת איבר מבוקש מהעץ. ניתן לבצע בזמן של ((<math>\ O(\log(N n)</math>.
 
הסרה (Remove): הסרת איבר מבוקש מהעץ. ניתן לבצע בזמן של ((O(log(N.
 
מכיוון שפעולות אלו משנות את העץ התוצאה עלולה להפר את התכונות של העץ. כדי לשמור על תכונות העץ עלינו לשנות את צבעיהם של כמה מן הצמתים, ואף את מבנה ההצבעה.
===רוטציה===
[[קובץ:Tree rotation.png|שמאל|ממוזער|250px|רוטציה]]
נתון צומת אב X שלו שני בנים: שמאלי- Z ,וימני ימני-Y . גם ל-Y שני בנים: שמאלי- A ,וימני ימני-B, ,כנ"ל עם Z שבניו בהתאמה C ו-D.
 
לאחר רוטציה ימנית, X יהיה בנו השמאלי של Y , כאשר A יהפוך להיות בנו הימני של X.
 
לעומת זאת, לאחר רוטציה שמאלית, X יהיה בנו הימני של Z , כאשר D יהיה בנו השמאלי של X.
 
===אלגוריתם להכנסת איבר חדש לעץ אדום-שחור===
משתמש אלמוני