字典树的数据结构_数据结构快速排序

字典树的数据结构_数据结构快速排序本文主要包括以下内容:Trie字典树的基本概念Trie字典树的基本操作插入查找前缀查询删除基于链表的Trie字典树Set性能对比LeetCode相关线段树的问题LeetCode第208号问题LeetCode第211号问题LeetCode第677号问题Trie字典树的基本概念上一篇我们介绍了线段树(SegmentTree),本文主要介绍Trie字典树…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

本文主要包括以下内容:

  1. Trie字典树的基本概念
  2. Trie字典树的基本操作
    1. 插入
    2. 查找
    3. 前缀查询
    4. 删除
  3. 基于链表的Trie字典树
  4. 基于Trie的Set性能对比
  5. LeetCode相关线段树的问题
    1. LeetCode第208号问题
    2. LeetCode第211号问题
    3. LeetCode第677号问题

Trie字典树的基本概念

上一篇我们介绍了 线段树(Segment Tree),本文主要介绍Trie字典树。

通过前面的介绍我们知道一个线性表的顺序查找的时间复杂度为O(n);二分搜索树的查找为O(log n),它们都和数据结构中的元素个数相关。关于线性表和二分搜索树的时间复杂度分析有需要的可以查看 Set集合和BinarySearchTree的时间复杂度分析

本文介绍的Trie字典树(主要用于存储字符串)查找速度主要和它的元素(字符串)的长度相关[O(w)]。

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

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

这里写图片描述

也就是说如果只考虑小写的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 即可

如下图所示

这里写图片描述

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

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

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

这里写图片描述

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

这里写图片描述

基于链表的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性能对比

在前面的Set集合和BinarySearchTree的时间复杂度分析中我们分别使用了基于链表和基于二分搜索树实现的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 这个属性了,因为不关注是不是一个单词。

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;
}

上面三个LeetCode的问题答案,都可以在我的github上查看

Reference

本文主要内容和大纲是学习了慕课网 liuyubobobo 老师的视频《算法大神带你玩转数据结构 从入门到精通》
有需要的同学可以看看, 真心不错. 墙裂推荐… 最好能加上自己的思考和理解.


下面是我的公众号,干货文章不错过,有需要的可以关注下,有任何问题可以联系我:

公众号: chiclaim

文本相关源代码github

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/196494.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 公有云和私有云的对比和区别「建议收藏」

    公有云和私有云的对比和区别「建议收藏」什么是云?云技术是指在广域网或局域网内将硬件、软件、网络等系列资源统一起来,实现数据的计算、储存、处理和共享的一种托管技术。例如云计算:将计算作为一种服务交付给用户而不是一种产品,在这种服务中,计算资源、软件和信息如同日常的水、电一样通过互联网交付给计算机和其他的计算媒介。​云计算的三种模式​按照商业模式的不同,云计算可以被分为三大类:公有云、私有云和混合云。这三种模式构成了云基础设施构建和消费的基础。​​1、公有云(PublicClouds),“公有”反映了这类云服务并非用户

  • 软件开发模式有哪些(软件工程开发模式)

    软件开发模式简介1.边做边改模型(Build-and-FixModel)  好吧,其实现在许多产品实际都是使用的“边做边改”模型来开发的,特别是很多小公司产品周期压缩的太短。在这种模型中,既没有规格说明,也没有经过设计,软件随着客户的需要一次又一次地不断被修改。  在这个模型中,开发人员拿到项目立即根据需求编写程序,调试通过后生成软件的第一个版本。在提供给用户使用后,如果程序出现错…

  • android碎片整理工具,Android的碎片整理「建议收藏」

    android碎片整理工具,Android的碎片整理「建议收藏」Android手机与平板高级历史橡皮擦和性能的助推器★★★★第一轮中的新工具支付Android上最流行的新的生产力应用程序,下载吧!清除历史搜索,杀敌多余的电池寿命,增加单键的任务!“碎片整理免费的Andr??oid现在是十大最热AppBrain.com应用之一,现在下载”“真棒应用程序”-编辑推荐奖AppEggs.com_________________________________我们现…

  • 自动阅读 到底 能不能赚钱

    自动阅读 到底 能不能赚钱

    2021年11月11日
  • p6使用教程_p6slite使用说明书

    p6使用教程_p6slite使用说明书最近开发中用到spring-data-jpa+hibernate的持久层框架,在调试过程中,日志记录的hibernateSQL执行语句无法显示传入的参数,所以上github上搜索了一番,发现了p6spy这个框架,此框架能够无缝地拦截和记录数据库的执行语句,而不会对现有应用程序进行代码更改。下面介绍一下p6spy的简单配置和使用。源码https://github.com/p6s…

  • 净推荐值NPS(Net Promoter Score)[通俗易懂]

    净推荐值NPS(Net Promoter Score)[通俗易懂]净推荐值净推荐值(NetPromoterScore,NPS)目录[隐藏]1什么是净推荐值2净推荐值的理论基础[3]3净推荐值的计算4净推荐值的意义5净推荐值的评析6净推荐值在企业中的应用分析[3]7企业通过净推荐值提高客户忠诚度的主要步骤[5]8净推荐值提高客户忠诚度的实证分析[5]9净推荐值应用实例10参考文献[编辑]什么是净推荐值  净推荐值(N…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号