]

एक TRIE के प्रमुख गुण:

नोड्स

---

: प्रत्येक नोड एक वर्ण का प्रतिनिधित्व करता है।

]

]
1. ]
बुनियादी TRIE संचालन:
2. 1। सम्मिलन
3. ] 2। खोज
4. ] 3। उपसर्ग खोज

]

---

जावास्क्रिप्ट में बुनियादी TRIE का कार्यान्वयन:

वर्ग trienode { कंस्ट्रक्टर () { this.children = {}; // बच्चे नोड्स स्टोर करें this.isendofword = false; // एक शब्द के अंत को चिह्नित करता है } } क्लास ट्राई { कंस्ट्रक्टर () { this.root = new trienode (); } // एक शब्द डालें डालें (शब्द) { चलो नोड = this.root; के लिए (शब्द का चार) { if (node.children [char]) { node.children [char] = new trienode (); } नोड = node.children [char]; } node.isendofword = true; // शब्द के अंत को चिह्नित करें } // एक शब्द के लिए खोजें खोज (शब्द) { चलो नोड = this.root; के लिए (शब्द का चार) { if (node.children [char]) { विवरण झूठा है; } नोड = node.children [char]; } Node.isendofword लौटें; } // जांचें कि क्या कोई शब्द दिए गए उपसर्ग के साथ शुरू होता है StartSwith (उपसर्ग) { चलो नोड = this.root; के लिए (उपसर्ग के चार) { if (node.children [char]) { विवरण झूठा है; } नोड = node.children [char]; } सच लौटें; } } // उदाहरण उपयोग const trie = new trie (); trie.insert ("Apple"); कंसोल.लॉग (trie.search ("Apple")); // सत्य कंसोल.लॉग (trie.search ("app")); // असत्य कंसोल.लॉग (trie.startswith ("app")); // सत्य trie.insert ("ऐप"); कंसोल.लॉग (trie.search ("app")); // सत्य

उन्नत ट्राई संचालन:

1।

एक शब्द हटाएं : ]

हटाएं if (गहराई === शब्द। Length) { if (node.isendofword) झूठी वापसी; // शब्द मौजूद नहीं है node.isendofword = false; वापसी ऑब्जेक्ट ।keys (Node.children) .length === 0; // जाँच करें कि क्या नोड के बच्चे हैं } const char = शब्द [गहराई]; if (node.children [char]) झूठी वापसी; const को contdeletechild = this.delete (शब्द, node.children [char], गहराई 1); if DELETE NODE.CHILDRENS [CHAR]; object.keys (node.children) .length === 0 &&! node.isendofword; } विवरण झूठा है; }

2। एक उपसर्ग के साथ शब्दों को गिनें :

गिनती करें कि कितने शब्द किसी दिए गए उपसर्ग के साथ शुरू होते हैं।

---

countwordswithprefix (उपसर्ग) { चलो नोड = this.root; के लिए (उपसर्ग के चार) { if (node.children [char]) रिटर्न 0; नोड = node.children [char]; } This._countwords (नोड) लौटें; } _Countwords (नोड) { गिनती = node.isendofword? 1: 0; के लिए (node.children में चार चलो) { गिनती = this._countwords (node.children [char]); } वापसी की गिनती; }

3।

class TrieNode {
    constructor() {
        this.children = {}; // Stores child nodes
        this.isEndOfWord = false; // Marks the end of a word
    }
}

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

    // Insert a word
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

:

---

]

getwordswithprefix (उपसर्ग) { चलो नोड = this.root; के लिए (उपसर्ग के चार) { if (node.children [char]) वापसी []; नोड = node.children [char]; } This._collectwords (नोड, उपसर्ग) वापस करें; } _CollectWords (नोड, उपसर्ग) { परिणाम दें = []; if (node.isendofword) results.push (उपसर्ग); के लिए (node.children में चार चलो) { परिणाम = results.concat (this._collectwords (node.children [char], उपसर्ग char)); } परिणाम लौटाएं; }

समय जटिलता:

डालें

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth   1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

खोज : o (l)

उपसर्ग खोज
: o (l)

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth   1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

हटाएं

: o (l)

TRIE के आवेदन:

]

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth   1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

वर्तनी चेकर्स

---

।

]

]
1. डीएनए अनुक्रम मिलान ।