字典树的数据结构

这篇具有很好参考价值的文章主要介绍了字典树的数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Trie字典树主要用于存储字符串,Trie 的每个 Node 保存一个字符。用链表来描述的话,就是一个字符串就是一个链表。每个Node都保存了它的所有子节点。

例如我们往字典树中插入see、pain、paint三个单词,Trie字典树如下所示:

字典树的数据结构,c#,开发语言

也就是说如果只考虑小写的26个字母,那么Trie字典树的每个节点都可能有26个子节点。

Trie字典树的基本操作

插入

本文是使用链表来实现Trie字典树,字符串的每个字符作为一个Node节点,Node主要有两部分组成:

  1. 是否是单词 (boolean isWord)
  2. 节点所有的子节点,用map来保存 (Map next)

例如插入一个paint单词,如果用户查询pain,尽管 paint 包含了 pain,但是Trie中仍然不包含 pain 这个单词,所以如果往Trie中插入一个单词,需要把该单词的最后一个字符的节点的 isWord 设置为 true。所以为什么Node需要存储 是否是单词 这个属性。

节点的所有子节点,通过一个Map来存储,key是当前子节点对应的字符,value是子节点。

实现的伪代码如下:

public void add(String word) {
	Node current = root;
	char[] cs = word.toCharArray();
	for (char c : cs) {
		Node next = current.next.get(c);
		if (next == null) {
		    //一个字符对应一个Node节点
			current.next.put(c, new Node());
		}
		current = current.next.get(c);
	}
	//current就是word的最后一个字符的Node
	
	//如果当前的node已经是一个word,则不需要添加
	if (!current.isWord) {
		size++;
		current.isWord = true;
	}
}

复制

查找

Trie查找操作就比较简单了,遍历带查找的字符串的字符,如果每个节点都存在,并且待查找字符串的最后一个字符对应的Node的 isWord 属性为 true ,则表示该单词存在,伪代码如下:

public boolean contains(String word) {
	Node current = root;
	for (int i = 0; i < word.length(); i++) {
		char c = word.charAt(i);
		Node node = current.next.get(c);
		if (node == null) {
			return false;
		}
		current = node;
	}
	//current就是word的最后一个字符的Node
	return current.isWord;
}

复制

前缀查询

前缀查询和上面的查询操作基本类似,就是不需要判断 isWord

public boolean containsPrefix(String prefix) {
    Node current = root;
    for (int i = 0; i < prefix.length(); i++) {
        char c = prefix.charAt(i);
        Node node = current.next.get(c);
        if (node == null) {
            return false;
        }
        current = node;
    }
    return true;
}

复制

删除

Trie的删除操作就稍微复杂一些,主要分为以下3种情况:

如果单词是另一个单词的前缀

如果待删除的单词是另一个单词的前缀,只需要把该单词的最后一个节点的 isWord 的改成false

比如Trie中存在 pandapan 这两个单词,删除 pan ,只需要把字符 n 对应的节点的 isWord 改成 false 即可

如下图所示

字典树的数据结构,c#,开发语言

如果单词的所有字母的都没有多个分支,删除整个单词

如果单词的所有字母的都没有多个分支(也就是说该单词所有的字符对应的Node都只有一个子节点),则删除整个单词

例如要删除如下图的see单词,如下图所示:

字典树的数据结构,c#,开发语言

如果单词的除了最后一个字母,其他的字母有多个分支

字典树的数据结构,c#,开发语言

基于链表的Trie字典树

