הצגת המקור של הדף "Trie"

{{מבנה נתונים
|תמונה=[[קובץ:Trie example.svg|250px]]
|כיתוב= עץ trie אשר מכיל את המפתחות "A", "to", "tea", "ted", "ten", "i", "in" ו"inn". לכל אחת מהמחרוזות השלמות יש ערך שלם שרירותי שמקושר אליה.
|תאריך המצאה= 1960
|ממציא= אדוארד פרדקין, אקסל טו ורנה דה לה בריאנדייס
|זיכרון ממוצע=<math>O(n)</math>
|זיכרון במקרה הגרוע=<math>O(n)</math>
|חיפוש ממוצע=<math>O(n)</math>
|חיפוש במקרה הגרוע=<math>O(n)</math>
|הכנסה ממוצע=<math>O(n)</math>
|הכנסה במקרה הגרוע=<math>O(n)</math>
|הוצאה ממוצע=<math>O(n)</math>
|הוצאה במקרה הגרוע=<math>O(n)</math>
}}

ב[[מדעי המחשב]], '''trie''', נקרא גם '''עץ קידומות''' או '''עץ דיגיטלי''', הוא [[מבנה נתונים]] מסוג [[עץ חיפוש|עץ]] אשר משמש לאיתור מפתחות מסוימים מתוך אוסף.

כמו שאר מבני הנתונים מבוססי החיפוש, ה-trie מאחסן מפתחות וערכים המקושרים אליהם. ברוב המקרים המפתח הוא [[מחרוזת (מדעי המחשב)|מחרוזת]], לעומת זאת הערך יכול להיות מכל סוג, לפעמים מדובר במזהה ייחודי או [[מצביע]] למידע הקשור למפתח הנ"ל. בשונה מ[[עץ חיפוש#עץ חיפוש בינארי|עץ חיפוש בינארי]], הצמתים במבנה לא מכילים מפתחות מאחר שהם מסמלים [[תו (מחשב)|תו]] יחיד. במקום זאת, המיקום של צומת במבנה מגדיר את המפתח אליו הוא מקושר.

לכל "הילדים" של צומת מסוים יש את אותה קידומת של המחרוזת המקושרת עם צומת האב שלהם, בעוד השורש מקושר עם [[מחרוזת ריקה (תכנות)|מחרוזת ריקה]].

בדומה ל[[מילון (מבנה נתונים)|מילון]], trie יכול גם לאחסן רק מפתחות ללא ערכים מקושרים.

==היסטוריה==
הרעיון ש-trie ייצג אוסף של מחרוזות תואר לראשונה באופן מופשט על ידי אקסל טו ב-1912. עצי trie הוזכרו לראשונה בקשר למחשבים על ידי רנה דה לה בריאנדייס ב-1959.

ב-1960 הרעיון פותח באופן עצמאי על ידי אדוארד פרדקין, שטבע את המושג trie, בעקבות ההברה האמצעית של המילה re'''trie'''val ''(שפירושה שליפה)''.

==פעולות==
[[קובץ:Trie representation.png|350px|שמאל|ממוזער|תמונה 2: Trie המכיל את אוסף המחרוזות: "sea", "sells" ו"she".]]
Trie תומך בפעולות: הכנסה, הוצאה וחיפוש אחר מחרוזת. ה-Trie מורכב מצמתים המכילים [[מערך (מבנה נתונים)|מערך]] בגודל מספר האיברים ב[[אלפבית (שפה פורמלית)|אלפבית]]. כל תא במערך מייצג סמל, ובהתאם מכיל קישור לצמתי המשך או ל- <math>\text{null}</math> ''(ראו תמונה 2 להמחשה)''. מלבד השורש, על כל צומת מצביע צומת אחר, הקרוי "אב". ברוב המקרים, הגודל של [[מערך (מבנה נתונים)|מערך]] הילדים יהיה אורך הסיביות של [[קידוד תווים|קידוד התווים]] - לדוגמה 256 תאים במקרה של [[ASCII]].

===חיפוש===
חיפוש אחר ערך בtrie מתבצע בעזרת התווים במחרוזת המפתח, כאשר כל צומת במבנה מכיל קישור תואם לכל תו אפשרי במחרוזת. לכן, מעקב אחר תווי המחרוזת בתוך הtrie יחזיר את הערך המקושר למחרוזת הקלט.

להלן מימוש החיפוש ב[[פסאודו קוד]] בהינתן שורש של trie {{כ}}(x) ומחרוזת (key):

<div class="mw-content-ltr">
 1 Trie-Find(x, key)
 2   '''for''' 0 &le; i < key.length '''do'''
 3     '''if''' <nowiki>x.Children[key[i]]</nowiki> = nil '''then'''
 4       '''return''' false
 5     '''end if'''
 6     x := <nowiki>x.Children[key[i]]</nowiki>
 7   '''repeat'''
 8   '''return''' x.Value
</div>

