# 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'.](/files/-M765W9i-sCJT_pLfRqD)

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:

![](/files/-M765xphqB6Z9np2B0W6)

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](/abstract-data-types/hashing.md) or [Sets](/abstract-data-types/collections/sets.md) etc.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b.bencuan.me/abstract-data-types/binary-trees/tries.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.