ტრი (prefix tree) არის ხე, სადაც თითოეული edge წარმოადგენს სიმბოლოს და თითოეული ფესვიდან გამომავალი ბილიკი წარმოადგენს პრეფიქსს. სიტყვები, რომლებიც იზიარებენ პრეფიქსს, იზიარებენ იმავე ბილიკს, რაც პრეფიქსის ძებნას უკიდურესად სწრაფს ხდის.
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word): # O(L), L = word length
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def starts_with(self, prefix): # O(L)
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True
| ოპერაცია | დრო |
|---|---|
| ჩასმა | O(L) |
| ძებნა | O(L) |
| პრეფიქსის ძიება | O(L) |
მნიშვნელოვნად, ღირებულება დამოკიდებულია სიტყვის სიგრძეზე L, არა შენახული სიტყვების რაოდენობაზე.
ტრი ის პირდაპირმა რედაქტორი ავტოსრულებას, მართლწერის შემმოწმებელს, IP მარშრუტიზაციის ცხრილებს და ლექსიკონზე დაფუძნებულ ძებნას, სადაც პრეფიქსის შესატყვისობა მნიშვნელოვნია.
ika hash set მხოლოდ "ზუსტი შესატყვისობის" შეკითხვაზე პასუხობს, ტრი დამატებით პასუხობს "რა სიტყვებით იწყება X?" ეფექტურად.