Tries

 

Trie is tree-based data structure.

used to search several strings fast & efficiently


external node is shown as a square, num of external node = num of string

Trie's internal node: max 26 (due to the number of the alphabet).

Trie has num of external node = num of string.

Trie's height is equal to the length of the longest sting.

The number of nodes in Trie is O(n) where n is the number of nodes.




Compressed Tries

# of node in standard trie 22 -> # of node in compressed trie

# of node of compressed trie: O(s) where s is number of string in trie

since # of nodes decrease, space used to store strings are reducing from O(n)->O(s).


trie struct

#define ALPHABET_SIZE 26

node structure with

  • char one char; // current char in key
  • trie array called child with ALPHABET_SIZE
  • boolean finished flag(last character of the word)

trie diagrams

general


storing endpoints


compressed (saves on memory)

Tries General Notes

  • data structure for representing strings that support O(L) lookup and insertion (where L is the length of a string)
  • Each node in a trie:
    • Contains one part of a key (typically one character)
    • May have up to 26 children
    • May be tagged as a "finishing" node
    • But even "finishing" nodes may have children
    • May contain other data for application (e.g. word frequency)
      • A "finishing" node marks the end of one key
  • Trie struct structure:

#define ALPHABET_SIZE 26

typedef struct Node *Trie;

typedef struct Node {

char onechar; // current char in key

Trie child[ALPHABET_SIZE];

bool finish; // last char in key?

Item data; // no Item if !finish

} Node;

typedef char *Key; // just lower-case letters