Skip to content

Latest commit

 

History

History
62 lines (36 loc) · 4.94 KB

readme.md

File metadata and controls

62 lines (36 loc) · 4.94 KB
Raw

Tries

Theory

Tries

  • A trie, also called digital tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.

  • Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated; i.e., the value of the key is distributed across the structure.

  • All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.

  • Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest.

  • For the space-optimized presentation of prefix tree, see compact prefix tree.

  • In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A trie can be seen as a tree-shaped deterministic finite automaton. Each finite language is generated by a trie automaton, and each trie can be compressed into a deterministic acyclic finite state automaton.

  • In order to retrieve a value by key from a trie rooted by node root, we proceed through the trie, starting from the root, following the edges labeled by the letters in the key. If we come to a leaf node, and the key is entirely consumed, the value found in the node is the value associated with the key. If the key is consumed before reaching a leaf, the key is not in the trie. A node might not have an associated value (in which case we say the value stored at the node is null).

  • To insert a key key and a value value into a trie rooted by node root, we proceed through the trie, starting from the root, following the edges labeled by the letters in the key. If we come to a leaf node before the key is consumed, we create new edges, representing the remaining letters of the key, and store the value at the leaf node. If we consume the key before reaching a leaf, we mark the last node as a leaf and store the value at the node.

  • To delete a key key from a trie rooted by node root, we proceed through the trie, starting from the root, following the edges labeled by the letters in the key. If we come to a leaf node before the key is consumed, the key is not in the trie. If we consume the key before reaching a leaf, we mark the last node as not a leaf.

  • To find all keys beginning with a given prefix prefix in a trie rooted by node root, we proceed through the trie, starting from the root, following the edges labeled by the letters in the prefix. If we come to a leaf node before the prefix is consumed, there are no keys in the trie beginning with the given prefix. If we consume the prefix before reaching a leaf, we perform a depth-first search starting from the current node, and report all keys encountered.

  • To find all keys in a trie rooted by node root, we perform a depth-first search starting from the root, and report all keys encountered.

  • To find the longest prefix of a given string s that is a key in a trie rooted by node root, we proceed through the trie, starting from the root, following the edges labeled by the letters in s, stopping as soon as we find a node v such that v is not a leaf, or the letters in s are consumed. The longest prefix of s that is a key is the label of the path from the root to v.

  • To find the node corresponding to the longest prefix of a given string s that is a key in a trie rooted by node root, we proceed through the trie, starting from the root, following the edges labeled by the letters in s, stopping as soon as we find a node v such that v is not a leaf, or the letters in s are consumed. The node corresponding to the longest prefix of s that is a key is v.

Tries Applications

  • Dictionary
  • Spell checker
  • IP routing (Longest prefix matching)

Tries Implementation

  • Using a struct.

Tries Time Complexity

  • Access: O(n)
  • Search: O(n)
  • Insertion: O(1)
  • Deletion: O(1)

Tries Space Complexity

  • O(n)

Problems

Category: Tries Status: Done Author: David Bujosa