הצגת המקור של הדף "X-fast trie"

{{מבנה נתונים
|תאריך המצאה=1982
|ממציא=דן ווילארד
|זיכרון ממוצע=<math>O(n\log M)</math>
|זיכרון במקרה הגרוע=<math>O(n\log M)</math>
|חיפוש ממוצע=<math>O (\log \log M)</math>
|חיפוש במקרה הגרוע=<math>O (\log \log M)</math>
|הכנסה ממוצע=<math>O(\log M)</math>
|הכנסה במקרה הגרוע=<math>\Omega(\log M)</math>
|הוצאה ממוצע=<math>O(\log M)</math>
|הוצאה במקרה הגרוע=<math>\Omega(\log M)</math>
|הצצה ממוצע=<math>O(1)</math>
|הצצה במקרה הגרוע=<math>O(1)</math>
}}
ב[[מדעי המחשב]], '''X-Fast trie''' הוא [[מבנה נתונים]] המאחסן מספרים שלמים מטווח נתון. מבנה הנתונים מתבסס על [[עץ חיפוש | עצים]] ו[[טבלת גיבוב |טבלאות גיבוב]]. מבנה הנתונים נחשב מהיר במיוחד מאחר שהוא מאפשר לבצע שאילתות בסיבוכיות זמן <math>O (\log \log M)</math> ועל ידי שימוש בסיבוכיות מקום של <math>O(n\log M)</math>, כאשר n מסמן את מספר הערכים בעץ ו-M את טווח הערכים שהעץ יכול להכיל. על מנת לתת [[אינטואיציה]] כמה הפונקציה <math>\log \log</math> גדלה לאט, מתקיים <math>\log_2 \log_2 (10^{10}) \approx 5</math>. בזמן פרסום המאמר, ווילארד הציג גם מבנה נתונים יעיל יותר בשם [[Y-fast trie]].

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

===טבלת גיבוב===
{{ערך מורחב|ערך=[[טבלת גיבוב]]}}
טבלת גיבוב היא מבנה נתונים המאפשר הכנסה, הוצאה וחיפוש בזמן ממוצע של <math>O(1)</math>, וסיבוכיות מקום ליניארית.
עבור X-fast trie אנחנו מניחים טבלת גיבוב מושלמת, כלומר, מתעלמים מה-worst case.

==מבנה==
[[קובץ:Xfast trie example.svg |ממוזער| upright 1.5 | alt=עץ המכיל את הערכים 1, 4 ו-5. בעץ 4 דרגות, 3 על לכל ביט במספר הארוך ביותר ועוד דרגת ה-0 | עץ המכיל את הערכים 1, 4 ו-5]]
X-Fast trie הוא '''Trie בינארי משורשר''' בו העלים מחוברים ב[[רשימה מקושרת]] דו כיוונית, וכל הצמתים בכל שלב מאוחסנים בטבלת גיבוב.

'''Trie בינארי משורשר''' הוא [[עץ בינארי]] המקיים
*כל צומת 0 שחסרה, יהיה מצביע לאיבר הקודם בסריקת inorder{{הערה|הכוונה ב'צומת 0 שחסרה' היא צומת ללא בן שמאלי, 'צומת 1 שחסרה' מוגדר באופן אנלוגי}}
*כל צומת 1 שחסרה, יהיה מצביע לאיבר העוקב בסריקת inorder
למצביעים אלה נקרא '''חוטים'''

ב-X-Fast trie נבדיל בין צמתים לעלים. כל הערכים יאוחסנו בעלים, בעוד הצמתים נועדו אך ורק לנווט בתוך העץ. לא נשמור צמתים פנימיים אם אין לאותו צומת צאצאים שהם עלים.
בכל דרגה של העץ נשמור טבלת גיבוב בה יש את כל הצמתים של אותה דרגה. על מנת שנוכל להבטיח את זמן הריצה הגרוע של השאילתות, נשתמש ב[[גיבוב דינמי מושלם]] או ב[[גיבוב קוקייה]].

==פעולות==
===הצצה===
על מנת לבדוק האם מספר (או מפתח) x נמצא בעץ, פשוט נחפש בטבלת הגיבוב של העלים. לכן ניתן לוודא קיום של מפתח בזמן <math>O(1)</math>.

===עוקב וקודם===
בX-fast trie ניתן למצוא עוקב לאיבר x בטווח בזמן <math>\log \log M</math>.

נחפש את התחילית הארוכה ביותר של x שנמצאת בעץ. אם זה עלה נתקדם לערך הבא. אם זה צומת אזי קיים מצביע לאחד העלים {{הערה | שהרי אם היו 0 ילדים אזי זה עלה, אך אך אם יש שני ילדים אז ניתן להמשיך לתחילית ארוכה יותר}}. נעקוב אחרי המצביע הזה, ונחזיר את הערך שהגענו אליו או את זה שאחריו, תלוי בערך של x כמובן.

על מנת שנוכל למצוא את התחילית במהירות, נבצע [[חיפוש בינארי]], כלומר נחפש בטבלת הגיבוב האמצעית את התחילית באורך חצי, אם היא לא קיימת אז נלך לדרגה h/4, ואם היא קיימת נתקדם לדרגה 3h/4. ההמשך כמו חיפוש בינארי רגיל.

===הכנסה===
על מנת להכניס ערך x, צריכים
*להוסיף מספר צמתים חדשים ל-Trie
*לחבר את x לרשימה המקושרת הדו כיוונית של העלים
*לעדכן את החוטים שיכללו את x
הזמן במקרה הגרוע הוא <math>\Omega(\log M)</math> בגלל השלבים הראשון והשלישי.

====אלגוריתם להכנסה====
[[אלגוריתם]] זה תומך בזמן הכנסה משוערך של <math>O(\log M)</math>

הכנסה ([[קלט]]: x)
#מצא את העוקב של x
#הוסף את x ל-Trie
#הכנס את x לרשימה המקושרת על ידי העוקב שמצאנו מקודם
#תעלה במעלה העץ מ-x, העוקב והקודם שלו, ועדכן את החוטים

===מחיקה===
באופן מאוד דומה להכנסה, מחיקה לוקחת זמן משוערך של <math>O(\log M)</math>

אנחנו צריכים
*למחוק את x מה-Trie
*להוציא את x מהרשימה המקושרת של העלים
*לעדכן את כל החוטים הרלוונטיים

==הערות שוליים==
{{הערות שוליים|יישור=ימין}}.

{{מבני נתונים}}

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