C++ Program to Implement Trie (Prefix Tree) Data Structure

Trie (Prefix Tree) เป็นโครงสร้างข้อมูลแบบ Tree ใช้สำหรับจัดเก็บและค้นหาสตริงอย่างมีประสิทธิภาพ เหมาะสำหรับ Autocomplete, Spell Checker, IP Routing, Dictionary

โครงสร้าง Node

• Array of Children Pointers (ขนาด = Alphabet Size, เช่น 26 สำหรับ A-Z)
• Flag endOfString บอกว่า Node นี้จบคำหรือไม่

Operations หลัก

การ Implement แบบสมบูรณ์

#include <bits/stdc++.h>
using namespace std;

const int ALPHA_SIZE = 26; // A-Z

struct TrieNode {
    TrieNode* children[ALPHA_SIZE];
    bool isEndOfWord;
    
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHA_SIZE; i++)
            children[i] = nullptr;
    }
};

class Trie {
    TrieNode* root;
    
public:
    Trie() { root = new TrieNode(); }
    
    // Insert Word
    void insert(const string& key) {
        TrieNode* curr = root;
        for (char ch : key) {
            int index = ch - 'A'; // Assume Uppercase A-Z
            if (!curr->children[index])
                curr->children[index] = new TrieNode();
            curr = curr->children[index];
        }
        curr->isEndOfWord = true;
    }
    
    // Search Exact Word
    bool search(const string& key) const {
        TrieNode* curr = root;
        for (char ch : key) {
            int index = ch - 'A';
            if (!curr->children[index]) return false;
            curr = curr->children[index];
        }
        return curr->isEndOfWord;
    }
    
    // Check if Node has Children
    bool isEmpty(TrieNode* node) const {
        for (int i = 0; i < ALPHA_SIZE; i++)
            if (node->children[i]) return false;
        return true;
    }
    
    // Delete Word (Recursive)
    TrieNode* deleteHelper(TrieNode* node, const string& key, int depth) {
        if (!node) return nullptr;
        
        if (depth == key.size()) {
            if (node->isEndOfWord)
                node->isEndOfWord = false;
            
            if (isEmpty(node)) {
                delete node;
                return nullptr;
            }
            return node;
        }
        
        int index = key[depth] - 'A';
        node->children[index] = deleteHelper(node->children[index], key, depth + 1);
        
        if (isEmpty(node) && !node->isEndOfWord) {
            delete node;
            return nullptr;
        }
        return node;
    }
    
    void deleteKey(const string& key) {
        root = deleteHelper(root, key, 0);
    }
};

int main() {
    Trie trie;
    string words[] = {"HELLOWORLD", "HI", "BYE", "THE", "THENA"};
    
    for (const auto& w : words) trie.insert(w);
    
    cout << (trie.search("HELLOWORLD") ? "Key is Found" : "Key is not Found") << '\n';
    cout << (trie.search("HE") ? "Key is Found" : "Key is not Found") << '\n';
    
    trie.deleteKey("THEN");
    cout << "Key is deleted\n";
    
    return 0;
}

ผลลัพธ์

Key is Found
Key is not Found
Key is deleted

การประยุกต์ใช้จริง

• Autocomplete: หาคำที่ขึ้นต้นด้วย Prefix (DFS จาก Node สุดท้ายของ Prefix)
• Spell Checker: ตรวจสอบคำผิด + Suggest คำใกล้เคียง
• IP Routing (Longest Prefix Match): ใช้ Binary Trie (0/1)
• Dictionary/Word Games: Boggle, Scrabble Solver

Space Optimization

• Compressed Trie (Radix Tree): รวม Node ที่มีลูกเดียว
• Ternary Search Trie: ใช้ BST แทน Array ลด Memory
• Double-Array Trie: ใช้ Array 2 อัน Compact มาก

Comparator Function ของ qsort() ใน C: เรียงลำดับข้อมูลโครงสร้าง

C++ Program: หาจำนวนวิธี Partition คำ ให้แต่ละส่วนเป็น Palindrome