{"id":20,"date":"2022-10-13T05:08:09","date_gmt":"2022-10-13T05:08:09","guid":{"rendered":"https:\/\/blogs.oregonstate.edu\/aphung\/?p=20"},"modified":"2022-10-13T05:08:09","modified_gmt":"2022-10-13T05:08:09","slug":"do-or-do-not-there-is-no-trie","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/aphung\/2022\/10\/13\/do-or-do-not-there-is-no-trie\/","title":{"rendered":"Do or Do Not, There is No Trie."},"content":{"rendered":"\n
\"\"
Photo by Christian Crocker<\/a> on Unsplash<\/a><\/figcaption><\/figure><\/div>\n\n\n\n

Decided I would use this time in writing a blog post to be productive and review data structures. Especially one that wasn’t covered in CS 261.<\/p>\n\n\n\n

What is a Trie? This is also called a prefix tree, and this is a tree data structure that is used for retrieval of a key in a dataset of strings. This data structure can be used in various applications such as:<\/p>\n\n\n\n

  1. Autocomplete<\/li>
  2. Spell Checker<\/li>
  3. IP Routing (Longest prefix matching)<\/li>
  4. T9 Predictive Text<\/li>
  5. Solving Word Games<\/li><\/ol>\n\n\n\n

    But why a trie over another data structure like a hash table? A hash table has O(1) time complexity looking for a key, but it’s not efficient in 1) finding keys with a common prefix, and 2) enumerating a dataset of strings in lexicographical order. There can also be hash collisions with a hash table. A trie can have O(m) time complexity, where m is the key length, and searching for a key in a balanced tree costs O(mlogn) time complexity.<\/p>\n\n\n\n

    A trie is a rooted tree, and its nodes generally have two fields: 1) Links to its children and 2) Boolean field that specifies whether the node corresponds to the end of the key or is just a prefix.<\/p>\n\n\n\n

    The following is an implementation of a Trie in Python, with the following conditions (source: https:\/\/leetcode.com\/problems\/implement-trie-prefix-tree\/description\/).<\/p>\n\n\n\n

    • Trie()<\/code>\u00a0Initializes the trie object.<\/li>
    • void insert(String word)<\/code>\u00a0Inserts the string\u00a0word<\/code>\u00a0into the trie.<\/li>
    • boolean search(String word)<\/code>\u00a0Returns\u00a0true<\/code>\u00a0if the string\u00a0word<\/code>\u00a0is in the trie (i.e., was inserted before), and\u00a0false<\/code>\u00a0otherwise.<\/li>
    • boolean startsWith(String prefix)<\/code>\u00a0Returns\u00a0true<\/code>\u00a0if there is a previously inserted string\u00a0word<\/code>\u00a0that has the prefix\u00a0prefix<\/code>, and\u00a0false<\/code>\u00a0otherwise.<\/li><\/ul>\n\n\n\n
      class Trie:\r\n    def __init__(self):\r\n        \"\"\"Initialize a TrieNode.\"\"\"\r\n        self.root = TrieNode()\r\n        \r\n\r\n    def insert(self, word: str) -> None:\r\n        \"\"\"Inserts a word into the trie.\"\"\"\r\n        cur_node = self.root\r\n        for char in word:\r\n            if char not in cur_node.children:\r\n                cur_node.children[char] = TrieNode()\r\n            cur_node = cur_node.children[char]\r\n        \r\n        cur_node.is_end = True\r\n        \r\n\r\n    def search(self, word: str) -> bool:\r\n        \"\"\"Returns True if word is in the trie, else False.\"\"\"\r\n        cur_node = self.root\r\n        for char in word:\r\n            if char not in cur_node.children:\r\n                return False\r\n            cur_node = cur_node.children[char]\r\n        \r\n        return cur_node.is_end\r\n        \r\n\r\n    def startsWith(self, prefix: str) -> bool:\r\n        \"\"\"Returns True if word exists in the trie that starts with the given prefix.\"\"\"\r\n        cur_node = self.root\r\n        for char in prefix:\r\n            if char not in cur_node.children:\r\n                return False\r\n            cur_node = cur_node.children[char]\r\n            \r\n        return True\r\n        \r\n    \r\nclass TrieNode:\r\n    def __init__(self):\r\n        self.children = {}\r\n        self.is_end = False\r\n    \r\n    \r\n# Your Trie object will be instantiated and called as such:\r\n# obj = Trie()\r\n# obj.insert(word)\r\n# param_2 = obj.search(word)\r\n# param_3 = obj.startsWith(prefix)<\/code><\/pre>\n\n\n\n
      In this case, the insertion of a key to the trie is O(m) time complexity, where m is the key length, and O(m) space complexity.<\/p>\n\n\n\n
      Searching for a key in the trie is O(m) time complexity, since in the worst case, we perform m operations. The space complexity is O(1).<\/p>\n\n\n\n
      Searching for a prefix in the trie is also O(m) time complexity and O(1) space complexity. This is one benefit of a trie over a hash map.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Decided I would use this time in writing a blog post to be productive and review data structures. Especially one that wasn’t covered in CS 261. What is a Trie? This is also called a prefix tree, and this is a tree data structure that is used for retrieval of a key in a dataset […]<\/p>\n","protected":false},"author":12752,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-20","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/posts\/20","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/users\/12752"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/comments?post=20"}],"version-history":[{"count":1,"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/posts\/20\/revisions"}],"predecessor-version":[{"id":21,"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/posts\/20\/revisions\/21"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/media?parent=20"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/categories?post=20"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/aphung\/wp-json\/wp\/v2\/tags?post=20"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}