tsl

TSL Trie

Project: TSL — Ternary Search Trie / Ternary Search Tree Concept: A balanced tree–based trie structure optimized for dynamic updates.

Overview

TSL Trie refers to a family of ternary search tree (TST) implementations in C++, designed for dynamic insertion, deletion, and lookup of English string sets. Unlike static trie variants (e.g., MARISA or DARTS), TSL supports online updates with efficient memory usage and reasonable lookup performance.

A ternary search tree stores characters in nodes with three child pointers:

• left: characters less than the node
• mid: characters equal to the node
• right: characters greater than the node

This structure combines aspects of binary search trees and tries, enabling dynamic workloads and ordered traversal.

---

Key Features

• Dynamic updates: supports insertions and deletions at runtime.
• Prefix search: supports lookup of all keys with a given prefix.
• Balanced access: favorable performance for balanced datasets.
• Memory efficient: nodes allocated on demand.

---

Typical Use Cases

• English dynamic dictionaries with insert/delete workloads
• Search systems requiring runtime term additions
• Prefix search on evolving word sets
• Applications where static build is insufficient

---

Not Suitable For

• Extreme performance requirements in static read‑only environments
• Very large dictionaries where static double‑array structures are optimal
• Non‑English or Unicode‑heavy applications

---

Industrial Fit

Requirement	TSL Support
Online dynamic insert/delete	✔️
Prefix search	✔️
mmap‑able dictionary	❌
Static serialization	❌
Attaching payload (bitmap / counts)	❌

Conclusion: TSL Trie is suited for dynamic English key workloads where insertions and deletions occur during runtime, and prefix search is required.

---

C++ Example

Below is a simple ternary search tree implementation example for build, insert, and search. This is a standalone implementation (no external library).

Ternary Search Tree Node

struct TSTNode {
    char ch;
    bool isEnd;
    TSTNode *left, *mid, *right;
    TSTNode(char c): ch(c), isEnd(false), left(nullptr), mid(nullptr), right(nullptr) {}
};

Insert Function

TSTNode* insert(TSTNode* root, const char* word) {
    if (!root) {
        root = new TSTNode(*word);
    }

    if (*word < root->ch) {
        root->left = insert(root->left, word);
    } else if (*word > root->ch) {
        root->right = insert(root->right, word);
    } else {
        if (*(word + 1)) {
            root->mid = insert(root->mid, word + 1);
        } else {
            root->isEnd = true;
        }
    }
    return root;
}

Search Function

bool search(TSTNode* root, const char* word) {
    if (!root) return false;

    if (*word < root->ch) {
        return search(root->left, word);
    } else if (*word > root->ch) {
        return search(root->right, word);
    } else {
        if (*(word + 1) == '\0') {
            return root->isEnd;
        }
        return search(root->mid, word + 1);
    }
}

Example Usage

#include <iostream>

int main() {
    TSTNode* root = nullptr;
    root = insert(root, "apple");
    root = insert(root, "application");
    root = insert(root, "banana");
    root = insert(root, "band");

    std::cout << std::boolalpha;
    std::cout << "search(\"apple\"): " << search(root, "apple") << "\n";
    std::cout << "search(\"app\"): " << search(root, "app") << "\n";

    return 0;
}

---

This implementation is simple and direct, illustrating how TSL/TST works in C++ for dynamic workloads. You can expand it with traversal and prefix search as needed.