Trie

Algorithms
tree
Catalogue
  1. 1. Introduction
  2. 2. Design a Dictionary
    1. 2.1. Time
    2. 2.2. Space
    3. 2.3. Use Case
  3. 3. 208. Implement Trie (Prefix Tree)
  4. 4. 211. Add and Search Word - Data structure design

Trie from the word Retrieve

  • A data structure, it is a tree and a search tree.

Introduction

Search Trees

  • Usually ordered data structure
  • search for some kind of “keys”

Example of Search Tree we are already very familiar: Binary Search Tree

  • the keys are associsated with each node in the tree
  • the keys can be any comparable type
  • main the order of the keys by topological property(leftsubtree < root < rightsubtree)

Design a Dictionary

n - # of words
m - length of the string/word

  1. What is the requirement of this dictionary?
  • search(word)
  • delete
  • add
  • find all words with give prefix
  1. Options of data structures
  • Hash Map
  • Balanced BST
  • ArrayList(sorted)

Time

  • Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string)
  • hashmap, remember we may need to calculate the hashCode() and compare eaquals, that is O(m).
  • Array List (sorted) - O(logn) * O(m)
  • Binary Search Tree - O(logn) * O(m)

DrawBack: if stored on disk, more random disk accesses (very expensive)

Space

  • if the tire is not too sparse, since reusing the common prefix as many as possible, less space required. worst case O(nm), but usually much better than this.

DrawBack:

  1. Every TrieNode has extra space comsumption -> extra space usage
  2. memory allocation fragmentation, especially when the trie is sparse.

Use Case

  • String or sequence typed elements
  • fast worst search/add/delete
  • grouping common prefix, both for time/space efficency
  • problems related to prefix/matching

208. Implement Trie (Prefix Tree)

  • Node <val, children>
    TODO: delete!!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Node(object):
    def __init__(self, val):
        self.val = val
        self.children = {}
        # self.parent = None ?
        # self.isWord = False ?

class Trie:

    def __init__(self):
        self.root = Node(-1)

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = Node(ch)
            cur = cur.children[ch]
        cur.children['#'] = True

    def search(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return '#' in cur.children

    def startsWith(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True

211. Add and Search Word - Data structure design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TrieNode(object):
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.isWord = False

class WordDictionary:

    def __init__(self):
        self.root = TrieNode(-1)

    def addWord(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode(ch)
            cur = cur.children[ch]
        cur.isWord = True

    def search(self, word):
        return self.exist(word, self.root)

    def exist(self, word, root):
        if len(word) == 0:
            return root.isWord

        cur = root
        ch = word[0]
        if ch == '.':
            for nxt in cur.children.keys():
                if self.exist(word[1:], cur.children[nxt]):
                    return True
            return False
        else:
            if ch not in cur.children:
                return False
            return self.exist(word[1:], cur.children[ch])
Share