Trie Data Structure | Prefix Tree | Search Engine Optimization

Introduction

A trie, also known as a prefix tree, is a tree-like data structure used to store and retrieve a set of strings. It is commonly used in search engines, spell checkers, and IP routers. In a trie, each node represents a character in a string, and the path from the root to a leaf node represents a complete string.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/graphs_trees("`Graphs Trees`") algorithm/BasicAlgorithmsGroup -.-> algorithm/recursion_dynamic("`Recursion Dynamic`") python/BasicConceptsGroup -.-> python/booleans("`Booleans`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ModulesandPackagesGroup -.-> python/importing_modules("`Importing Modules`") python/ModulesandPackagesGroup -.-> python/using_packages("`Using Packages`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") subgraph Lab Skills python/comments -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} algorithm/graphs_trees -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} algorithm/recursion_dynamic -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/booleans -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/conditional_statements -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/for_loops -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/while_loops -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/lists -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/tuples -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/function_definition -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/default_arguments -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/importing_modules -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/using_packages -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/standard_libraries -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/classes_objects -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/constructor -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/polymorphism -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/encapsulation -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} python/raising_exceptions -.-> lab-268839{{"`Trie Data Structure for String Storage`"}} end

Trie

Problem

Your task is to implement a trie with the following methods:

find(word) - returns True if the given word is in the trie, False otherwise.
insert(word) - inserts the given word into the trie.
remove(word) - removes the given word from the trie.
list_words() - returns a list of all words in the trie that end with a terminating character.

Requirements

To complete this challenge, the following requirements must be met:

The implementation should work with strings.
The strings are assumed to be in ASCII.
The find method should only match exact words with a terminating character.
The list_words method should only return words with a terminating character.
It is assumed that the implementation fits memory.

Example Usage

The following examples demonstrate the usage of the trie methods:

         root
       /  |  \
      h   a*  m
     / \   \   \
    a   e*  t*  e*
   / \         / \
  s*  t*      n*  t*
             /
            s*

find

* Find on an empty trie
* Find non-matching
* Find matching

insert

* Insert on empty trie
* Insert to make a leaf terminator char
* Insert to extend an existing terminator char

remove

* Remove me
* Remove mens
* Remove a
* Remove has

list_words

* List empty
* List general case

Trie Data Structure for String Storage