Skip to main content

Trie

  • prefix tree
  • data is stored in the edges
  • used to implement Priority Queue
  • Depending on the use case the children of the node can be set, dict, etc.

Node​

class Node:
    child: [None] * 26
    isEnd = False

Insert​

def insert(root, word):
    node = root
    for c in word:
        i = ord(c) - ord('a')
        if not node.child[i]:
            node.child[i] = new Node()
        node = node.child[i]
    node.isEnd = True

def search(root, word):
    node = root
    for c in word:
        i = ord(c) - ord('a')
        if not node.child[i]:
            return False
        node = node.child[i]
    return node.isEnd

Delete​

def isEmpty(root):
    for x in root.child:
        if x:
            return False
    return True

def delete(root, word, i):
    if root == None:
        return None
    if i == len(word):
        if root.isEnd:
            root.isEnd = False
        if isEmpty(root):
            root = None
        return root
    idx = ord(word[i]) - ord('a')
    root.child[idx] = delete(root.child[idx], word, i + 1)
    if isEmpty(root) and root.isEnd == False:
        root = None
    return root