X-fast trie

X-fast trie
יצירה
הומצא ב:	1982
ממציא:	דן ווילארד
סיבוכיות מקום וזמן
	ממוצע במקרה הגרוע
זיכרון:	${\displaystyle O(n\log M)}$ ${\displaystyle O(n\log M)}$
חיפוש:	${\displaystyle O(\log \log M)}$ ${\displaystyle O(\log \log M)}$
הכנסה:	${\displaystyle O(\log M)}$ ${\displaystyle \Omega (\log M)}$
הוצאה:	${\displaystyle O(\log M)}$ ${\displaystyle \Omega (\log M)}$
הצצה:	${\displaystyle O(1)}$ ${\displaystyle O(1)}$

במדעי המחשב, X-Fast trie הוא מבנה נתונים המאחסן מספרים שלמים מטווח נתון. מבנה הנתונים מתבסס על עצים וטבלאות גיבוב. מבנה הנתונים נחשב מהיר במיוחד מאחר שהוא מאפשר לבצע שאילתות בסיבוכיות זמן ${\displaystyle O(\log \log M)}$ ועל ידי שימוש בסיבוכיות מקום של ${\displaystyle O(n\log M)}$, כאשר n מסמן את מספר הערכים בעץ ו-M את טווח הערכים שהעץ יכול להכיל. על מנת לתת אינטואיציה כמה הפונקציה ${\displaystyle \log \log }$ גדלה לאט, מתקיים ${\displaystyle \log _{2}\log _{2}(10^{10})\approx 5}$. בזמן פרסום המאמר, ווילארד הציג גם מבנה נתונים יעיל יותר בשם Y-fast trie.

הקדמה

Trie

ערך מורחב – Trie

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

טבלת גיבוב

ערך מורחב – טבלת גיבוב

טבלת גיבוב היא מבנה נתונים המאפשר הכנסה, הוצאה וחיפוש בזמן ממוצע של ${\displaystyle O(1)}$, וסיבוכיות מקום ליניארית. עבור X-fast trie אנחנו מניחים טבלת גיבוב מושלמת, כלומר, מתעלמים מה-worst case.

מבנה

עץ המכיל את הערכים 1, 4 ו-5

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

Trie בינארי משורשר הוא עץ בינארי המקיים

• כל צומת 0 שחסרה, יהיה מצביע לאיבר הקודם בסריקת inorder^[1]
• כל צומת 1 שחסרה, יהיה מצביע לאיבר העוקב בסריקת inorder

למצביעים אלה נקרא חוטים

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

פעולות

הצצה

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

עוקב וקודם

בX-fast trie ניתן למצוא עוקב לאיבר x בטווח בזמן ${\displaystyle \log \log M}$.

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

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

הכנסה

על מנת להכניס ערך x, צריכים

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

הזמן במקרה הגרוע הוא ${\displaystyle \Omega (\log M)}$ בגלל השלבים הראשון והשלישי.

אלגוריתם להכנסה

אלגוריתם זה תומך בזמן הכנסה משוערך של ${\displaystyle O(\log M)}$

הכנסה (קלט: x)

1. מצא את העוקב של x
2. הוסף את x ל-Trie
3. הכנס את x לרשימה המקושרת על ידי העוקב שמצאנו מקודם
4. תעלה במעלה העץ מ-x, העוקב והקודם שלו, ועדכן את החוטים

מחיקה

באופן מאוד דומה להכנסה, מחיקה לוקחת זמן משוערך של ${\displaystyle O(\log M)}$

אנחנו צריכים

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

הערות שוליים

1. הכוונה ב'צומת 0 שחסרה' היא צומת ללא בן שמאלי, 'צומת 1 שחסרה' מוגדר באופן אנלוגי
2. שהרי אם היו 0 ילדים אזי זה עלה, אך אך אם יש שני ילדים אז ניתן להמשיך לתחילית ארוכה יותר

.