ternary-tree

一个没有不安全块且具有简化Wasm绑定的Ternary Search Trees的Rust实现。

Ternary Search Tree (TST) 是一种数据结构，它以树的形式存储键/值对。键是一个字符串，其字符放置在树节点中。每个节点可能有三个子节点（因此得名）：一个 左 子节点，一个 中 子节点和一个 右 子节点。

在TST中进行搜索时，会将键中的当前字符与当前节点的字符进行比较

• 如果两者匹配，搜索将遍历中间子节点，并继续到键中的下一个字符
• 如果键字符小于节点字符，搜索将简单地通过左子节点进行，并继续寻找相同的键字符
• 相应地，如果键字符大于节点字符，搜索将简单地通过右子节点进行

该数据结构和其算法在 Dr.Dobb's Ternary Search Trees 文章中有很好的解释。

以下树是在以下键按顺序插入后得到的TST： "aba"，"ab"，"bc"，"ac"，"abc"，"a"，"b"，"aca"，"caa"，"cbc"，"bac"，"c"，"cca"，"aab"，"abb"，"aa"（见下面代码生成的 tst.dot）

带有对勾的框 "☑" 表示存储值的节点（它对应于键的最后一个字符）。空框 "☐" 表示节点没有值。

TST可以用作映射，但它允许以更灵活的方式检索与键关联的值。这个crate提供了四种遍历TST值的办法

• 获取所有值（与常规映射相同），使用 visit_values 或 iter
• 获取所有键以某些前缀开始的值（即 完成 某个前缀），使用 visit_complete_values 或 iter_complete
• 获取所有与某些字符串 接近 的值（汉明距离），使用 visit_neighbor_values 或 iter_neighbor
• 使用 visit_crossword_values 或 iter_crossword 获取所有键匹配包含通配符的字符串（例如 "a?c"）的值。

访问方法递归并应用于找到的值。它们有不可变和可变版本（即 visit_neighbor_values_mut）。但一旦找到值（基于其键），它们就无法知道实际的键是什么。

另一方面，迭代器将其上下文保存在一个 Vec 中，并且只对不可变树进行操作。然而，它们是双端队列，支持 next 和 next_back 方法从两端遍历树。此外，一旦找到值，它们提供 current_key 和 current_key_back 方法来检索关联的键。

以下行可能为您提供了这个crate和TSTs的预览。

extern crate ternary_tree;

use ternary_tree::Tst;
use std::fs::File;
use std::error::Error;

const SOME_KEYS : [&str; 16] = ["aba", "ab", "bc", "ac",
"abc", "a", "b", "aca", "caa", "cbc", "bac", "c", "cca",
"aab", "abb", "aa"];

let mut map = Tst::new();

for key in &SOME_KEYS {

    // Say the value is the same as the key,
    // it makes the example easier !
    let some_value = *key;

    map.insert(key, some_value);
}

// Use Graphviz to convert tst.dot to tst.png:
// dot -T png -o tst.png tst.dot
let mut file = File::create("tst.dot").unwrap();
map.pretty_print(&mut file);

let mut v = Vec::new();

// Recursively get all values whose keys match "a?a" pattern
map.visit_crossword_values("a?a", '?', |s| v.push(s.clone()));
assert_eq!(v, ["aba", "aca"]);

v.clear();

// Iterate over all values whose keys are close to "abc"
// (At a Hamming distance of 1 from "abc")
{
    let mut it = map.iter_neighbor("abc", 1);

    while let Some(value) = it.next() {

        v.push(*value);
    }
    assert_eq!(v, ["ab", "aba", "abb", "abc", "cbc"]);

    v.clear();
}

// Mutate all values whose keys begin with "c"
map.visit_complete_values_mut("c", |s| *s = "xxx");

assert_eq!(map.get("caa"), Some(&"xxx"));
assert_eq!(map.get("cbc"), Some(&"xxx"));
assert_eq!(map.get("cca"), Some(&"xxx"));

许可证：BSD-3-Clause