מבנה נתונים Trie Tree

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

למה משמש עץ מסוג Trie Tree?

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

מקרי שימוש נפוצים כוללים:

• השלמה אוטומטית וחזוי טקסט: תוך כדי הקלדה, משתמש יכול למצוא במהירות את כל המילים שחולקות את הקידומת שהוא מזין.
• בודקי איות:Tries יכולים לאמת במהירות אם מילה קיימת במילון או להציע תיקונים על ידי חקירת נתיבים סמוכים בעץ.
• ניתוב (IP): נתבים משתמשים בווריאציות של Trie (כמו עצי Radix) כדי לאחסן ולחפש ביעילות את קידומת כתובת ה-IP הארוכה ביותר התואמת כדי לקבוע לאן להעביר פקטות מידע ברשת האינטרנט.
• אחסון יעיל: עצי Trie מספקים אחסון וחיפושים יעילים עבור קבוצות גדולות של מחרוזות, ולעתים קרובות עולים על ביצועי hash tables (מילונים של פייתון מיישמים hash tables) עבור פעולות הקשורות לקידומות.

איך ליישם Trie בפייתון?

יישום של Trie בפייתון כרוך בדרך כלל בהגדרת שני קלאסים:

1. TrieNode לייצוג כל תו.
2. מחלקת Trie לניהול פעולות כמו הכנסה וחיפוש.

להלן יישום פשוט של 2 המחלקות בפייתון:

class TrieNode:
    def __init__(self):
        # A dictionary to store children nodes, where keys are characters
        self.children = {}
        # A flag to mark the end of a complete word
        self.is_end_of_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Inserts a word into the trie."""
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        # Mark the end of the complete word
        current.is_end_of_word = True

    def search(self, word: str) -> bool:
        """Checks if a word exists in the trie."""
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        # Must reach the end of the path AND be marked as a complete word
        return current.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        """Checks if there is any word in the trie that starts with the given prefix."""
        current = self.root
        for char in prefix:
            if char not in current.children:
                return False
            current = current.children[char]
        # Reaching this point means the prefix path exists
        return True

נבדוק שהקוד עובד:

# Test cases
trie = Trie()
    
trie.insert("apple")
trie.insert("app")
trie.insert("banana")
    
print(f"'apple' exists? {trie.search('apple')}")     # Output: True
print(f"'app' exists? {trie.search('app')}")         # Output: True
print(f"'ap' exists? {trie.search('ap')}")           # Output: False (not marked as end of word)
print(f"'orange' exists? {trie.search('orange')}")   # Output: False
    
print(f"Words start with 'app'? {trie.starts_with('app')}") # Output: True
print(f"Words start with 'ora'? {trie.starts_with('ora')}") # Output: False

הערכת ביצועים

Trie (עץ קידומות) פועל ביעילות על מחרוזות, ובדרך כלל מציע סיבוכיות זמן של O(m) להכנסה, חיפוש ומחיקה, כאשר m הוא אורך המחרוזת. סיבוכיות המרחב היא O(n*m), כאשר n הוא המספר הכולל של מילים ו-m הוא האורך הממוצע, אם כי הוא יכול להיות גבוה יותר בהתאם למספר אותיות האלפבית.

מדריכים נוספים שעשויים לעניין אותך

הבנת אלגוריתם חיפוש לרוחב - BFS - סריקה של גרפים ומציאת הנתיב הקצר ביותר

המדריך התמציתי ליישום עץ בינארי בפייתון

Linked list - רשימה מקושרת - תיאוריה, קוד ואתגרים תכנותיים

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים