374 Advanced

374: Radix Tree (Compressed Trie)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "374: Radix Tree (Compressed Trie)" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Standard tries use one node per character — a word like "programming" requires 11 nodes. Key difference from OCaml: | Aspect | Rust radix tree | OCaml radix tree |

Tutorial

The Problem

Standard tries use one node per character — a word like "programming" requires 11 nodes. When many keys share long common prefixes (URLs, file paths, IP addresses), most trie nodes have exactly one child and waste memory. A radix tree (Patricia trie, compressed trie) collapses chains of single-child nodes into a single edge with a multi-character label. The word "programming" and "program" share a node labeled "program" with two children: one for "" (end) and one for "ming". This compression can reduce node count from O(total_chars) to O(words) for typical key sets. Radix trees power IP routing (longest prefix match), HTTP router matching, and autocomplete in shells.

🎯 Learning Outcomes

• Implement a RadixNode with children: HashMap<String, RadixNode> (multi-char edge labels)

• Insert by finding the longest common prefix with an existing edge label

• Split an edge when the new word shares only part of an existing label

• Search by matching prefixes of the remaining string against edge labels

• Find all words sharing a prefix by traversing the subtree below the prefix node

• Compare node count between a standard trie and a radix tree for the same word set

Code Example

#![allow(clippy::all)]
//! Radix Tree (Compressed Trie)
//!
//! Space-efficient prefix tree with edge compression.

use std::collections::HashMap;

/// Radix tree node with compressed edges
#[derive(Debug, Default)]
pub struct RadixNode {
    children: HashMap<String, RadixNode>,
    is_end: bool,
}

impl RadixNode {
    fn new() -> Self {
        Default::default()
    }
}

/// A radix tree (Patricia trie)
pub struct RadixTree {
    root: RadixNode,
}

impl RadixTree {
    pub fn new() -> Self {
        Self {
            root: RadixNode::new(),
        }
    }

    pub fn insert(&mut self, word: &str) {
        Self::insert_node(&mut self.root, word);
    }

    fn insert_node(node: &mut RadixNode, remaining: &str) {
        if remaining.is_empty() {
            node.is_end = true;
            return;
        }

        // Find matching edge
        let key = node
            .children
            .keys()
            .find(|k| remaining.starts_with(k.as_str()) || k.starts_with(remaining))
            .cloned();

        match key {
            Some(edge) if remaining.starts_with(&edge) => {
                let rest = &remaining[edge.len()..];
                let child = node.children.get_mut(&edge).unwrap();
                Self::insert_node(child, rest);
            }
            Some(edge) => {
                // Split edge
                let common_len = edge
                    .chars()
                    .zip(remaining.chars())
                    .take_while(|(a, b)| a == b)
                    .count();
                let common: String = edge.chars().take(common_len).collect();
                let edge_rest: String = edge.chars().skip(common_len).collect();
                let word_rest: String = remaining.chars().skip(common_len).collect();

                let old_child = node.children.remove(&edge).unwrap();
                let mut new_node = RadixNode::new();

                new_node.children.insert(edge_rest, old_child);

                if word_rest.is_empty() {
                    new_node.is_end = true;
                } else {
                    let mut word_node = RadixNode::new();
                    word_node.is_end = true;
                    new_node.children.insert(word_rest, word_node);
                }

                node.children.insert(common, new_node);
            }
            None => {
                let mut child = RadixNode::new();
                child.is_end = true;
                node.children.insert(remaining.to_string(), child);
            }
        }
    }

    pub fn search(&self, word: &str) -> bool {
        Self::search_node(&self.root, word)
    }

    fn search_node(node: &RadixNode, remaining: &str) -> bool {
        if remaining.is_empty() {
            return node.is_end;
        }
        for (edge, child) in &node.children {
            if remaining.starts_with(edge.as_str()) {
                return Self::search_node(child, &remaining[edge.len()..]);
            }
        }
        false
    }

