# Tries

## Main Ideas

A **trie** is a specific implementation of a set and is short for **retrieval tree.** 

It only works on sets with a **finite alphabet**, like digits or ASCII characters, for example. The idea is that each node can act like an **array containing all characters in the alphabet** and we can just access the branches super fast by indexing into them!

Tries are fantastic for searching to see if a word is contained in a set. Here's an example:

![This trie contains the words 'batcat', 'batman', and 'banana'.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M764C6P-wwHNG6AmMQb%2F-M765W9i-sCJT_pLfRqD%2Fimage.png?alt=media\&token=0e726495-4fb6-43cd-957e-b2dcef2a3357)

This is great because it makes the `add()` and `contains()` functions run in $$\Theta(1)$$ time! Additionally, it makes special string operations like prefix matching or autocomplete very efficient.

We can improve this data structure a lot- for instance, we can condense the leaves to reduce the number of nodes like this:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M764C6P-wwHNG6AmMQb%2F-M765xphqB6Z9np2B0W6%2Fimage.png?alt=media\&token=718717c8-07bc-47ec-93ad-805d0c14d9b7)

I won't go into too much detail on how to optimize it further, or how to implement the actual functions efficiently, but hopefully you'll have a good sense of how to do it yourself after learning about concepts like [Hashing and Hash Tables](https://cs61b.bencuan.me/abstract-data-types/hashing) or [Sets](https://cs61b.bencuan.me/abstract-data-types/collections/sets) etc.