5.1. Concept

This section gives an overview of tries.

Overview

A trie is a tree where each node has:

• 0-to-many children,

• A key whose type is character,

• A value that can be any type of object, and

• An end-state that indicates if the node and its ancestors together represent the end of a certain word.

Let us consider the following list of strings:

["she", "shell", "see", "shore", "selling", "sell"]

Given the strings as keys, a binary search tree can be constructed as follows using a balancing algorithm:

How many character comparisons does it need to make to search a string in a balanced BST?

With the same list of strings, a trie can be constructed as follows:

• 1st cell: key (a character).

• 2nd cell: value (the index of the string that the node represents).

• 3rd cell: end-state (T for true, F for false).

What is the worst-case complexity of searching a string in a trie?