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