עץ סיפות

מתוך ויקיפדיה, האנציקלופדיה החופשית

עץ סיפות עבור המחרוזת BANANA מרופדת עם  $. מצביעי הסיפה מקווקוים.
הגדל
עץ סיפות עבור המחרוזת BANANA מרופדת עם $. מצביעי הסיפה מקווקוים.


במדעי המחשב, עץ סיפות הוא מבנה נתונים המאפשר חיפושים מהירים של תת מחרוזות כלשהי של מחרוזת נתונה. אפשר לחשוב עליו כעל Trie (איך מתרגמים Trie לעברית?) המכיל את כל הסיפות של המחרוזת, לאחר כיווץ שרוכים.

יוקונן מצא שיטה יעילה לבניית עץ סיפות בסיבוכיות זמן ומקום O\left(n\right) תוך שימוש בכמה אופטימיזציות, כולל מצביעי סיפה. מבנה נתונים שקול אך כנראה יותר יעיל במעשה הינו מערך סיפות (הייצוג כמערך יותר קומפקטי ויעיל, אולם בעל אותה סיבוכיות אסימפטוטית).

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.

שפות אחרות