עץ אדום שחור הוא סוג של עץ
חיפוש בינארי ולכן הוא מקיים את תכונות עץ חיפוש בינארי:
- לכל צומת יש עד שני בנים (שמאלי וימני).
- לכל צומת יש ערך. ניתן לבדוק עבור שני ערכים איזה הגדול יותר.
- ערך כל צומת בתת העץ השמאלי של צומת קטן מערך האב. ערך כל צומת
בתת העץ הימני דול מערך האב.
בנוסף, עץ אדום שחור מקיים את התכונות הבאות:
- לכל צומת יש צבע - אדום או שחור.
- אם צומת אדום אז שני ילדיו שחורים.
- עבור צומת מסוים בעץ: כל מסלול מהצומת אל עלה שמתחתיו מכיל מספר
שווה של צמתים שחורים.
