X-fast trie

X-fast trie
יצירה
הומצא ב:	1982
ממציא:	דן ווילארד
סיבוכיות מקום וזמן
	ממוצע במקרה הגרוע
זיכרון:	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log M)} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log M)}
חיפוש:	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O (\log \log M)} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O (\log \log M)}
הכנסה:	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log M)} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(\log M)}
הוצאה:	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log M)} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(\log M)}
הצצה:	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}

במדעי המחשב, X-Fast trie הוא מבנה נתונים המאחסן מספרים שלמים מטווח נתון. מבנה הנתונים מתבסס על עצים וטבלאות גיבוב. מבנה הנתונים נחשב מהיר במיוחד מאחר שהוא מאפשר לבצע שאילתות בסיבוכיות זמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O (\log \log M)} ועל ידי שימוש בסיבוכיות מקום של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log M)} , כאשר n מסמן את מספר הערכים בעץ ו-M את טווח הערכים שהעץ יכול להכיל. על מנת לתת אינטואיציה כמה הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log \log} גדלה לאט, מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log_2 \log_2 (10^{10}) \approx 5} . בזמן פרסום המאמר, ווילארד הציג גם מבנה נתונים יעיל יותר בשם Y-fast trie.

הקדמה

Trie

ערך מורחב – Trie

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

טבלת גיבוב

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

טבלת גיבוב היא מבנה נתונים המאפשר הכנסה, הוצאה וחיפוש בזמן ממוצע של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} , וסיבוכיות מקום לינארית. עבור X-fast trie אנחנו מניחים טבלת גיבוב מושלמת, כלומר, מתעלמים מה-worst case.

מבנה

קובץ:Xfast trie example.svg

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

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

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

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

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

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

פעולות

הצצה

על מנת לבדוק האם מספר (או מפתח) x נמצא בעץ, פשוט נחפש בטבלת הגיבוב של העלים. לכן ניתן לוודא קיום של מפתח בזמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} .

עוקב וקודם

בX-fast trie ניתן למצוא עוקב לאיבר x בטווח בזמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log \log M} .

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

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

הכנסה

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

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

הזמן במקרה הגרוע הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(\log M)} בגלל השלבים הראשון והשלישי.

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

אלגוריתם זה תומך בזמן הכנסה משוערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log M)}

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

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

מחיקה

באופן מאד דומה להכנסה, מחיקה לוקחת זמן משוערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log M)}

אנחנו צריכים

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

הערות שוליים

.