    pub fn starts_with(&self, prefix: &str) -> bool {
        Self::prefix_node(&self.root, prefix)
    }

    fn prefix_node(node: &RadixNode, remaining: &str) -> bool {
        if remaining.is_empty() {
            return true;
        }
        for (edge, child) in &node.children {
            if edge.starts_with(remaining) || remaining.starts_with(edge.as_str()) {
                if edge.starts_with(remaining) {
                    return true;
                }
                return Self::prefix_node(child, &remaining[edge.len()..]);
            }
        }
        false
    }
}

impl Default for RadixTree {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_search() {
        let mut rt = RadixTree::new();
        rt.insert("test");
        rt.insert("testing");
        rt.insert("team");

        assert!(rt.search("test"));
        assert!(rt.search("testing"));
        assert!(rt.search("team"));
        assert!(!rt.search("tea"));
    }

    #[test]
    fn test_prefix() {
        let mut rt = RadixTree::new();
        rt.insert("rust");
        rt.insert("ruby");

        assert!(rt.starts_with("ru"));
        assert!(rt.starts_with("rus"));
        assert!(!rt.starts_with("py"));
    }

    #[test]
    fn test_compression() {
        let mut rt = RadixTree::new();
        rt.insert("romane");
        rt.insert("romanus");
        rt.insert("romulus");

        assert!(rt.search("romane"));
        assert!(rt.search("romanus"));
        assert!(rt.search("romulus"));
    }

    #[test]
    fn test_single_char() {
        let mut rt = RadixTree::new();
        rt.insert("a");
        rt.insert("ab");
        rt.insert("abc");

        assert!(rt.search("a"));
        assert!(rt.search("ab"));
        assert!(rt.search("abc"));
    }

    #[test]
    fn test_empty_search() {
        let rt = RadixTree::new();
        assert!(!rt.search("anything"));
    }
}

(* OCaml: radix tree / compressed trie *)

(* We show the compression concept *)
(* Standard trie for 'car','card','care' would have:
   root -> c -> a -> r -> (end) -> d -> (end)
                              \-> e -> (end)
   Radix compresses 'c','a' into edge 'ca' if no branching *)

type radix =
  | Leaf of string
  | Node of (string * radix) list * bool  (* edges * is_end *)

let empty = Node ([], false)

let rec insert node path =
  match node with
  | Leaf s -> if s = path then Leaf s else
    (* Find common prefix *)
    let rec cp a b i =
      if i >= String.length a || i >= String.length b || a.[i] <> b.[i] then i
      else cp a b (i+1)
    in
    let i = cp s path 0 in
    let pre = String.sub s 0 i in
    Node ([String.sub s i (String.length s - i), Leaf s;
           String.sub path i (String.length path - i), Leaf path], false)
  | _ -> node  (* simplified *)

let () =
  Printf.printf "Radix tree compresses 'car','card','care' into:\n";
  Printf.printf "  root --'car'--> Node(end) --'d'--> Leaf --'e'--> Leaf\n";
  Printf.printf "This uses 3 nodes instead of 7 in a standard trie\n"

Key Differences

Aspect	Rust radix tree	OCaml radix tree
Edge labels	`HashMap<String, RadixNode>`	`StringMap.t`
Mutability	In-place edge splitting (`&mut`)	Persistent (new tree)
Prefix matching	`str::starts_with` + `common_prefix_len`	`String.sub` comparison
Production	`radix` or `patricia-tree` crates	No standard library
IP routing	Bit-level radix tree (256-way branches)	Same concept

OCaml Approach

OCaml's standard trie approach uses String keys in a Map:

module StringMap = Map.Make(String)

type radix_node = {
  children: radix_node StringMap.t;
  is_end: bool;
}

(* Functional radix tree: returns new node per insert *)
let common_prefix a b =
  let n = min (String.length a) (String.length b) in
  let i = ref 0 in
  while !i < n && a.[!i] = b.[!i] do incr i done;
  String.sub a 0 !i

