עץ אדום שחור – הבדלי גרסאות
מ הורדת תבנית {{בעבודה}} |
מ r2.6.4) (בוט משנה: lt:Raudonai juodas medis |
||
שורה 90: | שורה 90: | ||
[[ja:赤黒木]] |
[[ja:赤黒木]] |
||
[[ko:레드-블랙 트리]] |
[[ko:레드-블랙 트리]] |
||
[[lt:Raudonai |
[[lt:Raudonai juodas medis]] |
||
[[nl:Rood-zwartboom]] |
[[nl:Rood-zwartboom]] |
||
[[pl:Drzewo czerwono-czarne]] |
[[pl:Drzewo czerwono-czarne]] |
גרסה מ־11:47, 26 במאי 2011
יש לפשט ערך זה: הערך מנוסח באופן טכני מדי, וקשה להבנה לקהל הרחב.
| ||
יש לפשט ערך זה: הערך מנוסח באופן טכני מדי, וקשה להבנה לקהל הרחב. | |
במדעי המחשב, עץ אדום-שחור (באנגלית: Red-Black Tree) הינו מבנה נתונים מסוג עץ חיפוש בינארי מאוזן, מבנה נתונים המשמש בדר"כ למימוש מילון. מבנה הנתונים המקורי הומצא בשנת 1972 על ידי רודולף באייר אשר קרא לו "עץ B בינארי סימטרי" (באנגלית: symmetric binary B-tree) ואת שמו המקורי קיבל במאמר שנכתב על ידי רוברט סדגוויק וליאונידס גויבס בשנת 1978. מבנה נתונים זה הוא מורכב יחסית אך בעל סיבוכיות זמן ריצה טובה עבור פעולותיו השונות והוא יעיל גם מעשית. העץ תומך בפעולות הכנסה, הוצאה וחיפוש בזמן (O(log n במקרה הגרוע כאשר n הוא מספר האיברים בעץ בעת ביצוע הפעולה. ניתן לאמר שעץ אדום-שחור הוא עץ חיפוש בינארי אשר מכניס ומוציא איברים בצורה חכמה, על מנת להבטיח שהעץ מאוזן ובכך שומר על יעילותן של הפעולות השונות.
טרמינולוגיה
עץ אדום שחור הוא סוג מיוחד של עץ בינארי, בו משתמשים במדעי המחשב לארגון מידע בר השוואה כגון מספרים או טקסט.
העלים של עץ אדום שחור אינם מכילים מידע. עלים אלו בדרך כלל לא מופיעים בזיכרון אלא מופיעים כnull, שמשמעותו במדעי המחשב היא "כלום" או "ללא ערך" והוא בדר"כ מיוצג על ידי 0, אך ניתן לפשט אלגוריתמים מסוימים באמצעות עלה יחיד המופיע בזיכרון המשמש לייצוג כל העלים של העץ. כלומר, כל ההפניות מצמתים פנימיים לעלים מצביעות לאותו עלה.
לעתים מגדירים עץ אדום שחור כעץ בו הקשתות צבועות ולא הצמתים אך למעשה אין לכך כל משמעות, צבעו של צומת בטרמינולוגיה של הערך יכול להיות צבעה של הקשת המחברת אותו לאביו, מלבד השורש, אשר צבעו תמיד שחור אך כפי שנראה בהמשך הגדרה זו אינה הכרחית ולא משמעותית במיוחד.
מאפיינים
עץ אדום שחור הוא עץ בינארי בו לכל צומת קיים שדה המגדיר צבע, שערכו אדום או שחור. בנוסף לדרישות הרגילות של עצי חיפוש בינאריים, עץ אדום שחור מקיים גם את הדרישות הבאות:
- 1. צומת הוא שחור או אדום (אחד מן השניים).
- 2. השורש הוא שחור (כלל זה לעתים מושמט מכיוון שצבע השורש תמיד יכול להשתנות מאדום לשחור אך לא תמיד להפך, אך השפעתו על ניתוח הסיבוכיות קטנה בכל מקרה)
- 3. כל העלים שחורים.
- 4. שני ילדיו של צומת אדום הם שחורים.
- 5. כל מסלול פשוט מצומת מסוים לכל אחד מהצאצאים העלים שלו מכיל אותו מספר של צמתים שחורים.
אילוצים אלו כופים הגדרה משמעותית על עצים אדומים שחורים: אורכו של המסלול הארוך ביותר מהשורש לכל אחד מן העלים הוא לכל היותר פעמיים אורכו של המסלול הקצר ביותר מהשורש לאחד העלים. התוצאה היא שהעץ מספיק מאוזן כדי לשמור על סיבוכיות טובה של הפעולות השונות, מכיוון שפעולות אלה דורשות במקרה הגרוע ביותר זמן יחסי לגובה העץ, הגבלת גובה העץ מגבילה גם את סיבוכיות הפעולות.
על מנת לראות מדוע מאפיינים אלה מבטיחים הגדרה זו, מספיק להבחין בכך שאף מסלול לא יכול להכיל שני צמתים אדומים ברצף, לפי מאפיין מספר 4. המסלול הקצר ביותר מכיל צמתים שחורים בלבד והמסלול הארוך ביותר מכיל לסירוגין צמתים אדומים ושחורים. בנוסף, כל המסלולים מהשורש לעלים מכילים מספר זהה של צמתים שחורים, לפי מאפיין מספר 5, ולכן אין מסלול הארוך פי שניים מאורכו של מסלול אחר.
בייצוגים רבים של עצים בתור מבני נתונים, לצומת יכול להיות בן אחד בלבד, ועלים תמיד מכילים מידע. קיימת אפשרות לייצג עצים אדומים שחורים בפרדיגמה זו, אך היא משנה ומוסיפה מאפיינים שונים ומסבכת את האלגוריתם. מסיבה זו אנו משתמשים בערך זה בעלים ריקים אשר מטרתם היא לסמן את "סוף" העץ, כפי שהראנו למעלה, ובצמתים בעלי שני בנים בלבד.
פעולות
הכנסה (Insert): הכנסת איבר לעץ, בצורה שתשמור על איזונו. ניתן לבצע בזמן של ((O(log(N .
הסרה (Remove): הסרת איבר מבוקש מהעץ. ניתן לבצע בזמן של ((O(log(N.
מכיוון שפעולות אלו משנות את העץ התוצאה עלולה להפר את התכונות של העץ. כדי לשמור על תכונות העץ עלינו לשנות את צבעיהם של כמה מן הצמתים, ואף את מבנה ההצבעה.
שינוי מבנה ההצבעה נקרא רוטציה. קיימים שני סוגים של רוטציה: רוטציה ימנית (Right-Rotate), ורוטציה שמאלית (Left-Rotate).
רוטציה
נתון צומת אב X שלו שני בנים: שמאלי-Z , ימני-Y . גם ל-Y שני בנים: שמאלי-A , ימני-B ,כנ"ל עם Z שבניו בהתאמה C ו-D.
לאחר רוטציה ימנית, X יהיה בנו השמאלי של Y , כאשר A יהפוך להיות בנו הימני של X.
לעומת זאת, לאחר רוטציה שמאלית, X יהיה בנו הימני של Z , כאשר D יהיה בנו השמאלי של X.
אלגוריתם להכנסת צומת לעץ אדום-שחור
- הכנסת X לעץ על פי אלגוריתם של הכנסה לעץ חיפוש בינארי.
- צביעת X באדום.
- כל עוד X אינו השורש וגם אביו של X אדום בצע:
- אם הדוד אדום בצע:
- צביעת הדוד של X בשחור.
- צביעת האבא של X בשחור.
- צביעת הסבא של X באדום.
- כעת X מצביע לסבא של X.
- אחרת (הדוד שחור) בצע:
- אם האבא של X הוא בן שמאלי בצע:
- אם X הוא בן ימני בצע:
- כעת X מצביע לאבא של X.
- רוטציה שמאלית ל-X.
- צביעת אבא של X בשחור.
- צביעת סבא של X באדום.
- רוטציה ימנית לסבא של X.
- אם X הוא בן ימני בצע:
- אחרת (אבא של X בן ימני) בצע:
- אם X הוא בן שמאלי בצע:
- X מצביע לאבא של X.
- רוטציה ימנית ל-X.
- צביעת אבא של X בשחור.
- צביעת סבא של X באדום.
- רוטציה שמאלית לסבא של X.
- אם X הוא בן שמאלי בצע:
- אם האבא של X הוא בן שמאלי בצע:
- אם הדוד אדום בצע:
- צביעת השורש בשחור.
קישורים חיצוניים
- אוסף מצגות, הדגמות ותרגילים עם פתרונות בנושא עצי אדום-שחור
- הרצאה של רוברט סדג'וויק על גרסה חדשה (2008) של עצי אדום שחור
מבני נתונים | ||
---|---|---|
מבנים מופשטים | רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • טריי X מהיר • טריי y מהיר• עץ WAVL | |
הסתברותיים | מסנן בלום |