loading...

Tries

jjb profile image JB Updated on ใƒป2 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources

  1. Trie Overview
  2. Trie Overview + Implementation
  3. Trie Operations + Implementations
  4. In Depth Trie Explanation
  5. A good implementation of the delete operation

(Also worth mentioning is this article from the Visual Studio Magazine. The article explains tries and why you might want to use them.)

Takeaways:

  • A trie is an ordered tree that compactly stores strings. Each node in a trie represents a single character in a string. Say we store the words "car" and "cars" in a trie - the trie would only use four nodes for both - one for each distinct letter of the words (c,a,r,s).
  • They are also known as digital trees and prefix trees.
  • A trie is most efficient when it is storing strings with similar prefixes, but in general tries are usually not space efficient. They have a space complexity of O(n + k).
  • They are useful for queries involving string prefixes, such as suggesting the next character(s) for a given prefix.
  • Tries are not usually found in standard libraries of popular languages (Java & C#, for example, do not have a trie data structure).
  • Tries are typically implemented using arrays or hash tables.
  • Although hash table implementations are more flexible, array implementations can be more efficient by placing limitations on the trie (like only allowing characters a-z)
  • Many trie implementations will use booleans to mark the end of words/strings. But some implementations will use an additional node appended after the last character of the word. This additional node might contain a NULL value or a special character.
  • Similarly, the root/head node of a trie can be represented in various ways. For my implementations I used a special character ($) to denote the root node.
  • Inserting and searching are both O(k) operations.
  • A related data structure is a radix tree
  • Radix trees are basically a space efficient trie. A trie only stores one character per node, whereas a radix tree can store many. A radix tree is essentially a trie where all nodes that are the only child are merged with their parent nodes - this means less total nodes are required for the same number of words.

Below you will find two trie implementations:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Dec 16 '19 by:

Discussion

markdown guide