Trie

Træ-baseret

En træstruktur optimeret til strengsøgning hvor hver 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 præfikstræ eller digitalt træ) er en specialiseret træstruktur designet til effektiv lagring og søgning af strenge. Hver node i en trie repræsenterer et enkelt tegn, og stier fra roden til bladene former komplette ord. Tries udmærker sig ved præfiksbaserede operationer - at finde alle ord der starter med "kat" er meget hurtigt. Hver node indeholder typisk et array eller map af børn (et for hvert muligt tegn) og en boolean der indikerer om noden markerer slutningen af et gyldigt ord. Tries bruges intensivt i autofuldførelsessystemer, stavekontrol og forslagssystemer, IP-routing, ordbøger og ordspil samt DNA-sekvenssammenligning. 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;
  }

  // Tjek om præfiks 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 præfiks
  findWordsWithPrefix(prefix) {
    let node = this.root;
    const results = [];
    
    // Find præfiks-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

•Autofuldførelse i søgefelter
•Stavekontrol og forslagssystemer
•IP-routingtabeller i netværk
•Ordbøger og ordspil
•DNA-sekvenssammenligning

Fordele

✓Meget hurtig præfikssøgning
✓Tidsgaranti uafhængig af datasætstørrelse
✓Perfekt til autofuldførelse
✓Ingen hash-kollisioner
✓Alfabetisk ordning indbygget

Ulemper

✗Højt hukommelsesforbrug
✗Hver node kan have mange børnepointere
✗Overkill for små datasæt
✗Ikke pladseffektiv for spredte data
✗Mere kompleks end hash-tabeller

Eksempler fra den virkelige verden

•Google-søgning autoforslag
•IDE-kodefuldførelse (IntelliSense)
•Mobiltastatur ordforudsigelser
•Scrabble-ordvalidering
•DNS-opslagssystemer

Relaterede strukturer

Radix TreeSuffix TreeTernary Search TreeDAWG