מהו Trie?

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

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

כל צומת בטריי מכיל שני פריטי מצב:

• children: מפה מתו לתו הבא TrieNode.
• isEndOfWord: דגל שערכו true כאשר המסלול מהשורש לצומת הזה מאיית מילה שלמה שהוכנסה.

חמש הפעולות העיקריות בטריי הן:

1. הכנסה: הוספת מילה תוך יצירת הצמתים החסרים בדרך.
2. חיפוש: בדיקה אם מילה שלמה מאוחסנת.
3. מתחיל ב: בדיקה אם למילה מאוחסנת כלשהי יש את התחילית הנתונה.
4. מחיקה: הסרת מילה וגיזום ענפים מתים.
5. ספירת מילים: ספירת מספר המילים הייחודיות המאוחסנות.

בואו נבנה מחלקת Trie!