Trie (ต้นไม้คำนำหน้า) คือต้นไม้ที่ ขอบ แต่ละขอบแสดงถึงอักขระ และเส้นทางจากรูต แต่ละเส้นทางแสดงถึงคำนำหน้า คำที่แชร์คำนำหน้าเดียวกันแชร์เส้นทางเดียวกัน ซึ่งทำให้การค้นหาคำนำหน้าเร็วมากขึ้น
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
| การดำเนิน | เวลา |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |
สำคัญคือ ค่าใช้จ่ายขึ้นอยู่กับ ความยาวของคำ L ไม่ใช่ จำนวนคำที่เก็บไว้
Trie ขับเคลื่อน autocomplete ตัวตรวจสอบการสะกด ตารางเส้นทาง IP และการค้นหาตามพจนานุกรม โดยที่การจับคู่คำนำหน้า มีความสำคัญ
ในขณะที่ชุด hash ตอบเพียง "ตรงกันแน่นอน" trie ยังตอบ "คำใดบ้างที่เริ่มต้นด้วย X?" ได้อย่างมีประสิทธิภาพ