คลาส TrieNode: แทรกและค้นหา

Trie คืออะไร

การออกแบบคลาส TrieNode

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False  # True if a word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def __repr__(self):
        return f'Trie(root with {len(self.root.children)} children)'

t = Trie()
print(t)  # Trie(root with 0 children)

การดำเนินการ insert

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)

การดำเนินการ search

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end  # must be a complete word

t = Trie()
t.insert('apple')
print(t.search('apple'))   # True
print(t.search('app'))     # False (app not inserted)
print(t.search('orange'))  # False

การขึ้นต้นด้วย (การค้นหาคำนำหน้า)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True  # prefix path exists

t = Trie()
t.insert('apple')
print(t.starts_with('app'))   # True
print(t.starts_with('ape'))   # False
print(t.search('app'))         # False (not inserted)

ความซับซ้อนด้านเวลาและพื้นที่

การใช้อาร์เรย์แทนพจนานุกรม

class TrieNodeArray:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class TrieArray:
    def __init__(self):
        self.root = TrieNodeArray()
    
    def insert(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = TrieNodeArray()
            node = node.children[idx]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None: return False
            node = node.children[idx]
        return node.is_end

t = TrieArray()
t.insert('cat')
print(t.search('cat'))  # True
print(t.search('car'))  # False

การดำเนินการลบ

การนับคำด้วยคำนำหน้า

class TrieNodeCount:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # words passing through this node

class TrieCount:
    def __init__(self):
        self.root = TrieNodeCount()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNodeCount()
            node = node.children[c]
            node.count += 1  # increment on each level
        node.is_end = True
    
    def count_with_prefix(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return 0
            node = node.children[c]
        return node.count

t = TrieCount()
for w in ['apple','app','application','apply']:
    t.insert(w)
print(t.count_with_prefix('app'))   # 4
print(t.count_with_prefix('appl'))  # 3

การเปรียบเทียบ Trie กับตารางแฮช

Trie ในระบบจริง

ตรวจสอบความเข้าใจ

สรุปบทเรียน