OCaml's persistent radix tree is structurally simpler to reason about — each insert returns a new node, sharing unchanged subtrees. The mutation-based Rust version is more cache-efficient but requires careful borrow management.

Full Source

#![allow(clippy::all)]
//! Radix Tree (Compressed Trie)
//!
//! Space-efficient prefix tree with edge compression.

use std::collections::HashMap;

/// Radix tree node with compressed edges
#[derive(Debug, Default)]
pub struct RadixNode {
    children: HashMap<String, RadixNode>,
    is_end: bool,
}

impl RadixNode {
    fn new() -> Self {
        Default::default()
    }
}

/// A radix tree (Patricia trie)
pub struct RadixTree {
    root: RadixNode,
}

impl RadixTree {
    pub fn new() -> Self {
        Self {
            root: RadixNode::new(),
        }
    }

    pub fn insert(&mut self, word: &str) {
        Self::insert_node(&mut self.root, word);
    }

    fn insert_node(node: &mut RadixNode, remaining: &str) {
        if remaining.is_empty() {
            node.is_end = true;
            return;
        }

        // Find matching edge
        let key = node
            .children
            .keys()
            .find(|k| remaining.starts_with(k.as_str()) || k.starts_with(remaining))
            .cloned();

        match key {
            Some(edge) if remaining.starts_with(&edge) => {
                let rest = &remaining[edge.len()..];
                let child = node.children.get_mut(&edge).unwrap();
                Self::insert_node(child, rest);
            }
            Some(edge) => {
                // Split edge
                let common_len = edge
                    .chars()
                    .zip(remaining.chars())
                    .take_while(|(a, b)| a == b)
                    .count();
                let common: String = edge.chars().take(common_len).collect();
                let edge_rest: String = edge.chars().skip(common_len).collect();
                let word_rest: String = remaining.chars().skip(common_len).collect();

                let old_child = node.children.remove(&edge).unwrap();
                let mut new_node = RadixNode::new();

                new_node.children.insert(edge_rest, old_child);

                if word_rest.is_empty() {
                    new_node.is_end = true;
                } else {
                    let mut word_node = RadixNode::new();
                    word_node.is_end = true;
                    new_node.children.insert(word_rest, word_node);
                }

                node.children.insert(common, new_node);
            }
            None => {
                let mut child = RadixNode::new();
                child.is_end = true;
                node.children.insert(remaining.to_string(), child);
            }
        }
    }

    pub fn search(&self, word: &str) -> bool {
        Self::search_node(&self.root, word)
    }

    fn search_node(node: &RadixNode, remaining: &str) -> bool {
        if remaining.is_empty() {
            return node.is_end;
        }
        for (edge, child) in &node.children {
            if remaining.starts_with(edge.as_str()) {
                return Self::search_node(child, &remaining[edge.len()..]);
            }
        }
        false
    }

    pub fn starts_with(&self, prefix: &str) -> bool {
        Self::prefix_node(&self.root, prefix)
    }

    fn prefix_node(node: &RadixNode, remaining: &str) -> bool {
        if remaining.is_empty() {
            return true;
        }
        for (edge, child) in &node.children {
            if edge.starts_with(remaining) || remaining.starts_with(edge.as_str()) {
                if edge.starts_with(remaining) {
                    return true;
                }
                return Self::prefix_node(child, &remaining[edge.len()..]);
            }
        }
        false
    }
}

impl Default for RadixTree {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_search() {
        let mut rt = RadixTree::new();
        rt.insert("test");
        rt.insert("testing");
        rt.insert("team");

        assert!(rt.search("test"));
        assert!(rt.search("testing"));
        assert!(rt.search("team"));
        assert!(!rt.search("tea"));
    }

    #[test]
    fn test_prefix() {
        let mut rt = RadixTree::new();
        rt.insert("rust");
        rt.insert("ruby");

        assert!(rt.starts_with("ru"));
        assert!(rt.starts_with("rus"));
        assert!(!rt.starts_with("py"));
    }

