Trie

Træ-baseret

En træstruktur optimeret til string søgning hvor hvert node repræsenterer et bogstav i en sekvens.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(m)`
Search	`O(m)`
Insertion	`O(m)`
Deletion	`O(m)`

Beskrivelse

En Trie (også kaldet prefix tree eller digital tree) er en specialiseret træstruktur designet til effektiv lagring og søgning af strings. Hvert node i en trie repræsenterer et enkelt tegn, og stier fra root til leaves former komplette ord. Tries udmærker sig ved prefix-baserede operationer - at finde alle ord der starter med "cat" er meget hurtigt. Hver node indeholder typisk et array eller map af children (et for hvert muligt tegn) og en boolean der indikerer om noden markerer slutningen af et gyldigt ord. Tries bruges intensivt i auto-complete systemer, spell checkers, IP routing, og generelt hvor prefix matching er vigtigt. De bruger mere hukommelse end andre strukturer men giver O(m) søgning hvor m er længden af søgeordet, uafhængigt af antal lagrede ord.

Kode Eksempel

// JavaScript Trie implementation
class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

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

  // Indsæt ord
  insert(word) {
    let node = this.root;
    for (let char of word.toLowerCase()) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  // Søg efter ord
  search(word) {
    let node = this.root;
    for (let char of word.toLowerCase()) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  // Check om prefix findes
  startsWith(prefix) {
    let node = this.root;
    for (let char of prefix.toLowerCase()) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }

  // Find alle ord med givet prefix
  findWordsWithPrefix(prefix) {
    let node = this.root;
    const results = [];
    
    // Find prefix node
    for (let char of prefix.toLowerCase()) {
      if (!node.children[char]) return results;
      node = node.children[char];
    }
    
    // DFS for at finde alle ord
    this._dfs(node, prefix, results);
    return results;
  }

  _dfs(node, currentWord, results) {
    if (node.isEndOfWord) {
      results.push(currentWord);
    }
    for (let char in node.children) {
      this._dfs(node.children[char], currentWord + char, results);
    }
  }
}

Anvendelsesområder

•Auto-complete i søgefelter
•Spell checking og suggestion systems
•IP routing tables i netværk
•Ordbøger og word games
•DNA sequence matching

Fordele

✓Meget hurtig prefix søgning
✓Tidsgaranti uafhængig af dataset størrelse
✓Perfekt til auto-complete
✓Ingen hash collisions
✓Alfabetisk ordering indbygget

Ulemper

✗Høj hukommelsesforbrug
✗Hver node kan have mange children pointere
✗Overkill for små datasets
✗Ikke space-efficient for sparse data
✗Mere kompleks end hash tables

Eksempler fra den virkelige verden

•Google search auto-suggestions
•IDE kode completion (IntelliSense)
•Mobil tastatur word predictions
•Scrabble ord validering
•DNS lookup systems

Relaterede strukturer

Radix TreeSuffix TreeTernary Search TreeDAWG