Scribd
Upload
60 views

Algorithms - String Processing - 01 - Trie

A trie is a tree data structure that is used to store strings. It allows for efficient string searches and insertions that take O(L) time where L is the length of the string. Nodes in the trie represent letters of the string, with branches connecting parent nodes to child nodes. Common prefixes are stored only once, saving space. The trie can be used to quickly determine if a string exists, count frequencies of strings and prefixes, and perform other operations related to strings in linear time with respect to the string length.

Uploaded by

murad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
60 views

Algorithms - String Processing - 01 - Trie

A trie is a tree data structure that is used to store strings. It allows for efficient string searches and insertions that take O(L) time where L is the length of the string. Nodes in the trie represent letters of the string, with branches connecting parent nodes to child nodes. Common prefixes are stored only once, saving space. The trie can be used to quickly determine if a string exists, count frequencies of strings and prefixes, and perform other operations related to strings in linear time with respect to the string length.

Uploaded by

murad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 11

Trie (Letter Tree)

Mostafa Saad

Trie
A simple but powerful data structure.
It adds/searches for string in O(L)
It is a tree with branches as letters

Initially, root exist

Add abcd
a

Add xyz
a

Add abf

Add xn

Add ab

Add bcd
b

So
Simple tree
Common prefixes are created once
Easy to know the nodes (red ones)
Could answer Questions such as:
Does word exist? Frequency?
Does prefix exist? Frequency?
Any question is answered by a trace from root to

maximum a leaf
So O(L) where L is word length
Could also print all strings on O(S), where S # of
words

Implementation
Node is similar to binary search tree, but we

have many children


Caring with memory?
Either have linked list for the set of nodes
Or more efficient. Use maps
Memory not issue

Has an array of nodes, its size the # of characters

Node could contain whatever needed


E.g. boolean to know full words
E.g. integer for frequency

You might also like