ternary-tree-wasm

A WebAssembly binding to Rust ternary-tree crate.

A Ternary Search Tree (TST) is a data structure which stores key/value pairs in a tree. The key is a string, and its characters are placed in the tree nodes. Each node may have three children (hence the name): a left child, a middle child and a right child.

A search in a TST compares the current character in the key with the character of the current node:

• If both matches, the search traverses the middle child, and proceed to the next character in the key
• If the key character is less than the node one, the search simply goes through the left child, and keep looking for the same key character
• Respectively, if the key character is greater than the node one, the search simply goes through the right child

The data structure and its algorithm are explained very well in Dr.Dobb's Ternary Search Trees article.

The following tree is the TST we get after inserting the following keys in order: "aba", "ab", "bc", "ac", "abc", "a", "b", "aca", "caa", "cbc", "bac", "c", "cca", "aab", "abb", "aa" (see tst.dot produced by code below)

A checked box "☑" denotes a node which stores a value (it corresponds to the last character of a key). An empty box "☐" means that the node has no value.

A TST can be used as a map, but it allows more flexible ways to retrieve values associated with keys. This package provides four basic ways to iterate over the values of a TST:

• Apply a closure to all values stored in the tree (same as a regular map) with tree.visit(closure, direction). See original iter doc 🦀
• Apply a closure to all values whose keys begin with some prefix (i.e. complete some prefix) with tree.complete(prefix, closure, direction). See original iter_complete doc 🦀
• Apply a closure to all values whose keys are close to some string (Hamming distance) with tree.neighbor(target, range, closure, direction). See original iter_neighbor doc 🦀
• Apply a closure to all values whose keys match a string with some joker (e.g. "a?c") with tree.crossword(pattern, joker, closure, direction). See original iter_crossword doc 🦀

See the doc for a quick API walkthrough with live examples.

License: BSD-3-Clause