    #[test]
    fn test_compression() {
        let mut rt = RadixTree::new();
        rt.insert("romane");
        rt.insert("romanus");
        rt.insert("romulus");

        assert!(rt.search("romane"));
        assert!(rt.search("romanus"));
        assert!(rt.search("romulus"));
    }

    #[test]
    fn test_single_char() {
        let mut rt = RadixTree::new();
        rt.insert("a");
        rt.insert("ab");
        rt.insert("abc");

        assert!(rt.search("a"));
        assert!(rt.search("ab"));
        assert!(rt.search("abc"));
    }

    #[test]
    fn test_empty_search() {
        let rt = RadixTree::new();
        assert!(!rt.search("anything"));
    }
}

(* OCaml: radix tree / compressed trie *)

(* We show the compression concept *)
(* Standard trie for 'car','card','care' would have:
   root -> c -> a -> r -> (end) -> d -> (end)
                              \-> e -> (end)
   Radix compresses 'c','a' into edge 'ca' if no branching *)

type radix =
  | Leaf of string
  | Node of (string * radix) list * bool  (* edges * is_end *)

let empty = Node ([], false)

let rec insert node path =
  match node with
  | Leaf s -> if s = path then Leaf s else
    (* Find common prefix *)
    let rec cp a b i =
      if i >= String.length a || i >= String.length b || a.[i] <> b.[i] then i
      else cp a b (i+1)
    in
    let i = cp s path 0 in
    let pre = String.sub s 0 i in
    Node ([String.sub s i (String.length s - i), Leaf s;
           String.sub path i (String.length path - i), Leaf path], false)
  | _ -> node  (* simplified *)

let () =
  Printf.printf "Radix tree compresses 'car','card','care' into:\n";
  Printf.printf "  root --'car'--> Node(end) --'d'--> Leaf --'e'--> Leaf\n";
  Printf.printf "This uses 3 nodes instead of 7 in a standard trie\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_search() {
        let mut rt = RadixTree::new();
        rt.insert("test");
        rt.insert("testing");
        rt.insert("team");

        assert!(rt.search("test"));
        assert!(rt.search("testing"));
        assert!(rt.search("team"));
        assert!(!rt.search("tea"));
    }

    #[test]
    fn test_prefix() {
        let mut rt = RadixTree::new();
        rt.insert("rust");
        rt.insert("ruby");

        assert!(rt.starts_with("ru"));
        assert!(rt.starts_with("rus"));
        assert!(!rt.starts_with("py"));
    }

    #[test]
    fn test_compression() {
        let mut rt = RadixTree::new();
        rt.insert("romane");
        rt.insert("romanus");
        rt.insert("romulus");

        assert!(rt.search("romane"));
        assert!(rt.search("romanus"));
        assert!(rt.search("romulus"));
    }

    #[test]
    fn test_single_char() {
        let mut rt = RadixTree::new();
        rt.insert("a");
        rt.insert("ab");
        rt.insert("abc");

        assert!(rt.search("a"));
        assert!(rt.search("ab"));
        assert!(rt.search("abc"));
    }

    #[test]
    fn test_empty_search() {
        let rt = RadixTree::new();
        assert!(!rt.search("anything"));
    }
}

Deep Comparison

OCaml vs Rust: Radix Tree

Both compress common prefixes into edge labels.

Exercises

Node count comparison: Insert 100 English words into both a standard Trie (char-per-node) and a RadixTree; count total nodes in each and compute the compression ratio.

Longest prefix match: Implement longest_prefix_match(&self, query: &str) -> Option<String> that finds the longest stored prefix of query — the core operation in IP routing tables.

Delete: Implement remove(&mut self, word: &str) -> bool that marks is_end = false for the word's node; also merge single-child non-end nodes back into their parent edge (re-compress after deletion).

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust