עץ אדום שחור – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
Crazy Ivan (שיחה | תרומות) |
||
שורה 1:
{{לפשט}}
[[קובץ:Red-black tree example.svg|שמאל|ממוזער|400px|דוגמה ל'''עץ אדום-שחור''', שהינו עץ מאוזן, אשר בו כל הקודקודים בעומק 0 ו-2 צבועים בשחור, וכל הקודקודים בעומק 1 ו-3 צבועים באדום]]
ב[[מדעי המחשב]], '''עץ אדום-שחור''' (ב[[אנגלית]]: '''Red-Black Tree''') הינו [[מבנה נתונים]] מסוג [[עץ (תורת הגרפים)|עץ]] [[עץ חיפוש|חיפוש]] [[עץ בינארי|בינארי]] [[עץ מאוזן|מאוזן]].
שורה 6 ⟵ 5:
'''עץ אדום-שחור''' הוא מבנה נתונים מורכב יחסית, אך בשל היותו [[עץ מאוזן|מאוזן]] הוא שומר על [[סיבוכיות]] [[סיבוכיות זמן|זמן ריצה]] טובה, יעילה ומעשית עבור הפעולות השונות הנתמכות: "הכנסה", "הוצאה" ו"חיפוש" בזמן של '''(O(log n''' במקרה הגרוע ביותר (כאשר n הוא מספר האיברים בעץ בעת ביצוע הפעולה).
שמו של העץ נובע מהתכונה הבאה שלו: בסיומה של כל פעולה (הכנסה, הוצאה, חיפוש) העץ מאוזן,
==רקע היסטורי==
| |||