עץ אדום שחור

עץ אדום שחור הוא סוג של עץ חיפוש בינארי. בעץ זה לכל שני עלים, מרחק עלה אחד מהשורש יהיה לכל היותר פעמיים מרחק השני מהשורש. דבר זה גורם לכך שפעולות רגילות על עץ החיפוש הבינארי כגון חיפוש, הוספה ומחיקה פועלות בזמן גרוע ביותר של (O(logn.

תכונות עץ אדום שחור

לכל צומת בעץ אדום שחור יש צבע (אדום או שחור). העץ תמיד יקיים את התכונות הבאות:

  • אם צומת אדום אז שני ילדיו שחורים.
  • עבור צומת מסוים בעץ: כל מסלול מהצומת אל עלה שמתחתיו מכיל מספר שווה של צמתים שחורים.

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

פעולות בסיסיות

עץ אדום שחור תומך באותן פעולות של עץ חיפוש בינארי רגיל, אך יש לבצען בצורה שונה כדי להבטיח שהעץ ישמור על התכונות שלו.

כדי לממש את פעולות הוספה ומחיקה, יש צורך בפעולת עזר: סיבוב של העץ לצד ימין או שמאל. פעולה זו משנה את מבנה העץ אך שומרת על היותו עץ חיפוש בינארי.