ما هو الـ Trie؟
الدرس 2 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
تُعد تري (trie) (تُنطق "try"، وهي اختصار لكلمة retrieval أي استرجاع) هيكل بيانات على شكل شجرة مصمم لتخزين والبحث عن السلاسل النصية من خلال أحرفها. يتم تمييز كل حافة في الشجرة بحرف واحد، وكل مسار من الجذر وصولاً إلى عقدة محددة يمثل كلمة واحدة مخزنة.
يجعل هذا الهيكل الأسئلة المتعلقة بالبادئات (prefixes) سريعة للغاية. فالتحقق مما إذا كانت الـ trie تحتوي على أي كلمة تبدأ بـ "car" يتطلب ثلاث عمليات بحث عن الأحرف فقط من الجذر، بغض النظر عن عدد آلاف الكلمات المخزنة. تُعد هياكل الـ trie المحرك وراء ميزات مثل الإكمال التلقائي، والتدقيق الإملائي، وجداول توجيه IP.
تحتوي كل عقدة (node) في الـ trie على قطعتين من الحالة:
children: خريطة من حرف إلى الـTrieNodeالتالي.isEndOfWord: علامة تكون قيمتهاtrueعندما يمثل المسار من الجذر إلى هذه العقدة كلمة كاملة تم إدراجها.
العمليات الخمس الرئيسية في الـ trie هي:
- Insert: إضافة كلمة، مع إنشاء أي عقد مفقودة على طول المسار.
- Search: التحقق مما إذا كانت هناك كلمة كاملة مخزنة.
- StartsWith: التحقق مما إذا كانت أي كلمة مخزنة تبدأ بالبادئة المعطاة.
- Delete: إزالة كلمة وتقليم أي فروع ميتة.
- WordCount: عد الكلمات الفريدة المخزنة.
لنقم ببناء فئة Trie!
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.