Trie

08 Jul 2023 in Study / Computer science on Trie

Data Structure

• Data structure using tree
• It consists of chars from the specific string
• is used to find prefix (접두사) easily

Idea for Implementation

• Chars from a specific string are saved as nodes into trie one by one
• If same char with same order has already been saved, there is no need to make new node (efficient for finding prefix)
• Last char from a string is saved as a node which has the string data

Implementation

class Node:
  def __init__(self, key, data = None):
    self.key = key
    self.data = data
    self.child = {}

class Trie:
  def __init__(self):
    self.head = Node(None)

  def insert(self, string):
    current_node = self.head

    for char in string:
      if char not in current_node.child:
        current_node.child[char] = Node(char)

      current_node = current_node.child[char]

    current_node.data = string

• Code Analysis
  

class Node:
  def __init__(self, key, data = None):
    self.key = key
    self.data = data
    self.child = {}

key : a char which gonna be saved
data : If this node is for the last char from a string, the string gonna be saved into “data”

---

def insert(self, string):
  current_node = self.head

  for char in string:
    if char not in current_node.child:
      current_node.child[char] = Node(char)

    current_node = current_node.child[char]

  current_node.data = string

should constantly update current_node
If there is no char in current_node.child, make new node for the char
If loop finishes, current_node is for last char from a string

Reference

blog