 |
(תנאי מוקדם כדי להבין הסבר זה יש להכיר את המושגים "מצביע" ו"מערך" בתכנות)
Trie הוא מבנה נתונים שבנוי כך:
הצומת הראשון מצביע אל מערך שמכיל את כל אותיות האלפבית של המפתח של המידע. כל איבר במערך, בנוסף לכך שהוא מכיל אות כלשהי (נסמנה a), מכיל גם מצביע למערך נוסף בעל אותו מבנה (שמאותחל ל-null - "כלום"), ומצביע לערך (Value), שמאותחל גם הוא ל-null. המצביע למערך הנוסף אכן מצביע למערך שכזה רק אם הוכנס ערך שהמפתח שלו, במקום המתאים, כולל את האות המתאימה (a). כלומר, עבור הכנסת המפתחות abc, abd ו-abdd נקבל את המבנה הבא:
מצביע לתחילת המבנה - המערך (נסמנו 1).
מערך (1) שמכיל את כל אותיות האלפבית. בתא של האות a המצביע אל מערך נוסף אינו null אלא מצביע למערך (נסמנו 2), כל שאר המצביעים במערך זה הם null.
מערך (2) שמכיל את כל אותיות האלפבית. בתא של האות b המצביע אל מערך נוסף אינו null אלא מצביע למערך (נסמנו 3), כל שאר המצביעים במערך זה הם null.
מערך (3) שמכיל את כל אותיות האלפבית. בתא של האות c המצביע אל *ערך* אינו ריק אלא מצביע אל הערך המתאים למפתח abc. בתא של האות d המצביע אל ערך גם אינו ריק אלא מצביע אל הערך המתאים למפתח abd. כמו כן, בתא זה גם המצביע למערך נוסף אינו null אלא מצביע למערך (נסמנו 4), כל שאר המצביעים במערך זה הם null.
מערך (4) שמכיל את כל אותיות האלפבית. בתא של האות d המצביע אל הערך אינו ריק אלא מצביע אל הערך המתאים למפתח abdd. כל שאר המצביעים במערך זה הם null.
כדי לבדוק אם מפתח נמצא במבנה אתה מטייל לפי אותיות המפתח לעומק (ממערך (1) והלאה), ואם הגעת למצב שאינך יכול להתקדם (כי המצביע למערך הבא הוא null), או שהגעת ליעדך ואין שם מצביע לערך, אזי אין ערך שמתאים למפתח הנ"ל במבנה.
מאד נוח להחזיק בצורה כזו מילון של ערכים, כי כפי שציין ירדן, קל מאד להדפיס אותם לפי סדר אלפביתי - ערוך טיול DFS על המבנה והדפס כל צומת שנכנסת אליו לראשונה ושהמצביע לערך שלו אינו null.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש