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

נוספו 1,734 בתים ,  לפני 6 שנים
הוספת הסבר פשוט
מ (?)
(הוספת הסבר פשוט)
'''עץ אדום-שחור''' הוא מבנה נתונים מורכב יחסית, אך בשל היותו [[עץ מאוזן|מאוזן]] הוא שומר על [[סיבוכיות]] [[סיבוכיות זמן|זמן ריצה]] טובה, יעילה ומעשית עבור הפעולות השונות הנתמכות: "הכנסה", "הוצאה" ו"חיפוש" בזמן של <math>\ O(\log n)</math> במקרה הגרוע ביותר (כאשר <math>n</math> הוא מספר האיברים בעץ בעת ביצוע הפעולה).
 
==הסבר פשוט==
במדעי המחשב לעיתים רבות בוחרים לשמור מידע בצורת עץ חיפוש בינארי. צורה זו מאפשרת, בתנאים מסויימים, חיפוש מהיר של מידע, עדכונו או הכנסת מידע חדש, בלי לפגוע במיונו של המידע הקודם. עם זאת, בעצים בינארים עשויה להתעורר בעיית איזון אשר עשויה להוביל לכך שהפעולות המבוצעות עליו יקחו זמן רב מאוד, ובכך יהפכו אותו ללא יעיל לשימוש. איזון משמעו שהמידע בעץ יחולק בצורה שווה בין ענפי העץ הימניים והשמאלים, כך שלא יקרה לדוגמה, מצב בו קיים תת עץ ("ענף") שמאלי דליל מאוד במידע, בעוד שתת העץ הימני עתיר במידע רב.
לשם הדגמה, בעץ בינארי לא מאוזן המכיל 10,000 רשומות מידע, ייתכן ונצטרך לבדוק כל אחת מ-10,000 הרשומות. לעומת זאת, בעץ בינארי מאוזן, נדרש לבדוק לכל היותר 100 רשומות בלבד.
 
על מנת למנוע את בעיית היציאה מן האיזון פותח עץ אדום שחור. למעשה, עץ זה דומה לעץ חיפוש בינארי רגיל, אך פעולת הוספת או מחיקת המידע, דורשות טיפול מיוחד, העומד בכללי העץ האדום שחור. כללים אלו אוכפים מדיניות המובילה לכך שהעץ אינו יכול לצאת מאיזון, מעבר לגבול מסויים, ובכך למנוע מצב בו העץ יהפוך להיות לא יעיל.
 
==רקע היסטורי==