Trie (עץ תחיליות)

1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_word = False5
6
7class Trie:8    def __init__(self):9        self.root = TrieNode()10
11    def insert(self, word):12        node = self.root13        for ch in word:14            node = node.children.setdefault(ch, TrieNode())15        node.is_word = True16
17    def search(self, word):18        node = self._walk(word)19        return node is not None and node.is_word20
21    def starts_with(self, prefix):22        return self._walk(prefix) is not None23
24    def _walk(self, s):25        node = self.root26        for ch in s:27            if ch not in node.children:28                return None29            node = node.children[ch]30        return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35    trie.insert(word)36
37print("search(card):     ", trie.search("card"))38print("search(ca):       ", trie.search("ca"))39print("starts_with(ca):  ", trie.starts_with("ca"))40print("starts_with(do):  ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))

1class TrieNode {2    constructor() {3        this.children = {};4        this.isEnd = false;5    }6}7
8class Trie {9    constructor() {10        this.root = new TrieNode();11    }12
13    insert(word) {14        let node = this.root;15        for (const ch of word) {16            if (!node.children[ch]) node.children[ch] = new TrieNode();17            node = node.children[ch];18        }19        node.isEnd = true;20    }21
22    // Walk the prefix; null when a character is missing23    findNode(prefix) {24        let node = this.root;25        for (const ch of prefix) {26            node = node.children[ch];27            if (!node) return null;28        }29        return node;30    }31
32    search(word) {33        const node = this.findNode(word);34        return node !== null && node.isEnd;35    }36
37    startsWith(prefix) {38        return this.findNode(prefix) !== null;39    }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));

1public class Main {2    static class Node {3        Node[] children = new Node[26];4        boolean isWord;5    }6
7    static Node root = new Node();8
9    static void insert(String word) {10        Node cur = root;11        for (char c : word.toCharArray()) {12            int i = c - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isWord = true;17    }18
19    // Follow the path for s; null means no word has this prefix20    static Node walk(String s) {21        Node cur = root;22        for (char c : s.toCharArray()) {23            cur = cur.children[c - 'a'];24            if (cur == null) return null;25        }26        return cur;27    }28
29    static boolean search(String word) {30        Node node = walk(word);31        return node != null && node.isWord;32    }33
34    static boolean startsWith(String prefix) {35        return walk(prefix) != null;36    }37
38    public static void main(String[] args) {39        insert("code");40        insert("coder");41        insert("cool");42        System.out.println("search code: " + search("code"));43        System.out.println("search cod: " + search("cod"));44        System.out.println("startsWith cod: " + startsWith("cod"));45        System.out.println("startsWith cat: " + startsWith("cat"));46    }47}

1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6    std::unordered_map<char, TrieNode*> children;7    bool isEnd = false;8};9
10struct Trie {11    TrieNode* root = new TrieNode();12
13    void insert(const std::string& word) {14        TrieNode* node = root;15        for (char c : word) {16            if (!node->children.count(c)) node->children[c] = new TrieNode();17            node = node->children[c];18        }19        node->isEnd = true;20    }21
22    // Follow the path for s; nullptr if a link is missing23    TrieNode* walk(const std::string& s) const {24        TrieNode* node = root;25        for (char c : s) {26            auto it = node->children.find(c);27            if (it == node->children.end()) return nullptr;28            node = it->second;29        }30        return node;31    }32
33    bool search(const std::string& word) const {34        TrieNode* node = walk(word);35        return node != nullptr && node->isEnd;36    }37
38    bool startsWith(const std::string& prefix) const {39        return walk(prefix) != nullptr;40    }41};42
43int main() {44    Trie trie;45    for (const std::string& word : {"car", "card", "care", "dog"}) {46        trie.insert(word);47    }48    std::cout << std::boolalpha;49    std::cout << "search(card): " << trie.search("card") << "\n";50    std::cout << "search(ca): " << trie.search("ca") << "\n";51    std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52    std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53    return 0;54}

1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6    struct TrieNode* children[26];7    bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11    return calloc(1, sizeof(TrieNode));  // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15    for (; *word; word++) {16        int i = *word - 'a';17        if (root->children[i] == NULL) root->children[i] = newNode();18        root = root->children[i];19    }20    root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25    for (; *s; s++) {26        root = root->children[*s - 'a'];27        if (root == NULL) return NULL;28    }29    return root;30}31
32bool search(TrieNode* root, const char* word) {33    TrieNode* node = walk(root, word);34    return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38    return walk(root, prefix) != NULL;39}40
41int main(void) {42    TrieNode* root = newNode();43    const char* words[] = {"car", "card", "care", "dog"};44    for (int i = 0; i < 4; i++) insert(root, words[i]);45    printf("search(card): %s\n", search(root, "card") ? "true" : "false");46    printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47    printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48    printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49    return 0;50}