# Randomized Ternary Search Tries

arXiv: https://arxiv.org/abs/1606.04042 · HTML: https://mlsanity.com/paper/1606.04042/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2016.

## Built on by (most cited first, 1 of 1)

- [Overview and Comparison of AVS Point Cloud Compression Standard](https://mlsanity.com/paper/2602.08613/) (2026)

## Abstract (arXiv)

This paper presents a new kind of self-balancing ternary search trie that uses a randomized balancing strategy adapted from Aragon and Seidel's randomized binary search trees ("treaps"). After any sequence of insertions and deletions of strings, the tree looks like a ternary search trie built by inserting strings in random order. As a result, the time cost of searching, inserting, or deleting a string of length k in a tree with n strings is at most O(k + log n) with high probability.