AlgoScope

Radix Tree

A trie where chains of single-child nodes are merged into one edge labelled with a string.

Data structures, data structure, advancedAlso called compressed trie, Patricia trie
Fold the chain into the edge ca.ca•cartet
Fold the chain into the edge ca.ca•cartet

Radix Tree, Suffix Tree, Aho-Corasick: Radix tree: chains become labelled edges

Decision, step 2 of 3

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.