Last Updated: 2023-08-31 13:38:42 Thursday
-- TOC --
A Trie, also known as a
prefix tree, is a type of search tree used for storing a collection of strings. It has a number of uses such as building autocomplete functionalities, and is especially efficient for prefix-based searches.
Trie这种数据结构于1960年由Edward Fredkin和著名的Donald Knuth（克努特）提出。
The original paper on the Trie data structure was titled "A File Maintenance System" and was written by
1960. The paper introduces the Trie data structure as a way to efficiently store and retrieve information from a large collection of records.
Trie supports three main operations: insert, search, and startswith.
insert: To insert a word into the Trie, start from the root and traverse down the path that corresponds to the word. If the path doesn't exist, create a new node. If the path already exists, move down to the next level. Repeat until you've processed each character in the word. At the end of the word, mark the final node as the end of a word. \(O(N)\)
search: To find a word (or a prefix), start from the root and traverse down the path corresponding to the word. If at any point the path doesn't exist, return false. If you finish traversing the word and end at a node that's marked as the end of a word, return true. Otherwise, return false. \(O(N)\)
startswith(retrieval): Retrieve all words with the same prefix.
The space complexity of a Trie can be high. In the worst-case scenario, if no paths are shared by any words, the space required is \(O(N\cdot M)\), where N is the number of words and M is the length of the longest word. This is because each word would require a new path from the root to the leaf. However, in the average case where there are some common prefixes, the space complexity will be less because paths are shared between words.
虽然现在内存便宜，多用点空间换取性能是常规操作，但是（在保持性能时）节省空间依然有一些潜在的好处：（1）增加CPU Cache命中率；（2）减少Page Swap。
-- EOF --
-- MORE --