Data Structures & Algorithms – Tries
A Trie, also known as a prefix tree, is a tree-like data structure that is used to store a collection of strings. Each node in a trie represents a character in a string, and the path from the root to a particular node represents a prefix of one of the strings in the collection. The main advantage of tries is the ability to efficiently search for a string in the collection by prefix, as well as the ability to efficiently insert and delete strings.
Here is an example of how to implement a Trie in Python using primitives:
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
current = self.root
for letter in word:
if letter not in current.children:
current.children[letter] = TrieNode()
current = current.children[letter]
current.is_word = True
def search(self, word):
current = self.root
for letter in word:
if letter not in current.children:
return False
current = current.children[letter]
return current.is_word
Here is an example of how to implement a Trie in Java using primitives:
class TrieNode {
boolean isWord;
TrieNode[] children;
TrieNode() {
isWord = false;
children = new TrieNode[26];
for (int i = 0; i < children.length; i++) {
children[i] = null;
}
}
}
class Trie {
TrieNode root;
Trie() {
root = new TrieNode();
}
void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();</code>
}
current = current.children[index];
}
current.isWord = true;
}
boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return current.isWord;
}
}
Here is an example of how to implement a Trie in Rust using primitives:
struct TrieNode {
children: [Option<Box<TrieNode>>; 26],
is_word: bool,
}
impl TrieNode {
fn new() -> Self {
Self {
children: [None; 26],
is_word: false,
}
}
}
struct Trie {
root: TrieNode,
}
impl Trie {
fn new() -> Self {
Self { root: TrieNode::new() }
}
fn insert(&mut self, word: &str) {
let mut current = &mut self.root;
for c in word.chars() {
let idx = (c as u8 - b'a') as usize;
if current.children[idx].is_none() {
current.children[idx] = Some(Box::new(TrieNode::new()));
}
current = current.children[idx].as_mut().unwrap();
}
current.is_word = true;
}
fn search(&self, word: &str) -> bool {
let mut current = &self.root;
for c in word.chars() {
let idx = (c as u8 - b'a') as usize;
match current.children[idx] {
Some(ref node) => current = node,
None => return false,
}
}
current.is_word
}
}
It is worth noting that in Rust, the standard library has a TrieMap<K, V> type in the std::collections::TrieMap module which provides a more efficient and robust implementation of the Trie data structure.
In conclusion, Tries are a powerful data structure that can be used to efficiently store and retrieve data based on prefixes, and can be implemented using primitives in Python, JavaScript, Java and Rust. However, it’s worth noting that the standard libraries of these languages may provide more efficient and robust implementations of the Trie data structure.