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