עץ קידומות - מבנה הנתונים שמאחורי השלמה אוטומטית

Trie (נקרא גם Prefix Tree) הוא עץ שבו כל מסלול מהשורש לעלה מייצג מחרוזת. מחרוזות עם קידומת משותפת חולקות את אותו נתיב - וזה מה שהופך חיפוש קידומות לזריז במיוחד.

מבנה הצומת

class TrieNode {
  constructor() {
    this.children = {};  // אות -> TrieNode
    this.isEnd = false;  // סוף מילה תקינה?
  }
}

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

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return true; // קידומת קיימת
  }
}

סיבוכיות

יישומים בפועל ובראיונות

• Autocomplete - השלמה אוטומטית בחיפוש (Google, VS Code)
• Spell Checker - בדיקת איות וצביעה שגיאות
• IP Routing - ניתוב רשת לפי קידומות IP (longest prefix match)
• Word Search II (LeetCode) - מציאת מילים בלוח אותיות
• Replace Words - החלפת מילים בקידומת הקצרה ביותר

אופטימיזציה - Compressed Trie

Trie רגיל בוזבז זיכרון כשיש שרשרות ארוכות של צמתים עם בן יחיד. Compressed Trie (Radix Tree) מאחד שרשרות כאלה לקשת אחת עם תווית מחרוזת - חוסך זיכרון משמעותי.