19 lines
558 B
Plaintext
19 lines
558 B
Plaintext
= Trie =
|
|
|
|
A trie (pronounced "tree"), aka digital tree or prefix tree, is a type of
|
|
search tree used for locating keys within a set. The keys are usually strings,
|
|
however any datatype can be used. To find a key, the tree is traveresed
|
|
using [[DFS]].
|
|
|
|
Nodes in a trie can have any number of children, and only leaves actually store
|
|
their values. Each child node stores another more specific permutation of the
|
|
current node's key, unless it is a leaf.
|
|
|
|
== Operations ==
|
|
|
|
M is the length of a key
|
|
|
|
| Insertion | O(M) |
|
|
| Deletion | O(M) |
|
|
| Search | O(M) |
|