 |
|
 |
עץ אדום שחורעץ אדום שחור הוא סוג של עץ חיפוש בינארי. בעץ זה לכל שני עלים, מרחק עלה אחד מהשורש יהיה לכל היותר פעמיים מרחק השני מהשורש. דבר זה גורם לכך שפעולות רגילות על עץ החיפוש הבינארי כגון חיפוש, הוספה ומחיקה פועלות בזמן גרוע ביותר של (O(logn. תכונות עץ אדום שחורלכל צומת בעץ אדום שחור יש צבע (אדום או שחור). העץ תמיד יקיים את התכונות הבאות:
מכיוון שהעץ מקיים את תכונות אלה, גובהו של עץ בעל n איברים יהיה לכל היותר (2log(n+1, ומכאן נובע שפעולות סטנדרטיות על העץ יעבדו בזמן (O(logn. פעולות בסיסיותעץ אדום שחור תומך באותן פעולות של עץ חיפוש בינארי רגיל, אך יש לבצען בצורה שונה כדי להבטיח שהעץ ישמור על התכונות שלו.
כדי לממש את פעולות הוספה ומחיקה, יש צורך בפעולת עזר: סיבוב של העץ לצד ימין או שמאל. פעולה זו משנה את מבנה העץ אך שומרת על היותו עץ חיפוש בינארי.
|
|
