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

נוספו 603 בתים ,  לפני 8 שנים
הפשטה של פסקת הפתיחה + הסבר לשם
(הפשטה של פסקת הפתיחה + הסבר לשם)
{{לפשט}}
 
[[קובץ:Red-black tree example.svg|שמאל|ממוזער|400px|דוגמה לעץל'''עץ אדום -שחור''', שהינו עץ מאוזן, אשר בו כל הקודקודים בעומק 0 ו-2 צבועים בשחור, וכל הקודקודים בעומק 1 ו-3 צבועים באדום]]
ב[[מדעי המחשב]], '''עץ אדום-שחור''' (ב[[אנגלית]]: '''Red-Black Tree''') הינו [[מבנה נתונים]] מסוג [[עץ (תורת הגרפים)|עץ]] [[עץ חיפוש|חיפוש]] [[עץ בינארי|בינארי]] [[עץ מאוזן|מאוזן]].
ב[[מדעי המחשב]], '''עץ אדום-שחור''' (ב[[אנגלית]]: '''Red-Black Tree''') הינו [[מבנה נתונים]] מסוג [[עץ חיפוש בינארי מאוזן]], מבנה נתונים המשמש בדר"כ למימוש [[מילון (מבנה נתונים)|מילון]]. מבנה הנתונים המקורי הומצא בשנת 1972 על ידי [[רודולף באייר]] אשר קרא לו "[[עץ B]] בינארי סימטרי" (באנגלית: symmetric binary B-tree) ואת שמו המקורי קיבל במאמר שנכתב על ידי [[רוברט סדגוויק]] ו[[ליאונידס גויבס]] בשנת 1978. מבנה נתונים זה הוא מורכב יחסית אך בעל סיבוכיות זמן ריצה טובה עבור פעולותיו השונות והוא יעיל גם מעשית. העץ תומך בפעולות הכנסה, הוצאה וחיפוש בזמן '''(O(log n''' במקרה הגרוע כאשר n הוא מספר האיברים בעץ בעת ביצוע הפעולה. ניתן לאמר שעץ אדום-שחור הוא עץ חיפוש בינארי אשר מכניס ומוציא איברים בצורה חכמה, על מנת להבטיח שהעץ מאוזן ובכך שומר על יעילותן של הפעולות השונות.
 
'''עץ אדום-שחור''' הוא מבנה נתונים מורכב יחסית, אך בשל היותו [[עץ מאוזן|מאוזן]] הוא שומר על [[סיבוכיות]] [[סיבוכיות זמן|זמן ריצה]] טובה, יעילה ומעשית עבור הפעולות השונות הנתמכות: "הכנסה", "הוצאה" ו"חיפוש" בזמן של '''(O(log n''' במקרה הגרוע ביותר (כאשר n הוא מספר האיברים בעץ בעת ביצוע הפעולה).
 
שמו של העץ נובע מהתכונה הבאה שלו: בסיומה של כל פעולה (הכנסה, הוצאה, חיפוש) העץ מאוזן, כאשר כל הקודקודים בעלי עומק זוגי מסומנים/צבועים בצבע אחד (שחור), וכל יתר הקודקודים (בעלי עומק אי-זוגי) צבועים בצבע אחר (אדום). או במילים אחרות: בכל רגע נתון, עבור כל קודקוד הצבוע בצבע אחד - מתקיימים כי כל שכניו צבועים בצבע אחר.
 
==רקע היסטורי==
מבנה הנתונים המקורי הומצא בשנת 1972 על ידי [[רודולף באייר]] אשר קרא לו "[[עץ B]] בינארי סימטרי" (באנגלית: symmetric binary B-tree) ואת שמו המקורי קיבל במאמר שנכתב על ידי [[רוברט סדגוויק]] ו[[ליאונידס גויבס]] בשנת 1978.
 
==טרמינולוגיה==