# Tries

Source: https://wisconsin.twango.dev/sp25-cs400/topics/tries

# Tries

Tries are a type of tree data structure that is used to store a dynamic set of strings, where the keys are usually strings. They are particularly useful for tasks such as autocomplete and spell checking.

## Structure of a Trie

A trie consists of nodes, where each node represents a character in a string. The root node represents an empty string, and each path from the root to a node represents a prefix of the strings stored in the trie. Each node contains:

- A list of child nodes, each representing a character.
- A boolean flag indicating whether the node represents the end of a valid string.

## Insertion

Walk the key one character at a time, creating a missing child as needed. Mark only the node reached **after the entire key** as terminal. Intermediate prefixes are not automatically stored keys. Empty strings, if permitted, use the root's terminal flag.

## Deletion

To delete a string from a trie, follow these steps:

1. Start at the root node.
2. For each character in the string:
   - Check if the character exists in the current node's children.
   - If it does, move to that child node.
   - If it doesn't, the string is not present in the trie, and no deletion is needed.
   - If you reach the end of the string, set the boolean flag of the last character's node to false.
   - If the node has no children and is not marked as the end of another string, delete the node and backtrack to remove any empty nodes.

## Connections

- [[sp25-cs400/topics/index|Topic index]]

Obvious technical and formatting errors repaired.