Radix Tree
A trie where chains of single-child nodes are merged into one edge labelled with a string.
Radix Tree, Suffix Tree, Aho-Corasick: Radix tree: chains become labelled edges
From the root, the edge "c" leads into a chain of 1 node that each have one child and end no word. Nobody can branch off inside it, so the whole chain becomes a single edge labelled "ca". 1 node gone.
Cost
- Insert
- O(L)
- Search
- O(L)
- Space
- O(number of words)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Radix Tree, Suffix Tree, Aho-Corasick covers these too, in the same run.