Czym jest Trie (drzewo prefiksowe) i typowe zastosowanie?

Głębiej

Trie (drzewo prefiksowe) przechowuje klucze znak po znaku. Każdy węzeł reprezentuje prefiks, a znacznik końca słowa oznacza pełny wpis. Złożoność zależy od długości klucza L, a nie bezpośrednio od liczby słów (pomijając narzut pamięci/cache).

Typowe operacje:

• insert(word): O(L)
• search(word): O(L)
• startsWith(prefix): O(L)

Zastosowania

• Autouzupełnianie / wyszukiwanie po prefiksie.
• Słowniki + sprawdzanie pisowni.
• Prefiksy routingu/IP (często jako trie skompresowane).

Przykłady

type Node = { end: boolean; next: Map<string, Node> }
const root: Node = { end: false, next: new Map() }

function insert(word: string) {
  let node = root
  for (const ch of word) {
    const child = node.next.get(ch) ?? { end: false, next: new Map() }
    node.next.set(ch, child)
    node = child
  }
  node.end = true
}

function startsWith(prefix: string): boolean {
  let node = root
  for (const ch of prefix) {
    const child = node.next.get(ch)
    if (!child) return false
    node = child
  }
  return true
}

Trade-offy

• Trie potrafi być pamięciożerne (dużo węzłów). Warianty typu radix tree/compact trie zmniejszają narzut.
• Rozmiar alfabetu ma znaczenie: tablice są szybkie dla małego alfabetu, a mapy oszczędzają pamięć przy rzadkich węzłach.

Typowe pułapki