首页 > 其他分享 >数据结构第28节 字典树

数据结构第28节 字典树

时间：2024-07-15 11:25:22浏览次数：14  
标签：trie 28 public current TrieNode 数据结构 children 字典

字典树（Trie，也称前缀树）是一种用于存储字符串的树形数据结构。它将字符串中的字符作为树的边，每个节点代表一个可能的前缀。字典树非常适合处理大量字符串的搜索、插入和删除操作，尤其是在查找具有相同前缀的字符串时非常高效。

基本概念：

  • 根节点：通常不包含任何数据，它的子节点包含字符串的第一个字符。
  • 内部节点：代表字符串的中间字符。
  • 叶子节点：代表字符串的结束字符，通常会附加一个标志表示该路径是一个完整的单词。

案例分析与实现：

假设我们要实现一个简单的字典树来存储英文单词，比如 “cat”, “cattle”, “dog”, “dodge” 和 “do”。

步骤1: 定义节点类
class TrieNode {
    private final int ALPHABET_SIZE = 26;
    TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = null;
        }
    }
}
步骤2: 实现字典树类
public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // 插入单词到字典树中
    public void insert(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    // 搜索单词是否存在于字典树中
    public boolean search(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current != null && current.isEndOfWord;
    }
}
步骤3: 使用字典树
public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("cattle");
        trie.insert("dog");
        trie.insert("dodge");
        trie.insert("do");

        System.out.println("Search cat: " + trie.search("cat")); // 应输出 true
        System.out.println("Search dog: " + trie.search("dog")); // 应输出 true
        System.out.println("Search do: " + trie.search("do"));   // 应输出 true
        System.out.println("Search dodge: " + trie.search("dodge")); // 应输出 true
        System.out.println("Search dodger: " + trie.search("dodger")); // 应输出 false
    }
}

这个简单的字典树实现了插入和搜索功能。在实际应用中，你可能还需要实现删除、获取所有前缀单词等功能。字典树在拼写检查、自动完成、IP路由选择等领域有着广泛的应用。

当然，我们可以继续扩展字典树的功能，添加删除操作以及遍历字典树以列出所有单词或特定前缀下的单词。以下是完善后的代码：

步骤4: 添加删除功能

为了正确地删除一个单词，我们需要从字典树中移除该单词的路径，但要注意不要移除其他单词的公共前缀。这需要我们递归地检查并删除空闲的节点。

// 删除单词
public boolean delete(String key) {
    return delete(root, key, 0);
}

private boolean delete(TrieNode node, String key, int depth) {
    if (node == null) return false;

    if (depth == key.length()) {
        if (!node.isEndOfWord) return false;

        node.isEndOfWord = false;
        // 如果当前节点没有孩子，则可以删除
        if (isEmpty(node)) {
            node = null;
            return true;
        }
        return false;
    }

    int index = key.charAt(depth) - 'a';
    boolean shouldDeleteCurrentNode = delete(node.children[index], key, depth + 1);

    if (shouldDeleteCurrentNode) {
        node.children[index] = null;
        // 如果当前节点没有任何孩子并且不是单词的结尾，那么删除它
        if (isEmpty(node) && !node.isEndOfWord) {
            return true;
        }
    }
    return false;
}

private boolean isEmpty(TrieNode node) {
    for (int i = 0; i < node.children.length; i++) {
        if (node.children[i] != null) return false;
    }
    return true;
}

步骤5: 遍历字典树

遍历字典树可以让我们打印出所有的单词，或者找到具有特定前缀的所有单词。

// 打印具有给定前缀的所有单词
public void printWordsWithPrefix(String prefix) {
    TrieNode node = get(prefix);
    if (node == null) {
        System.out.println("No words found with the given prefix.");
        return;
    }
    printWords(node, prefix);
}

private void printWords(TrieNode node, String currentString) {
    if (node.isEndOfWord) {
        System.out.println(currentString);
    }

    for (int i = 0; i < node.children.length; i++) {
        if (node.children[i] != null) {
            printWords(node.children[i], currentString + (char)(i + 'a'));
        }
    }
}

