Questions tagged [ternary-search-tree]

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

ternary-search-tree
Filter by
Sorted by
Tagged with
14 votes
5 answers
5k views

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. ...
Unknown's user avatar
  • 46.3k
13 votes
7 answers
6k views

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 ...
user avatar
10 votes
4 answers
4k views

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's user avatar
  • 4,053
6 votes
2 answers
5k views

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) ...
CoderXX's user avatar
  • 81
4 votes
0 answers
631 views

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 ...
user3023621's user avatar
3 votes
3 answers
5k views

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 ...
Cheok Yan Cheng's user avatar
3 votes
0 answers
401 views

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 ...
Pacu's user avatar
  • 163
2 votes
2 answers
1k views

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 ...
Abel's user avatar
  • 56.5k
2 votes
1 answer
402 views

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 ...
Izy-'s user avatar
  • 1,103
2 votes
1 answer
5k views

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 ...
Shagun Chhikara's user avatar
2 votes
1 answer
118 views

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' ?...
Andy897's user avatar
  • 7,013
2 votes
1 answer
384 views

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). ...
Tom's user avatar
  • 63
2 votes
2 answers
2k views

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 ...
msd's user avatar
  • 73
1 vote
2 answers
1k views

Ternary tree vs trie with map as transition table for Aho-Corasick FSA

What is the difference between FSA using ternary tree and a trie with transition tables implemented as search trees (e.g. std::map)? It seems like both have O(log k) complexity for reading one symbol ...
lizarisk's user avatar
  • 7,690
1 vote
1 answer
446 views

Finding longest common prefix in a ternary search tree

I implement a ternary search tree for a 20000 words.I want to know an algorithm to find a longest common prefix(prefix that is shared by at least 2 words)? Is there anyway to find a Longest Common ...
Proud's user avatar
  • 39
1 vote
1 answer
111 views

segmentation fault in insertion into ternary search tree

i am trying to insert the charachter in to ternary search tree, please help me out with this segmentation fault ?? here is what i am doing to inser in to trie,on running this i am getting segmentation ...
user1688392's user avatar
1 vote
1 answer
3k views

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 ...
user avatar
1 vote
2 answers
751 views

Spell Checker : Ternary Search tree

i have made a spell checker code using Ternary search tree. Can anybody tell me how to find the next possible word in TST. for example if i want to search if i search a word "Manly" in spell checker ...
Parul Setia's user avatar
1 vote
0 answers
2k views

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 ...
Eziz Durdyyev's user avatar
1 vote
1 answer
319 views

Time complexity for inserting all suffixes of a string into a ternary search tree?

I have a ternary search tree that contain all the suffixes of a word. What is the time complexity for construction and searching a word in this structure? Example: a word banana$, have the suffix ...
Yosvanys Aponte's user avatar
0 votes
1 answer
3k views

How to list in an alphabetical order the words of a ternary search tree?

How can I go about listing the words a TST contains in an alphabetical order? Unlike BSTs where an in-order traversal will do the trick, this won't work TST. Neither would pre-order nor post-order ...
mkab's user avatar
  • 953
0 votes
2 answers
160 views

Exploring a binary search tree

I figure a binary search tree is the simplest example, but really I would like to know how to explore a ternary search tree or some variety of tries. I don't have any experience with these, but I ...
tau's user avatar
  • 6,629
0 votes
2 answers
1k views

Spell Checker using Ternary Search tree

I made a spell checker using Ternary search tree (TST). Can anybody tell me how to find the next possible word in the TST? eg: If i want to search the word "Manly" in spell checker and if the word ...
Parul Setia's user avatar
0 votes
1 answer
3k views

Ternary search tree with all suggestions autocomplete in C#

I wonder is it possible to modify ternary search tree to check that word exists AND find all words that starts with that word ( or finish by that word ?) ? For example do => dog dogs etc. From this ...
deadfish's user avatar
  • 12.2k
0 votes
1 answer
546 views

Ternary Search Tree in C, Pointer to a Pointer to a struct problem

I'm trying to build a ternary search tree for a school project. As far as I can tell, my code looks okay. But, the leaf nodes of the original root function are not being initialized when I use malloc....
Evan's user avatar
  • 5
0 votes
0 answers
53 views

Near-Neighbor Searching in Ternary Search Tree

How is the search for the nearest neighbors in the tree? Trying to find information, I get only some formulas without illustrative examples. enter image description here Example of a function: void ...
Willy Adams's user avatar
0 votes
0 answers
43 views

Can ternary search trees be used for every word?

A node has three children, left, right, and middle, but what if those are occupied? Then what? And by a different character? If the root is 'b', and I try to insert cecil and dock, then what will I do?...
FariyaAchhab's user avatar
0 votes
1 answer
103 views

What is the name of this data structure search algorithm?

I have a tree search algorithm that uses multiple keys and each node has a sub tree which is searched with the next key in the list of keys until the keys run out and the data being searched is in ...
Christ Kennedy's user avatar
0 votes
1 answer
676 views

Properly deleting a node in a Ternary Search Tree

I want to delete a specific node using a key from a Ternary Search Tree. This works pretty well in most cases, but in some of my test sets, nodes that do not have a middle child also do not store ...
deathkid535's user avatar
0 votes
0 answers
542 views

How to implement autocomplete with top K suggestions algorithm?

This is a question for an interview: Write a program to implement autocomplete for a given set of N strings and positive weights. That is, given a prefix and an integer k, find the top k strings in ...
LOCKLOCK's user avatar
  • 341
0 votes
0 answers
157 views

Ternary Search Tree Implementation in R

I'm trying to implement a ternary search tree in R. Here's the logic I'm trying to implement: A vector will be "tiered" by designating each level of the tree as the next 3^somepower of cells after ...
GFauxPas's user avatar
  • 299
0 votes
0 answers
261 views

Ordering for creating a balanced Ternary Tree

I'm trying to create a balanced ternary tree. To do that I want to insert keys in an order that ensures the tree is built so that each node partitions the range of characters below it evenly. So ...
Ian Mercer's user avatar
  • 38.8k
0 votes
0 answers
203 views

Serialize custom ternary search tree in java

I would like to convert a dictionary of words into a binary file. after some search time, I found out that ternary search tree is the best option for my usage. I couldn't find how to serialize it to a ...
leah's user avatar
  • 433
0 votes
1 answer
843 views

Searching for (NOT with) wildcards inside an ternary search tree

I want to modify an recursive function from an 'ternary search tree' library (sourceforge & http://code.google.com/p/ternary-search-tree/). The default behaviour is to search in an ternary search ...
Constantin's user avatar
  • 8,799
-1 votes
1 answer
72 views

Search function for a tree

I am working with a ternary search tree. Following code should give you an overview of how the tree looks like. Every leaf will contain a pointer to a linked list which contains pointer to the head ...
user1010101's user avatar
  • 2,098