前缀树/字典树Trie

目录

一、Trie的数据结构

二、代码示例

一、Trie的数据结构

Tire通常包括：
1.root节点(根节点)：插入、查找、删除、遍历等操作从root节点开始.
2.flag：结束标志true/false，用于表示当前节点是否为一个完整的字符串的结尾.
3.key：每个节点代表一个字符，这个字符是组成字符串的一部分.
4.children：一个节点的孩子节点.
5.data：key代表一个字符，多个key组合起来所表示的数据.
6.parent(可选)：当前父节点，有助于回溯到根节点，通常用于删除、修改等操作.

class TrieNode:
    def __init__(self, key):
        # 每一个节点代表一个字符，当然你可以用char等命名
        self.key = key

        # 表示这个节点是否是一个单词的结尾
        self.flag_end = False

        # 可能包含任何相关的数据，例如完整的单词、完整的词语、一个URL等等
        self.data = None

        # 孩子节点，值是下一个TrieNode
        self.children = {}

        # 父节点，值是上一个TrieNode
        self.parent = None

function TrieNode(key) {
    this.key = key;
    this.flag_end = false;
    this.data = data;
    this.children = {};
    this.parent = null;
}

以下是前缀树的一些主要特点和用途：

1. 路径表示单词：在前缀树中，每个节点可能包含多个子节点，每个子节点代表在当前字符后可能出现的下一个字符。沿着从根节点到某个特定节点的路径可以形成一个字符串。

2. 共享前缀：前缀树可以高效地处理具有共同前缀的字符串集合。如果多个字符串有相同的前缀，它们将共享前缀树中的一条路径，这使得前缀树在空间使用上非常高效。

3. 快速搜索：前缀树允许以O(m)的时间复杂度进行搜索，其中m是要搜索的字符串的长度。这是因为每个步骤沿着树的路径只需要查找下一个字符。

4. 自动补全：前缀树是实现自动补全功能的理想数据结构，因为它可以快速找到具有共同前缀的所有字符串。

5. 词频统计：前缀树可以用来统计和排序大量字符串（如单词）的频率。

6. 拼写检查：它可以用来进行拼写检查，因为它可以快速告诉你一个单词是否在字典中。

7. 字符串排序：前缀树可以用来对字符串进行字典序排序。

8. 空间效率：尽管前缀树在最坏情况下可能空间效率低下（每个节点只有一个子节点），但对于有共同前缀的字符串集合，前缀树通常比其他数据结构更节省空间。

二、代码示例

class TrieNode {
        constructor(key) {
        this.key = key;
        this.parent = null;
        this.children = {};
        this.end = false;
        this.url = null;
    }

    findURL() {
        if (this.end) {
            return this.url;
        }
        return null;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode(null);
    }

    insert(word, url) {
        let node = this.root;

        for (let i = 0; i < word.length; i++) {
            if (!node.children[word[i]]) {
                node.children[word[i]] = new TrieNode(word[i]);
                node.children[word[i]].parent = node;
            }

            node = node.children[word[i]];

            if (i === word.length - 1) {
                node.end = true;
                node.url = url;
            }
        }
    }

    search(word) {
        let node = this.root;

        for (let i = 0; i < word.length; i++) {
            if (node.children[word[i]]) {
                node = node.children[word[i]];
            } else {
                return null;
            }
        }

        return node.findURL();
    }
}

var trie = new Trie();
trie.insert("Ja", "http://www.baidu.com");
trie.insert("Java", "http://www.bilbil.com");
trie.insert("JaC++", "http://www.youtube.com");
trie.insert("ScPy", "http://www.coze.com");
trie.insert("Script", "http://www.sklearn.com");
trie.insert("Go", "http://www.google.com");