// 查找具有给定前缀的节点
private TrieNode get(String key) {
    TrieNode current = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key.charAt(i) - 'a';
        if (current.children[index] == null) {
            return null;
        }
        current = current.children[index];
    }
    return current;
}

现在，我们可以在主函数中使用这些方法：

public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("cat");
    trie.insert("cattle");
    trie.insert("dog");
    trie.insert("dodge");
    trie.insert("do");

    System.out.println("Search cat: " + trie.search("cat"));
    System.out.println("Search dog: " + trie.search("dog"));
    System.out.println("Search do: " + trie.search("do"));
    System.out.println("Search dodge: " + trie.search("dodge"));
    System.out.println("Search dodger: " + trie.search("dodger"));

    trie.printWordsWithPrefix("d");
    trie.delete("cat");
    System.out.println("After deleting 'cat': Search cat: " + trie.search("cat"));
}

这样，我们就有了一个更完整的字典树实现，包括插入、搜索、删除和遍历功能。

在学生成绩管理系统中使用字典树（Trie）来实现增删改查（CRUD）操作是一种创新的方法，尤其是当需要对大量以文本形式存储的数据（如学生姓名）进行快速前缀搜索时。但是，传统的字典树并不直接支持数据的删除或修改操作，因为这些操作可能会影响树的结构。为了简化说明，我们将使用字典树来存储学生姓名，并使用一个额外的数据结构（如HashMap）来关联姓名与成绩，以便于更新和删除操作。

下面是一个使用Java实现的简化版学生成绩管理系统，其中使用字典树来存储学生姓名，并使用HashMap来存储姓名和成绩之间的对应关系。

首先，我们定义字典树的节点类TrieNode：

class TrieNode {
    private final int ALPHABET_SIZE = 26;
    TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = null;
        }
    }
}

然后，定义字典树类Trie：

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String key) {
        TrieNode current = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    public boolean search(String key) {
        TrieNode current = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current != null && current.isEndOfWord;
    }
}

接下来，创建StudentScoreManager类，用于管理学生姓名和成绩：

import java.util.HashMap;

public class StudentScoreManager {
    private Trie studentNames;
    private HashMap<String, Integer> scores;

    public StudentScoreManager() {
        studentNames = new Trie();
        scores = new HashMap<>();
    }

    public void addScore(String name, int score) {
        studentNames.insert(name);
        scores.put(name, score);
    }

    public void updateScore(String name, int score) {
        if (scores.containsKey(name)) {
            scores.put(name, score);
        } else {
            throw new IllegalArgumentException("Student not found.");
        }
    }

    public void deleteScore(String name) {
        if (scores.containsKey(name)) {
            scores.remove(name);
            // 删除字典树中的条目（这里简化处理，不实际删除）
        } else {
            throw new IllegalArgumentException("Student not found.");
        }
    }

    public int getScore(String name) {
        if (scores.containsKey(name)) {
            return scores.get(name);
        } else {
            throw new IllegalArgumentException("Student not found.");
        }
    }

    public boolean checkName(String name) {
        return studentNames.search(name);
    }
}

最后，在main方法中使用StudentScoreManager：

public static void main(String[] args) {
    StudentScoreManager manager = new StudentScoreManager();
    manager.addScore("Alice", 90);
    manager.addScore("Bob", 85);
    manager.addScore("Charlie", 92);

    System.out.println(manager.checkName("Alice")); // 输出 true
    System.out.println(manager.getScore("Bob")); // 输出 85
    manager.updateScore("Charlie", 95);
    System.out.println(manager.getScore("Charlie")); // 输出 95
    manager.deleteScore("Bob");
    System.out.println(manager.checkName("Bob")); // 输出 false
}

在这个示例中，addScore方法同时在字典树和HashMap中添加学生姓名和成绩；updateScore和deleteScore仅更新或删除HashMap中的成绩，而字典树保持不变（为了简单起见，没有实现在字典树中删除节点的功能）。getScore和checkName分别用于获取成绩和检查姓名是否存在。

