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

נוספו 28 בתים ,  לפני 8 שנים
אין תקציר עריכה
'''עץ אדום-שחור''' הוא מבנה נתונים מורכב יחסית, אך בשל היותו [[עץ מאוזן|מאוזן]] הוא שומר על [[סיבוכיות]] [[סיבוכיות זמן|זמן ריצה]] טובה, יעילה ומעשית עבור הפעולות השונות הנתמכות: "הכנסה", "הוצאה" ו"חיפוש" בזמן של '''(O(log n''' במקרה הגרוע ביותר (כאשר n הוא מספר האיברים בעץ בעת ביצוע הפעולה).
 
שמו של העץ נובע מהתכונה הבאה שלו: בסיומה של כל פעולה (הכנסה, הוצאה, חיפוש) העץ מאוזן, כאשר כל הקודקודים בעלי עומק זוגי מסומנים/צבועים בצבע אחד (שחור), וכל יתר הקודקודים (בעלי עומק אי-זוגי) צבועים בצבע אחר (אדום). או במילים אחרות: בכל רגע נתון, עבור כל קודקוד הצבוע בצבע אחד - מתקיימיםמתקיים כי כל שכניוהקודקודים הסמוכים אליו צבועים בצבע אחר.
 
==רקע היסטורי==