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

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

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

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