需要注意的是，这种方法在删除操作上可能会导致字典树中存在“孤儿”节点，如果需要维护一个完全一致的字典树，那么删除操作需要更复杂的逻辑来重构树的结构。

标签：trie,28,public,current,TrieNode,数据结构,children,字典
From： https://blog.csdn.net/hummhumm/article/details/140433847

相关文章

  • 数据结构绪论
    本篇主要介绍数据结构的基本概念和术语数据：数据是信息的载体。数据元素：数据的基本单元，通常作为一个整体进行考虑和处理。数据项：构成数据元素的不可分割的最小单位。数据对象：具有相同性质的数据元素的集合。数据类型原子类型：值不可再分的数据类型结构类型：值可以分解为......
  • 【NOI】C++数据结构入门之一维数组（一）数组基础
    文章目录前言一、概念1.导入2.数组2.1数组的创建2.2数组的使用二、例题讲解问题：1423-考试成绩的简单统计问题：1153-查找“支撑数”问题：1156-排除异形基因问题：1155-找找谁的身高超过全家的平均身高问题：1231-考试成绩的分布情况三、总结四、感谢前言在......
  • 【Python】 深入了解 Python 字典的 | 更新操作
    我白天是个搞笑废物表演不在乎夜晚变成忧伤怪物撕扯着孤独我曾经是个感性动物小心地感触现在变成无关人物                     ......
  • 字典树(Tire树)
    字典树(Tire树)字典树是一种多叉树，又称为前缀树。核心思想是利用字符串的公共前缀。字典树的根节点为空，从根节点到某一节点路径上的字符连接起来构成字符串，完整的字符串在链上而非结点上，一个节点的所有子节点都具有相同公共前缀。普通Tire树structnode{boolend;......
  • 数据结构专题
    [NOIP2012]借教室可以看到答案是有单调性的，若第i个可以那么第i-1个也可以，就可以二分答案，用差分维护区间加，也可以用树状数组#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#definedoublelongdouble#definePIIpair<int,int>constintN=1e6......
  • Python 字典（Dict）详解与实战应用
    目录前言一、字典的定义和创建1.使用花括号定义2.使用dict()函数创建二、字典的三种遍历方式方式1：遍历字典的键，通过键获取值 dict.keys()方式2：遍历字典的值，但不能通过值获取键dict.values()方式3：最常用的方法：直接获取键值对 dict.items()三、字典的常见操作1.添......
  • 【数据结构】图
     目录一、数据结构图的基本概念二、数据结构图的操作2.1图的创建（CreateGraph）2.2输入元素（InputElements）2.3遍历算法（TraversalAlgorithms）2.4搜索算法2.5查找操作（LocateOperation）2.6其他操作三、几种常见的数据结构图3.1UML类图（UnifiedModelingLanguage......
  • sqlalchemy pandas转化字典转为orm写入到sqlite数据库报错类型错误的解决办法
    使用pandas读取csv数据,然后将其转化为字典,再写入到数据库的时候,数据库总是报错类型错误,于是转为orm之前,统一转化一下类型fromsqlalchemyimportDECIMAL,Index,String,Date,Integer,Text,CHAR,SmallInteger,Float,Time,case,and_,extract,TypeDecoratorfrom......
  • 数据结构-栈
    介绍栈是一种线性的数据结构，它具有先进后出的特性。栈是一种“操作受限”的数据结构——栈的插入和弹出都只能在一端进行。正是因为栈的这一个特性，计算机许多底层逻辑都是由栈实现的。栈的操作将元素压入栈查询栈的顶端元素弹出栈的顶端元素C++中栈的实现C++STL中包含栈......
  • 数据结构-黄洛天
    数据结构-黄洛天A-冰火战士题面支持$Q$次两种操作，添加一个三元组$(w,a,b),w\in{0,1}$撤回第$k$此操作，此操作保证为报名信息每次操作后，求$$\max_{x}\min(\sum_{w_i=0,a_i\lex}b_i,\sum_{w_i=1,a_i\gex}b_i)$$以及取到最值的最大的$x$。$1\leQ\le1\times10^......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99