Python 字典树的变体：压缩字典树、三分搜索树等

2023-04-11 00:00:00 压缩字典变体

压缩字典树（Trie-树）

Trie-树是一种特殊的字典树，它以空间换时间的方式，将相同前缀的节点进行压缩，从而减少存储空间。在 Trie-树中，每个节点表示一个字符串的前缀，每条边表示一个字符，从根节点到叶子节点的路径表示一个完整的字符串。

以下是 Trie-树的实现：

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

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

def insert(self, word: str) -> None:
    current = self.root
    for ch in word:
        if ch not in current.children:
            current.children[ch] = TrieNode()
        current = current.children[ch]
    current.is_end = True

def search(self, word: str) -> bool:
    current = self.root
    for ch in word:
        if ch not in current.children:
            return False
        current = current.children[ch]
    return current.is_end

def startsWith(self, prefix: str) -> bool:
    current = self.root
    for ch in prefix:
        if ch not in current.children:
            return False
        current = current.children[ch]
    return True

注意，此实现并没有进行压缩操作，而是使用普通的 Trie-树实现。如果需要实现压缩 Trie-树，可以在每个节点中添加一个计数器，表示以该节点为结尾的单词数量。当计数器为 1 时，就可以合并该节点与其父节点。

三分搜索树

三分搜索树是一种特殊的字典树，它的每个节点有三个指针，分别指向小于、等于、大于当前节点的元素。在三分搜索树中，每个节点表示一个字符，从根节点到叶子节点的路径表示一个完整的字符串。

以下是三分搜索树的实现：

class TSTNode:
def init(self, val: str):
self.val = val
self.left = None
self.mid = None
self.right = None
self.is_end = False

class TST:
def init(self):
self.root = None

def insert(self, word: str) -> None:
    def _insert(node: TSTNode, i: int) -> TSTNode:
        if not node:
            node = TSTNode(word[i])
        if word[i] < node.val:
            node.left = _insert(node.left, i)
        elif word[i] > node.val:
            node.right = _insert(node.right, i)
        elif i < len(word) - 1:
            node.mid = _insert(node.mid, i + 1)
        else:
            node.is_end = True
        return node

    self.root = _insert(self.root, 0)

def search(self, word: str) -> bool:
    def _search(node: TSTNode, i: int) -> bool:
        if not node:
            return False
        if word[i] < node.val:
            return _search(node.left, i)
        elif word[i] > node.val:
            return _search(node.right, i)
        elif i == len(word) - 1:
            return node.is_end
        else:
            return _search(node.mid, i + 1)

    return _search(self.root, 0)

def startsWith(self, prefix: str) -> bool:
    def _startsWith(node: TSTNode, i: int) -> bool:
        if not node:
            return False
        if prefix[i] < node.val:
            return _startsWith(node.left, i)
        elif prefix[i] > node.val:
            return _startsWith(node.right, i)
        elif i == len(prefix) - 1:
            return True
        else:
            return _startsWith(node.mid, i + 1)

    return _startsWith(self.root, 0)

注意，由于每个节点有三个指针，因此在插入和搜索时需要对字符进行比较，比较顺序为左、中、右。

相关文章