Trie

पथ के रूप में शब्द

हर शब्द root से एक पथ है, प्रति वर्ण एक edge। cat और car c-a पथ साझा करते हैं फिर अलग होते हैं। Lookup, insert, और prefix जाँच O(L) हैं जहाँ L शब्द की लंबाई — संग्रहीत शब्दों की संख्या से स्वतंत्र।

Insert और search

Node केवल child वर्णों का map और end-of-word flag है।

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node['$'] = True          # word ends here
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return '$' in node

फ़ोन संपर्क

'Jo' टाइप करें और फ़ोन तुरंत John, Joanna, Joseph तक सीमित हो जाता है। यह नामों की trie में दो edge नीचे चला।

यह कहाँ छिपा है

Autocomplete, spell-check, IP routing table, और word-search / prefix समस्याएँ। ट्रेड-ऑफ: प्रति वर्ण भारी पॉइंटर overhead।