"إذا أراد العامل أن يؤدي عمله بشكل جيد، فعليه أولاً أن يشحذ أدواته." - كونفوشيوس، "مختارات كونفوشيوس. لو لينجونج"
الصفحة الأمامية > برمجة > مقدمة إلى Trie (شجرة بادئة)

مقدمة إلى Trie (شجرة بادئة)

نشر في 2025-02-07
تصفح:154

Introduction to Trie (Prefix Tree)

الخصائص الرئيسية ل trie:


العقد
    : تمثل كل عقدة حرفًا.
  1. الجذر
  2. : عقدة الجذر فارغة وتعمل كنقطة انطلاق.
  3. الأطفال
  4. : كل عقدة لديها ما يصل إلى 26 طفلًا (للحصول على أحرف اللغة الإنجليزية الصغيرة) أو أكثر ، اعتمادًا على مجموعة الأحرف.
  5. علامة نهاية كلمة
  6. : يتم تمييز بعض العقد للإشارة إلى نهاية كلمة.
  7. عمليات تري الأساسية:

1.

insertion

إدراج كلمة يتضمن اجتياز Trie وإنشاء عقد جديدة للشخصيات غير الموجودة.

2.

Search

يتحقق البحث عما إذا كانت كلمة واحدة موجودة في تري عن طريق اجتياز العقد.

3.

Search Search

هذا يتحقق مما إذا كانت أي كلمة في trie تبدأ ببادئة معينة.

تنفيذ Trie الأساسي في JavaScript:


class trienode { مُنشئ () { this.children = {} ؛ // يخزن العقد الفرعية this.isendofword = false ؛ // يمثل نهاية كلمة } } فئة تري { مُنشئ () { this.root = new trienode () ؛ } // أدخل كلمة إدراج (كلمة) { دع العقدة = this.root ؛ ل (دع char of word) { if (! node.children [char]) { node.children [char] = new trienode () ؛ } العقدة = node.children [char] ؛ } node.isendofword = true ؛ // وضع علامة على نهاية الكلمة } // ابحث عن كلمة البحث (كلمة) { دع العقدة = this.root ؛ ل (دع char of word) { if (! node.children [char]) { العودة كاذبة } العقدة = node.children [char] ؛ } إرجاع node.isendofword ؛ } // تحقق مما إذا كانت أي كلمة تبدأ بالبادئة المحددة Startswith (بادئة) { دع العقدة = this.root ؛ ل (دع char من البادئة) { if (! node.children [char]) { العودة كاذبة } العقدة = node.children [char] ؛ } العودة صحيح. } } // مثال الاستخدام const trie = new trie () ؛ trie.insert ("Apple") ؛ console.log (trie.search ("Apple")) ؛ // حقيقي console.log (trie.search ("app")) ؛ // خطأ شنيع console.log (trie.startswith ("app")) ؛ // حقيقي trie.insert ("التطبيق") ؛ console.log (trie.search ("app")) ؛ // حقيقي

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

1.

حذف كلمة

:

حذف كلمة يتضمن نهجًا متكررًا ، حيث نزيل العقد التي لم تعد مطلوبة.

delete (word ، node = this.root ، depth = 0) { if (depth === word.length) { if (! node.isendofword) return false ؛ // الكلمة غير موجودة node.isendofword = false ؛ return Object.Keys (node.children) .Length === 0 ؛ // تحقق مما إذا كانت العقدة لديها أطفال } const char = كلمة [العمق] ؛ if (! node.children [char]) العودة false ؛ const يجب أن deledeletechild = this.delete (كلمة ، node.children [char] ، العمق 1) ؛ إذا (يجب أن (يجب أن يكون deletechild) { حذف node.children [char] ؛ إرجاع Object.Keys (node.children) .Length === 0 &&! node.isendofword ؛ } العودة كاذبة }

2.
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;
}
:

عد عدد الكلمات التي تبدأ ببادئة معينة.

countwordswithprefix (بادئة) { دع العقدة = this.root ؛ ل (دع char من البادئة) { if (! node.children [char]) return 0 ؛ العقدة = node.children [char] ؛ } إرجاع this._countwords (العقدة) ؛ } _countwords (العقدة) { دع العد = node.isendofword؟ 1: 0 ؛ لـ (دع char in node.children) { count = this._countwords (node.children [char]) ؛ } عدد العائد }

3.
countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count  = this._countWords(node.children[char]);
    }
    return count;
}
:

إعطاء بادئة ، أعد كل الكلمات التي تبدأ بها.

getWordswithPrefix (بادئة) { دع العقدة = this.root ؛ ل (دع char من البادئة) { if (! node.children [char]) return [] ؛ العقدة = node.children [char] ؛ } إرجاع this._collectwords (العقدة ، بادئة) ؛ } _collectwords (العقدة ، بادئة) { دع النتائج = [] ؛ if (node.isendofword) results.push (بادئة) ؛ لـ (دع char in node.children) { النتائج = النتائج. } نتائج العودة }

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix   char));
    }

    return results;
}

insert
    : o (l) (l = طول الكلمة)
  1. Search
  2. : o (l)
  3. بادئة البحث
  4. : o (l)
  5. حذف
  6. : o (l)
  7. تطبيقات تري:

أنظمة الإكمال التلقائي
    (على سبيل المثال ، أشرطة البحث ، محرري النص).
  1. تعويذة المدقق
  2. .
  3. توجيه IP
  4. (أطول بادئة مطابقة).
  5. ألعاب الكلمات
  6. (على سبيل المثال ، boggle).
  7. تسلسل الحمض النووي مطابقة
  8. .
بيان الافراج يتم استنساخ هذه المقالة على: https://dev.to/keshav___dev/introduction-to-trie-prefix-tree-5g07؟1 إذا كان هناك أي انتهاك ، فيرجى الاتصال بـ [email protected] لحذفه.
أحدث البرنامج التعليمي أكثر>

تنصل: جميع الموارد المقدمة هي جزئيًا من الإنترنت. إذا كان هناك أي انتهاك لحقوق الطبع والنشر الخاصة بك أو الحقوق والمصالح الأخرى، فيرجى توضيح الأسباب التفصيلية وتقديم دليل على حقوق الطبع والنشر أو الحقوق والمصالح ثم إرسالها إلى البريد الإلكتروني: [email protected]. سوف نتعامل مع الأمر لك في أقرب وقت ممكن.

Copyright© 2022 湘ICP备2022001581号-3