עץ סיפות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ פתרון בעיית ההתלבטות על ידי חיפוש קצר בויקי האנגלית |
מ תיקון קישור |
||
שורה 1:
[[
ב[[מדעי המחשב]] '''עץ סיפות''' הוא [[מבנה נתונים]] המאפשר חיפושים מהירים של [[תת מחרוזות]] כלשהי של [[מחרוזת (תכנות)|מחרוזת]] נתונה. אפשר לחשוב עליו כעל [[עץ תחילות]] המכיל את כל ה[[סיפה|סיפות]] של המחרוזת, לאחר כיווץ [[שרוך|שרוכים]].
[[יוקונן]] מצא שיטה יעילה לבניית עץ סיפות בסיבוכיות זמן ומקום <math>O\left(n\right)</math> תוך שימוש בכמה אופטימיזציות, כולל מצביעי סיפה. מבנה נתונים שקול אך כנראה יותר יעיל במעשה הינו [[מערך סיפות]] (הייצוג כמערך יותר קומפקטי ויעיל, אולם בעל אותה סיבוכיות אסימפטוטית).
| |||