简单字典树实现

MonoLog 发布于2019-07-31 11:32 / 858人阅读

摘要：查找操作查询指定单词是否在字典树中。将单词标记为当前单词，将根节点标记为当前节点，执行操作当前单词为空，那么返回，即字典树中存在该单词。字典树的简单实现插入操作查找操作删除操作具体实现放在上，可以在这里找到。

原文地址

字典树介绍

我们经常会在网上输入一些单词，一般情况下，当我们输入几个字母时，输入框中会自动弹出以这些字母开头的单词供我们选择，用户体验非常好。

不过这种自动提示功能到底是怎么实现的呢？这就要用到我们的前缀树了，前缀树也叫字典树、Trie树。假如我们有一个简单的字典，里面包含以下几个单词：apps apple cook cookie cold，那么可以构建以下树：

图1. 简单的字典树

当我们输入a时，程序会遍历a的子树，找出所有的单词，这里就是apps和apple了。继续输入ppl，那么只用遍历appl下面的子树，然后即得到apple。同理，输入co时，会遍历o下面的子树，取得单词cook, cookie, cold。这里的单词不一定都在叶节点上，像上例中的cook就是在其中一个子节点上。

从上面的图中，我们可以总结出字典树的一些特征来：

根节点不包含字符，除去根节点的每一个节点均包含有一个字符。

从根节点到某一节点，路径上经过的所有节点的字符连接起来就是该节点对应的字符串。

每个节点的所有子节点包含的字符都不相同。

字典树的基本操作

字典树有三个基本操作：插入，查找，删除：

插入操作：向字典树中插入某个单词。将单词标记为当前单词，将根节点标记为当前节点，执行操作1：

当前单词为空，将当前节点标记为单词位置，终止操作；否则取出当前单词的首字符记为X，遍历当前节点的子节点：如果X存在于子节点N，将剩余字符标记为当前单词，将N标记为当前节点，重复操作1，如果X不存在于当前节点的子节点中，那么进入操作2。

取出当前单词的首字符记为X，新建一个节点M存储X，M的父节点为当前节点。剩余字符串记为当前单词，如果当前单词为空，将M标记为单词位置，终止操作；否则，将M标记为当前节点，重复操作2。

查找操作：查询指定单词是否在字典树中。将单词标记为当前单词，将根节点标记为当前节点，执行操作1：

当前单词为空，那么返回true，即字典树中存在该单词。否则，取出当前单词的首字符，标记为X，遍历当前节点的子节点，如果X存在于子节点N中，将N标记为当前节点，将剩余字符串标记为当前单词，重复操作1；如果X不存在于子节点中，返回false，即字典树中不存在该单词。

删除操作：删除字典树中的某个单词。将单词标记为当前单词，将根节点标记为当前节点，执行操作1：

当前单词为空，如果当前节点不为叶子节点，那么取消标记当前节点为单词位置，当前节点为叶子节点，删除该叶子节点即可，然后终止操作。当前单词不为空，取出当前单词的首字符记为X，遍历当前节点的子节点：如果X存在于当前节点的子节点N上，将N标记为当前节点，将剩余字符串记为当前单词，重复过程1；否则删除失败，即单词不在字典树上，终止操作。

字典树的简单实现

插入操作：

def insert(word):
    current_word = word
    current_node = root
    insert_operation_1(current_word, current_node)

def insert_operation_1(current_word, current_node):
    if current_word not empty:
        X = current_word[0]

        if X in current_node.child:
            current_word = current_word[1:]
            current_node = child_node
            insert_operation_1(current_word, current_node)
        else:
            insert_operation_2(current_word, current_node)

    else:
        mark current_node insert_node 

def insert_operation_2(current_word, current_node):
    X = current_word[0]
    M.value = x
    M.father = current_node
    current_node.child = M

    current_word = current_word[1:]
    if current_word not empty:
        current_node = M
        insert_operation_2(current_word, current_node)

    else:
        mark M insert_node

查找操作：

def find(word):
    current_word = word
    current_node = root
    return find_opration(current_word, current_node)

def find_opration(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            if current_word not empty:
                return find_opration(current_word, current_node)
            else:
                return current_node.isword
        else:
            return false
    else:
        return true

删除操作：

def delete(word):
    current_word = word
    current_node = root
    return delete_operation(current_word, current_node)

def delete_operation(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            is_deleted = delete_operation(current_word, current_node)
        else:
            return false
    else:
        if current_node have child_node:
            mark current_node no_word_node
        else:
            delete current_node
        return true

具体实现放在gist上，可以在这里找到。

参考

6天通吃树结构—— 第五天 Trie树
从Trie树（字典树）谈到后缀树
数据结构之Trie树

云服务器 GPU云服务器字典树 java字典树查询决策树c语言实现 java实现2-3树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45284.html

大展身手的字典树

摘要：原文地址在简单字典树的实现一文中，我们以单词输入自动提示为引子，简单介绍了字典树的实现。前缀匹配本文讲述前缀匹配的字典树实现方案。在简单字典树的实现一文中，我们已经实现了字典树的基本操作，这里只需要再加上一个前缀匹配方法即可。原文地址在简单字典树(Trie)的实现一文中，我们以单词输入自动提示为引子，简单介绍了字典树的实现。那么，字典树到底可以用于哪些场合呢？前缀匹配：给定字典...

Anchorer 2019-07-24 17:36 评论0 收藏0
Trie树 php 实现敏感词过滤

摘要：在树中，每个节点表示一个状态，每条边表示一个字符，从根节点到叶子节点经过的边即表示一个词条。查找一个词条最多耗费的时间只受词条长度影响，因此的查找性能是很高的，跟哈希算法的性能相当。 Last-Modified: 2019年5月10日15:25:35 参考文章 c++ 使用map实现Trie树关键词过滤扩展，用于检查一段文本中是否出现敏感词，基于Double-Array Trie...

王笑朝 2019-07-01 12:46 评论0 收藏0
一种字典树结构的高效实现

摘要：另一种高效实现下面介绍另一种实现，它将字典树用数组存储起来，不仅压缩了数组，而且不降低查找效率。这就是双数组字典树。字典树的心得体会常见的字典树实现方法 class Node{ uint node ; uint[] next; }; 或者类似如下结构 class Node{ uint node; map n...

kycool 2019-08-14 17:44 评论0 收藏0
准备下次编程面试前你应该知道的数据结构

摘要：以下内容编译自他的这篇准备下次编程面试前你应该知道的数据结构瑞典计算机科学家在年写了一本书，叫作算法数据结构程序。国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程序员面试中需要掌...

desdik 2019-08-23 14:57 评论0 收藏0
准备下次编程面试前你应该知道的数据结构

摘要：以下内容编译自他的这篇准备下次编程面试前你应该知道的数据结构瑞典计算机科学家在年写了一本书，叫作算法数据结构程序。国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程序员面试中需要掌...

chadLi 2019-08-16 14:48 评论0 收藏0