Data structures & algorithmsLesson 3 of 3 in the course Trees and hashing

Trie Structure, Operations, Compression, and Applications

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

A trie is a tree-shaped data structure for storing and retrieving strings. Its structure organizes keys by their characters, so strings that share prefixes can share paths through the tree. This lesson introduces how tries represent keys and why that organization is useful.

A trie, also called a digital tree or prefix tree, stores strings by arranging characters along paths. The root represents the empty string. Each link from a node represents a character, and following links from the root spells a prefix of a stored key.

All flashcards

How does a trie represent a string key?
As a path of character links from the root; each node's position represents a prefix.
Why is a terminal marker useful in a trie?
It distinguishes a stored key from a path that is only a prefix of a longer key.
What is the usual time complexity of searching a trie for a key of length mm?
O(m)O(m), because the search follows at most one link per character.
What does a radix tree do to a trie?
It merges nodes with only one child, compressing unbranching paths.
What does a Patricia tree use to represent branching decisions?
A skip number identifying the bit index where a branching decision occurs.

Quiz questions

  1. When deleting a key from a trie, when may a node on its path be pruned?Answer: When it has no stored value and no children.
  2. Which structure compresses a trie by merging nodes that have only one child?Answer: A radix tree.
  3. How does a Patricia tree reduce unnecessary branching in a binary trie?Answer: It stores the bit index where each branching decision occurs.
  4. What can a bitmap record in a trie node?Answer: Which character links are present.
  5. Which trie application finds the most specific stored address prefix matching a network address?Answer: Internet routing with longest-prefix lookup.

Based on the Wikipedia article Trie, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Data structures & algorithms

All Data structures & algorithms lessons
Data structures & algorithmsBinary Heaps: Ordering, Array Operations, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsBinary Search Trees: Ordering, Operations, Height, and Uses5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsMerge Sort: Algorithms, Complexity, Variants, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →