Data structure: Trie

1 · Yingjun Mou · Aug. 18, 2021, 7 a.m.
notes about trie (aka. prefix tree) 1. Concept Motivation: reduce unnecessary comparisons between strings, making it faster than Hash Table By saying “faster than Hash Table”, simply looking for a key takes O(1) for both of them. But (1) finding all keys with common prefix, and (2) enumerating dataset in lexicographical order will be faster using Trie. Solution: create a tree-like structure, root is ‘0’ as the initial start index, each edge is a candidate of appended character. So each child no...