public class Trie {
private Node root;
private int size;
private static class Node {
public boolean isWord;
public Map<Character, Node> next;
public Node() {
next = new TreeMap<>();
}
public Node(boolean isWord) {
this();
this.isWord = isWord;
}
}
public Trie() {
root = new Node();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 插入操作
*
* @param word 单词
*/
public void add(String word) {
Node current = root;
char[] cs = word.toCharArray();
for (char c : cs) {
Node next = current.next.get(c);
if (next == null) {
current.next.put(c, new Node());
}
current = current.next.get(c);
}
//如果当前的node已经是一个word,则不需要添加
if (!current.isWord) {
size++;
current.isWord = true;
}
}
/**
* 是否包含某个单词
*
* @param word 单词
* @return 存在返回true,反之false
*/
public boolean contains(String word) {
Node current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
Node node = current.next.get(c);
if (node == null) {
return false;
}
current = node;
}
//如果只存在 panda这个词,查询 pan,虽然有这3个字母,但是并不存在该单词
return current.isWord;
}
/**
* Trie是否包含某个前缀
*
* @param prefix 前缀
* @return
*/
public boolean containsPrefix(String prefix) {
Node current = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
Node node = current.next.get(c);
if (node == null) {
return false;
}
current = node;
}
return true;
}
/*
* 1,如果单词是另一个单词的前缀,只需要把该word的最后一个节点的isWord的改成false
* 2,如果单词的所有字母的都没有多个分支,删除整个单词
* 3,如果单词的除了最后一个字母,其他的字母有多个分支,
*/
/**
* 删除操作
*
* @param word
* @return
*/
public boolean remove(String word) {
Node multiChildNode = null;
int multiChildNodeIndex = -1;
Node current = root;
for (int i = 0; i < word.length(); i++) {
Node child = current.next.get(word.charAt(i));
//如果Trie中没有这个单词
if (child == null) {
return false;
}
//当前节点的子节点大于1个
if (child.next.size() > 1) {
multiChildNodeIndex = i;
multiChildNode = child;
}
current = child;
}
//如果单词后面还有子节点
if (current.next.size() > 0) {
if (current.isWord) {
current.isWord = false;
size--;
return true;
}
//不存在该单词,该单词只是前缀
return false;
}
//如果单词的所有字母的都没有多个分支,删除整个单词
if (multiChildNodeIndex == -1) {
root.next.remove(word.charAt(0));
size--;
return true;
}
//如果单词的除了最后一个字母,其他的字母有分支
if (multiChildNodeIndex != word.length() - 1) {
multiChildNode.next.remove(word.charAt(multiChildNodeIndex + 1));
size--;
return true;
}
return false;
}
}

复制

基于Trie的Set性能对比

现在使用Trie实现下Set集合,然后三者性能做一个比较,还是以傲慢与偏见双城记战争与和平三本原著作为数据源。

傲慢与偏见(Pride and Prejudice)的性能对比

Pride and Prejudice
Total words: 125901
Total different words: 6530
TrieSet       Time: 0.099788784
BSTSet        Time: 0.339963625
LinkedListSet Time: 3.554973381

复制

从中可以看出傲慢与偏见不同的单词只有6000左右,阅读难度不是很大。

双城记(A Tale of Two Cities)的性能对比

A Tale of Two Cities
Total words: 141489
Total different words: 9944
TrieSet       Time: 0.119505174
BSTSet        Time: 0.331334495
LinkedListSet Time: 5.26063235

复制

战争与和平(War and peace)的性能对比

War and Peace
Total words: 602359
Total different words: 16725
TrieSet       Time: 0.09750872
BSTSet        Time: 0.233328074

复制

以上关于原著词汇的统计只是简单的对比单词是否一致,并没有考虑一个单词的过去式、进行时等时态,只要字符串不一致都把它当作不同的单词。

更多关于Trie的话题

上面实现的Trie中,我们是使用TreeMap来保存节点的所有的子节点,也可以使用HashMap来保存所有的子节点,效率更高:

public Node() {
next = new HashMap<>();
}

复制

当然我们也可以使用一个定长的数组来存储所有的子节点,效率比HashMap更高,因为不需要使用hash函数:

public Node(boolean isWord){
this.isWord = isWord;
next = new Node[26];//只能存储26个小写字母
}

复制

Trie查询效率非常高,但是对空间的消耗还是挺大的,这也是典型的空间换时间。

可以使用 压缩字典树(Compressed Trie) ,但是维护相对来说复杂一些。

如果我们不止存储英文单词,还有其他特殊字符,那么维护子节点的集合可能会更多。

可以对Trie字典树做些限制,比如每个节点只能有3个子节点,左边的节点是小于父节点的,中间的节点是等于父节点的,右边的子节点是大于父节点的,这就是三分搜索Trie字典树(Ternary Search Trie)

LeetCode相关线段树的问题

LeetCode第208号问题

问题描述:

实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

复制

问题说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。

这个问题在我们实现的 Trie字典树 中已经实现了这个功能了,add()就是对应的insert(),contains()就是对应的search(),starcontainsPrefix()就是对应的startsWith(),这里就不贴代码了。

LeetCode第211号问题

问题描述:

设计一个支持以下两种操作的数据结构:

void addWord(word)
bool search(word)
search(word) 

复制

可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z. 可以表示任何一个字母。

示例:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

复制

问题说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

这个问题就是上一个问题的基础上加上 . 的处理,稍微复杂点。

