X-fast trie

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

הקדמה

Trie

Trie הוא מבנה נתונים פשוט הנועד לאחסון מחרוזות. ניתן לראות במספר טבעי כמחרוזת, לפי הייצוג הבינארי שלו. הרעיון יהיה לשמור את הערכים ב-Trie של ביטים.

טבלת גיבוב

טבלת גיבוב היא מבנה נתונים המאפשר הכנסה, הוצאה וחיפוש בזמן ממוצע של , וסיבוכיות מקום ליניארית.
עבור X-fast trie אנחנו מניחים טבלת גיבוב מושלמת, כלומר, מתעלמים מה-worst case.

מבנה

X-Fast trie הוא Trie בינארי משורשר בו העלים מחוברים ברשימה מקושרת דו כיוונית, וכל הצמתים בכל שלב מאוחסנים בטבלת גיבוב.

Trie בינארי משורשר הוא עץ בינארי המקיים
כל צומת 0 שחסרה, יהיה מצביע לאיבר הקודם בסריקת inorder
כל צומת 1 שחסרה, יהיה מצביע לאיבר העוקב בסריקת inorder
למצביעים אלה נקרא חוטים

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

פעולות

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

עוקב וקודם
בX-fast trie ניתן למצוא עוקב לאיבר x בטווח בזמן .

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

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

הכנסה
על מנת להכניס ערך x, צריכים
להוסיף מספר צמתים חדשים ל-Trie
לחבר את x לרשימה המקושרת הדו כיוונית של העלים
לעדכן את החוטים שיכללו את x
הזמן במקרה הגרוע הוא  בגלל השלבים הראשון והשלישי.

אלגוריתם להכנסה
אלגוריתם זה תומך בזמן הכנסה משוערך של 

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

מחיקה
באופן מאוד דומה להכנסה, מחיקה לוקחת זמן משוערך של 

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

הערות שוליים
.

מבני נתונים
עצים (גרפים)