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

נוספו 53 בתים ,  לפני 3 שנים
מ
"הגובה השחור" זה הגובה מ*השורש* לעלה כלשהו, ניסוח
מ ("הגובה השחור" זה הגובה מ*השורש* לעלה כלשהו, ניסוח)
# כל העלים שחורים
# שני ילדיו של צומת אדום הם שחורים
# כל [[מסלול (תורת הגרפים)|מסלול פשוט]] מצומת מסוים לכל אחד מהצאצאים העלים שלו מכיל אותו מספר של צמתים שחורים (מספר זה, כאשר הצומת המסוים הוא השורש, מכונה "הגובה השחור" של העץ)
 
אילוצים אלו כופים הגדרה משמעותית על עצים אדומים שחורים: אורכו של המסלול הארוך ביותר מהשורש לכל אחד מן העלים הוא לכל היותר פעמיים אורכו של המסלול הקצר ביותר מהשורש לאחד העלים. התוצאה היא שהעץ מספיק מאוזן כדי לשמור על [[סיבוכיות]] טובה של הפעולות השונות, מכיוון שפעולות אלה דורשות במקרה הגרוע ביותר זמן יחסי לגובה העץ, הגבלת גובה העץ מגבילה גם את סיבוכיות הפעולות.
עריכה אחת