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

הוסר בית אחד ,  לפני 6 שנים
חיפוש בעץ מאוזן לגמרי בגודל 10,000 לוקח log2(10000)~14
מ (בוט החלפות: לעתים, \1תייחס, מסוי\1, \1תת-)
(חיפוש בעץ מאוזן לגמרי בגודל 10,000 לוקח log2(10000)~14)
==הסבר פשוט==
במדעי המחשב לעתים רבות בוחרים לשמור מידע בצורת עץ חיפוש בינארי. צורה זו מאפשרת, בתנאים מסוימים, חיפוש מהיר של מידע, עדכונו או הכנסת מידע חדש, בלי לפגוע במיונו של המידע הקודם. עם זאת, בעץ בינארי עשויה להתעורר בעיית איזון אשר, במקרה קיצוני, תוביל לכך שהפעולות המבוצעות עליו יקחו זמן רב מאוד, ובכך יהפכו אותו ללא יעיל לשימוש. איזון משמעו שהמידע בעץ יחולק בצורה שווה, בין ענפי העץ הימניים והשמאלים, כך שלא יקרה לדוגמה, מצב בו קיים תת-עץ שמאלי דליל מאוד במידע, בעוד שתת-העץ הימני עתיר במידע רב.
לשם הדגמה, בעץ בינארי לא מאוזן המכיל 10,000 רשומות מידע, ייתכן ונצטרך לבדוק כל אחת מ-10,000 הרשומות על מנת לאתר רשומת מידע ספציפית המעניינת אותנו. לעומת זאת, בעץ בינארי מאוזן, נדרש לבדוק לכל היותר 10014 רשומות בלבד.
 
על מנת למנוע את בעיית חוסר האיזון בעצים פותח עץ אדום שחור. למעשה, עץ זה דומה לעץ חיפוש בינארי רגיל, אך פעולת הוספת או מחיקת המידע, דורשות טיפול מיוחד, העומד בכללי העץ האדום שחור. כללים אלו אוכפים מדיניות המובילה לכך שהעץ אינו יכול לצאת מאיזון, מעבר לגבול מסוים, ובכך למנוע מצב בו העץ יהפוך להיות לא יעיל.
עריכה אחת