===הכנסה===
פעולת ההכנסה לtrie נעזרת ב[[קידוד תווים#מערכת תווים מקודדת|מערכת התווים]] בתור אינדקסים של [[מערך (מבנה נתונים)|מערך]] "הילדים" עד הגעתה לתו האחרון של המחרוזת. למעשה, מבנה הtrie משקף ביצוע של [[מיון בסיס]] מתחילת המחרוזת לסופה.

להלן מימוש ההכנסה ב[[פסאודו קוד]] בהינתן שורש של trie {{כ}}(x), מחרוזת (key) וערך (value):

<div class="mw-content-ltr">   
 1    Trie-Insert(x, key, value)
 2      '''for''' 0 &le; i < key.length '''do'''
 3        '''if''' <nowiki>x.Children[key[i]]</nowiki> = nil '''then'''
 4          <nowiki>x.Children[key[i]]</nowiki> := Node()
 5        '''end if'''
 6        <nowiki>x := x.Children[key[i]]</nowiki>
 7      '''repeat'''
 8      x.Value := value
 9      x.Is-Terminal := True
</div>

במידה והאלגוריתם נתקל במצביע ל-<math>\text{null}</math> לפני שהגיע לתו האחרון במחרוזת, הוא יוצר צומת חדש (כפי שניתן לראות בשורות 3–5).

===הוצאה===
הוצאה של מפתח-ערך מtrie מצריכה מציאה של צומת "סוף" בעזרת המחרוזת המקושרת אליו, שינוי סימון של אינדיקטור הסיום ל-''false'' ושל הערך עצמו ל-<math>\text{null}</math>.

להלן מימוש [[רקורסיה|רקורסיבי]] לפעולת הוצאה של מחרוזת (key) מtrie {{כ}}(x):
<div class="mw-content-ltr">   
 1   Trie-Delete(x, key)
 2      '''if''' key = nil '''then'''
 3        '''if''' x.Is-Terminal = True '''then'''
 4          x.Is-Terminal := False
 5          x.Value := nil
 6        '''end if'''
 7        '''for''' 0 &le i &lg x.Children.length
 8          '''if''' x.Children[i] != nil
 9            '''return''' x
 10         '''end if'''
 11       '''repeat'''
 12        '''return''' nil
 13      '''end if'''
 14      <nowiki>x.Children[key[0]] := Trie-Delete(x.Children[key[0]]</nowiki>, key[1:])
 15     '''return''' x
</div>

הפעולה מתחילה בבדיקה האם חיפוש אחר המפתח הוביל לצומת "סוף" או לסיומה של מחרוזת. במידה ומדובר בצומת "סוף" ללא "ילדים", הצומת מוסר מה-trie.
למרות זאת, הגעה לסיומה של מחרוזת מבלי שהצומת הוא צומת "סוף" מסמלת שהמחרוזת אינה קיימת ולכן לא מתבצע שום שינוי ב-trie. ה[[רקורסיה]] מתקדמת על ידי קידום של אינדקס המפתח (שורה 14).

==יישומים==
מבני trie משמשים בדרך כלל עבור חיזוי מלל/השלמה אוטומטית ואלגוריתמים להתאמת מחרוזות משוערת. ה-trie מאפשר חיפושים מהירים ותופס יחסית מעט מקום, במיוחד כאשר המבנה מכיל מספר גדול של מחרוזות קצרות. לכן ה-trie נמצא בשימוש ב[[בודק איות|בודקי איות]], ביישומי [[מקף|מיקוף]] ובאלגוריתמים להתאמת הקידומת הארוכה ביותר.
{{ש}}מילוני מחרוזות יעילים גם ב[[עיבוד שפה טבעית]], כגון הוצאת [[לקסיקון (בלשנות)|לקסיקון]] מתוך אוסף של קובצי טקסט.

===מיון===
מיון [[יחס סדר מילוני|לקסיקוגרפי]] של מחרוזות יכול להיות ממומש על ידי בניית trie עבור המחרוזות וסיור [[עץ חיפוש#מסלולי מעבר|pre-order]] על העץ; למעשה זוהי דרך לבצע [[מיון בסיס]]. מבני ה-trie חשובים מאוד עבור [[Burstsort]], אשר ידוע בשל היותו [[אלגוריתם]] מיון המחרוזות המהיר ביותר נכון לשנת 2007.

===חיפוש טקסטים===
גרסה מיוחדת של trie, שנקראת [[עץ סיפות]], משמשת כדי לאנדקס את כל הסיומות האפשריות של טקסט מסוים ומאפשרת חיפוש וגישה מהירים אליהן.

===מנועי חיפוש אינטרנטיים===
גרסה מיוחדת של ה-trie, הנקראת trie דחוס, נמצאת בשימוש ב[[מנוע חיפוש#מנועי חיפוש אינטרנטיים|מנועי חיפוש אינטרנטיים]] כדי לאחסן את אוסף כל המילים הניתנות לחיפוש. כל צומת "סוף" מקושרת עם רשימת [[URL]] אשר מובילים לדפים שתואמים למילת המפתח.

===ביואינפורמטיקה===
ה-trie נמצא בשימוש ב[[ביואינפורמטיקה]], במיוחד ביישומי [[עימוד רצפים]] כמו [[BLAST (ביוטכנולוגיה)|BLAST]].

===ניתוב אינטרנט===
גרסאות דחוסות של trie נמצאות בשימוש לשם אחסון קידומות של [[כתובת IP|כתובות IP]] בתוך [[נתב]]ים ו[[גשר (רשת)|גשרים]] כדי לבצע חיפוש מבוסס קידומות.

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

==הערות שוליים==
{{מבני נתונים}}

[[קטגוריה:מבני נתונים]]
[[קטגוריה:עצים (גרפים)]]