Stack Overflow
Stack Overflow

Questions tagged [ternary-search-tree]

A ternary search tree is a data structure for efficiently storing string data using prefixes.

35 questions
14
votes
5 answers

Ternary Tree Vs Hash Table

I need to know if a ternary tree is better than a hash table. I came across this question in a reply to another question I had where someone said that ternary trees are often faster than hash tables. I found that hard to believe, so I decided to…
Unknown
  • 45,913
  • 27
  • 138
  • 182
13
votes
7 answers

How to search a string based key/value collection fast

Hello fellow stackoverflowers! I have a word list of 200.000 string entries, average string length is around 30 characters. This list of words are the key and to each key i have a domain object. I would like to find the domain objects in this…
Oskar
10
votes
4 answers

Balancing a ternary search tree

How does one go about 'balancing' a ternary search tree? Most tst implementations don't address balancing, but suggest inserting in an optimal order (which I can't control.)
uroc
  • 3,993
  • 3
  • 21
  • 18
6
votes
2 answers

Ternary Search Tree

struct Ternary { char current; bool wordend; Ternary* left; Ternary* mid; Ternary* right; Ternary(char c='@',Ternary* l=NULL, Ternary* m=NULL, Ternary* r=NULL,bool end=false) { wordend=end; current=c; …
CoderXX
  • 81
  • 1
  • 4
4
votes
0 answers

Radix Tries, Tries and Ternary Search Tries

I'm currently trying to get my head around the variations of Trie and was wondering if anyone would be able to clarify a couple of points. (I got quite confused with the answer to this question Tries versus ternary search trees for autocomplete?,…
user3023621
  • 103
  • 1
  • 9
3
votes
3 answers

Case Insensitive Ternary Search Tree

I had been using Ternary Search Tree for a while, as the data structure to implement a auto complete drop down combo box. Which means, when user type "fo", the drop down combo box will display foo food football The problem is, my current used of…
Cheok Yan Cheng
  • 47,586
  • 132
  • 466
  • 875
3
votes
0 answers

Given a list of letters, finding all possible words in a ternary search tree

I wrote a program to find all possible words with a list of given letters in a ternary search tree. The output is a sorted set of all words. Following is the python code for finding the words: def _find_words(self, node: Node, letters: str,…
Pacu
  • 163
  • 1
  • 2
  • 8
2
votes
1 answer

J2ME implementation of a Trie (Ternary Search Tree )

I am currently working on a predictive text SMS system. I want to implement it using TST data structure and bi-gram (Predicting the next probable word based on current key sequence 12-keypad). Currently I have a corpus and have used the available…
Tom
  • 63
  • 5
2
votes
2 answers

Is it possible to generate all possible terms findable in a ternary search tree?

From what I understand of ternary search trees, they are inverse deterministic in the items that can be sought and found (not sure about correct terms). What I mean, if you create a ternary tree for cat, bicycle, axis and you give someone the…
Abel
  • 56,041
  • 24
  • 146
  • 247
2
votes
1 answer

Python Ternary Search Algorithm

I'm trying to write a ternary search algorithm function that consumes a sorted list of integers and a value. It is similar to binary search, except that the search region is divided into three smaller regions (having lengths as equal as possible)…
Shagun Chhikara
  • 153
  • 1
  • 3
  • 11
2
votes
1 answer

Equals pointer in ternary search tree and limitations

HERE it is said that each node in a ternary search tree has three pointers. Left, right and equals. But in the example tree for {CAT, BUGS, CATS, UP}, How is that equals pointer of 'C' points to 'A' ? 'C' and 'A' are not equal right ? And if a node…
Andy897
  • 6,915
  • 11
  • 51
  • 86
2
votes
2 answers

Which is faster, a ternary search tree or a binary search tree?

ternery search tree requires O(log(n)+k) comparisons where n is number of strings and k is the length of the string to be searched and binary search tree requires log(n) comparisons then why is TST faster than BST ?
msd
  • 73
  • 1
  • 7
2
votes
1 answer

Ternary search trie insert function issues

So I'm trying to make a Ternary search trie. Right now, I'm only working on the insert function. I have understood the basic idea of a ternary search trie online. I know that one root node has 3 leaves, and if the character comes before the root, it…
Izy-
  • 1,041
  • 2
  • 16
  • 29
1
vote
1 answer

How do I print all the words out in a Trie?

I have a Ternary Search Tree (Trie) and I want to print out all of the words in it. How do I go about this using this current implementation that I have below? I have a standard put method to add new words to the tree. I was attempting to print the…
user9145291
1
vote
0 answers

Trie vs Radix tree vs Patricia trie

As I understand (also from here) memory-complexity of these DSs can be ordered like Trie > Radix > Patricia. But what about time-complexity? I assume they are almost same. If to mention my problem, I want to do a lot of prefix search queries from…
Eziz Durdyyev
  • 1,110
  • 2
  • 16
  • 34
1
2 3