数据结构与算法----复习Part 13.5 番外 （字典树）

本系列是算法通关手册LeeCode的学习笔记

算法通关手册（LeetCode） | 算法通关手册（LeetCode） (itcharge.cn)

目录

字典树（Trie）

字典树的结构

字典树的插入和删除操作

字典树（Trie）

        又称前缀树、单词查找树，是一种树形结构。顾名思义就是一个像字典一样的树，他是字典的一种存储方式。字典中的每个单词在字典树中表现为一条从根节点出发的路径，路径相连的边上的字母连起来就形成了对应的字符串。

        例如下图，其中包含有 a, b, ab, acb, acc, ach, chb

         需要留意一下这张图中的特点，节点不存储字符串，只存储信息，其中红色的节点表示有字符在该节点结束了，共有七个红色节点，代表有七个字符串。字符存储在边上，也就是在每个节点指向下一个节点过程上。

字典树的结构

        字典树是一棵多叉树，【多叉】的意思是一个节点可以有多个子节点。而多叉的实现方式可以使用数组实现，也可以用哈希表实现。本篇使用哈希表的形式实现字典树。

class Node:
    def __init__(self):
        self.children = dict()
        self.isEnd = False

        self.children 使用哈希表实现，表示该节点的所有子节点，isEnd 用于标记单词是否结束。这样，如果在插入单词时，根据单词中的字符，创建相应的字符节点，并将其插入到对应的哈希表中。

        在字典树的初始化时，定义一个根节点。并且这个根节点不用保存字符，在后续的插入操作，查找操作都是从字典树的根节点开始的。

class Trie:
    
    def __init__(self):
        self.root = Node()

字典树的插入和删除操作

        字典树的创建指的是将字符串数组中的所有字符串都插入字典树中，而插入操作是将一个字符串插入字典树中。

        插入字符的步骤如下：

                依次遍历单词中的字符 ch，并从字典树的根节点的子节点位置开始进行插入操作；

                如果当前节点的子结点中，不存在键为 ch 的节点，则建立一个节点将其保存到当前节点

        的子结点中；

                如果当前节点的子节点中，存在键为 ch 的节点，则直接令当前节点指向键为 ch 的节点

                单词处理完成时，将当前节点标记为单词结束。

    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = None()
            cur = cur.children[ch]      # 这里对图中，字符在路径上这一特点体现的淋漓尽致
        cur.isEnd = True

字典树的创建：

trie = Trie()
for word in words:
    trie.insert(word)

字符串的查找操作：

        依次遍历单词中的字符，并从字典树的根节点位置开始进行查找操作；

        如果当前节点的子节点中，不存在键为 ch 的节点，则说明不存在该单词，直接返回 False；

        如果当前子节点中，存在键为 ch 的节点，则令当前节点指向新建立的节点，然后继续查找下

一个字符；

        在单词处理完成时，判断当前节点是否有单词结束标记，如果有，则说明字典树中存在该单

词，返回 True。否则，则说明字典树中不存在该单词，返回 Fasle。

    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        
        return cur is not None and cur.isEnd

字典树的查找前缀操作

        在字典树中查找某个前缀是否存在，在字典树的查找单词操作一样，不同点在于最后不需要判断是否有单词结束标记。

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

全部代码如下：

class Node:
    def __init__(self):
        self.children = dict()
        self.isEnd = False

class Trie:

    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = None()
            cur = cur.children[ch]      # 这里对图中，字符在路径上这一特点体现的淋漓尽致
        cur.isEnd = True

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

        return cur is not None and cur.isEnd

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return cur is not None
words = [...]
trie = Trie()
for word in words:
    trie.insert(word)

算法通关手册（LeetCode） | 算法通关手册（LeetCode）

原文内容在这里，如有侵权，请联系我删除。