|s||Focus search module bar|
|?||Open this information panel|
|j||Move selection down|
|k||Move selection up|
|enter||Open current selection|
|Name||herd.prefixmap / 0.0.5/|
|Compatible Ceylon release||
JVM: 1.2.x, 1.3.x (latest)
|Published||Jan 2, 2016|
Downloads (JVM): 113
Downloads (JS): 45
Source downloads: 158
Provides general-purpose maps with support to prefix queries.
This module defines the following interfaces:
A ternary search tree, also known as a lexicographic search tree, is a kind of prefix tree whose nodes contain key elements, rather than complete keys.
The figure below shows a ternary search tree whose keys are sequences of characteres. Each node contain one element (a character) of a key. The keys in this tree are the words "as", "at", "bat", "bats", "bog", "boy", "caste", "cats", "day", "dogs", "donut", and "door". Squares denote terminal nodes. A terminal node contains the last element of a key. It also contains the item (not shown) associated with the key.
![Ternary search tree image](https://raw.githubusercontent.com/reverbel/prefix-map/master/doc/resources/ternary-search-tree.png "Ternary search tree example")
For a very short, formal and precise definition of ternary search tree, see pages 674-676 of Sleator and Tarjan's paper "Self-Adjusting Binary Search Trees", available here, from which the image above was taken. The relevant part is in section 6, "Two Applications of Splaying", starting at the bottom of page 674 and going up to the first paragraph of page 676. (Sleator and Tarjan do not mention "ternary search trees", they use the term "lexicographic search tree".) For a longer discussion, see Bentley and Sedgewick's paper "Fast Algorithms for Sorting and Searching Strings", or their article "Ternary Search Trees" in Dr. Dobb's.
A ternary splay tree, also known as a lexicographic splay tree, is a self-adjusting form of ternary search tree. Ternary splay trees are an extension of Sleator and Tarjan's plain (binary) splay trees, and were first presented in the same (aforementioned) paper that developed and analyzed splay trees. Both varieties of splay trees use the same restructuring heuristic and have operations with similar amortized time bounds.
"Self-Adjusting Binary Search Trees" "Fast Algorithms for Sorting and Searching Strings" "Ternary Search Trees"
import herd.prefixmap "0.0.5";
Download source archive
Download module documentation
View API documentation