如果下一个字符是 . ,那么需要遍历该节点的所有子节点,对所有子节点的处理就是一个递归程序:

public boolean searchByWildCard(String express) {
return search(root, express, 0);
}
private boolean search(Node node, String express, int index) {
//如果已经到了待查询字符串的尾端了
if (index == express.length()) {
return node.isWord;
}
char c = express.charAt(index);
if (c != '.') {
Node nextChar = node.next.get(c);
if (nextChar == null) {
return false;
}
return search(nextChar, express, index + 1);
} else {//如果是通配符
Map<Character, Node> nextNodes = node.next;
//遍历所有的子节点
for (Map.Entry<Character, Node> entry : nextNodes.entrySet()) {
if (search(entry.getValue(), express, index + 1)) {
return true;
}
}
return false;
}
}

复制

LeetCode第677号问题

问题描述:

实现一个 MapSum 类里的两个方法,insert 和 sum。

对于方法 insert,你将得到一对(字符串,整数)的键值对。字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。

对于方法 sum,你将得到一个表示前缀的字符串,你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5

复制

总结一句话就是,求出所有符合该前缀的字符串的键值的总和。

节点需要保存一个键值,用于求和。节点Node不需要维护 isWord 这个属性了,因为不关注是不是一个单词。文章来源地址https://www.toymoban.com/news/detail-533324.html

class Node {
public int value;
public Map<Character, Node> next;
}
public int sum(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
Node node = cur.next.get(c);
if (node == null) {
return 0;
}
cur = node;
}
//cur指向prefix的最后一个字符的Node
//对每个以prefix为前缀的node进行累加
return countValue(cur);
}
private int countValue(Node node) {
int result = node.value;
for (char c : node.next.keySet()) {
result += countValue(node.next.get(c));
}
return result;
}

到了这里,关于字典树的数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉树的前中后序遍历(C语言)

    [二叉树] 顾名思义就是有 两个分支节点的树,不仅如此,除了叶子外的所有节点都具有两个分支节点; 由于结构像一棵倒立的树,顾名思义为二叉树 ; 如下图所示,该图即为一棵 野生的二叉树 ; 既然二叉树为树,固然有着和树一样的部分( 叶子、根、分支… ) 这些也成为

    2024年02月17日
    浏览(41)
  • 二叉树的基本操作-C语言实现-数据结构作业

    目录  (1)二叉树的创建; (2)二叉树的先序、中序和后序遍历输出; (3)输出二叉树的叶子节点和度为2的节点的数量; (4)输出二叉树的深度; (5)将二叉树所有节点的左右子树互换(左子树变右子树,右子树变左子树); (6)参考书上,二叉树按层次输出(一行输出一层); (7)删除二

    2024年02月04日
    浏览(46)
  • 数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ,需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ,一个是 数据结构 ,一

    2023年04月19日
    浏览(50)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(48)
  • 《数据结构C语言版》——树、森林与二叉树的转换(超详图解)

    哈喽!这里是一只派大鑫,不是派大星。本着基础不牢,地动山摇的学习态度,从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编程(或是应付期末考试 狗头.jpg)的大家能够在学习阶段找到好的方法、路线,让天下没有难学的程序(只有秃头的程

    2024年02月10日
    浏览(38)
  • C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)

    1、若左子树不为空,左子树上所有节点值小于 它根节点的值 2、若右子树不为空,右子树上所有节点值大于 它根节点的值 3、每个节点的左右子树也是二叉排序树 目的:提高查找、插入、删除的速度(不是为了排序) 时间复杂度:由于查找性能取决于树的形态,所以

    2024年02月09日
    浏览(48)
  • 14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

    概述:         二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对

    2024年02月11日
    浏览(42)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(43)
  • 数据结构---字典树(Tire)

    字典树是一种能够快速插入和查询字符串的多叉树结构,节点的编号各不相同,根节点编号为0 Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。 核心思想也是通过空间来换取时间上的效率 在一定情况下字典树的效率要比哈希表要高 字典树

    2024年02月21日
    浏览(45)
  • 【Redis】基础数据结构-字典

    基本语法 字典是Redis中的一种数据结构,底层使用哈希表实现,一个哈希表中可以存储多个键值对,它的语法如下,其中KEY为键,field和value为值(也是一个键值对): 根据Key和field获取value: 哈希表 数据结构 dictht dictht是哈希表的数据结构定义: table:哈希表数组,数组中的

    2024年02月07日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包