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

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