Stack Overflow
Stack Overflow

Questions tagged [prefix-tree]

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

57 questions
10
votes
3 answers

Implementing a Trie to support autocomplete in Python

I'm trying to implement a data structure that supports autocomplete on a website. I've managed to implement an iterative version of a Trie. It supports the two primary methods of adding and searching in a Trie. However now I need to add a method…
Melissa Stewart
  • 3,483
  • 11
  • 49
  • 88
5
votes
2 answers

Algorithm for 2 Pattern String Matching

I need to code an algorithm for longest two pattern prefix/suffix match whose time complexity is O(n+m1+m2), where n is the length of the String and m1, m2 are the lengths of pattern1 and pattern2 respectively. Example: if the String is "OBANTAO"…
user3320657
5
votes
2 answers

Determine if one string is a prefix of another

I have written down a simple function that determines if str1 is a prefix of str2. It's a very simple function, that looks like this (in JS): function isPrefix(str1, str2) // determine if str1 is a prefix of a candidate string { if(str2.length…
Parijat Kalia
  • 4,929
  • 10
  • 50
  • 77
5
votes
3 answers

Choosing an appropriate data structure (hash table vs. suffix tree) for indexing a very large set of similar strings

I have a large set of strings, on order ~10^12 or so, and I need to choose an appropriate data structure so that, provided a string, I can retrieve and associated integer value in something like O(log(n)) or O(m) time where 'n' is the length of the…
Bob
  • 51
  • 3
4
votes
1 answer

Which search is faster, binary search or using prefix tree?

Suppose I have a list of strings and a prefix tree of those strings, and I would like to locate a string given a key, which one is more faster? binary search or prefix tree search? Why and what's the time complexity? Thanks!
Jack Twain
  • 6,273
  • 15
  • 67
  • 107
4
votes
2 answers

how to convert a propositional logical tree into conjunction normal form (CNF) tree

I have a string like string s="(=> P (OR (AND A (NOT B)) (AND B (NOT A))))"; and convert it output the CNF of this string,like ( OR ( NOT P ) ( OR A B ) ) ( OR ( NOT P ) ( OR ( NOT B ) ( NOT A ) ) ) do I need to make a struct TreeNode to…
Rebecca
  • 111
  • 2
  • 12
4
votes
5 answers

Autocomplete Style Prefix Lookup

Making a specific example: You have a list of every first name in the USA. You want to autosuggest completions in a GUI. The obvious thing is to do is use a radix tree to get a list of names for the given prefix. However, this doesn't take into…
koblas
  • 25,410
  • 6
  • 39
  • 49
3
votes
1 answer

Typing Scala collections

I wanted to learn the new Scala collections framework by making a very general prefix tree. Not only must the keys and the values be parameters, but the type of the maps used in each node must be parameters too. So I tried this: import…
James Cranch
  • 31
  • 1
3
votes
2 answers

Can I use a trie that has a whole word on each node?

I want to implement a trie to check for the validity of paths, so I would have a tree built that contains all the possible path constructions by breaking it down by directory. So something like /guest/friendsList/search would go from the root node…
zulusam
  • 185
  • 1
  • 8
3
votes
1 answer

Prefixes and Namespaces with C# Objects

I am attempting to create a POST function that serialises C# class objects into XML. The part I am having great difficulty with is adding namespace prefixes to the sub-root element's children, so in this instance, contact children only. The only way…
PurpleSmurph
  • 2,055
  • 3
  • 32
  • 52
3
votes
1 answer

Javascript: Find exactly 10 words in a prefix tree that start with a given prefix

I have a trie (also called a prefix tree). Given a prefix, I want to get a list of ten words that start with the prefix. The thing that's unique about this problem is that I only want 10 of the words that start with the given prefix-- not all of…
user2946797
  • 171
  • 2
  • 11
3
votes
1 answer

Segmentation fault when adding to a prefix tree

I'm trying to write a function to input words from a text file into a prefix tree, but it keeps giving me segmentation fault int wordCount = 0; typedef struct node { bool isWord; struct node* children[26]; }node; struct node* newNode(struct…
Ryan Aleksander
  • 423
  • 5
  • 18
3
votes
2 answers

Address book and trie structure

I'have a question for you. I have to implement a business address book that contains 30000 names. All the names contains firstname and lastname. I have to implement an autocomplete textbox that search not only typing firstname but also by…
Mapo
  • 115
  • 1
  • 11
3
votes
2 answers

Is sorted iteration an inherent feature of a Trie or it is up to implementation to provide it?

Concerning Trie from Wikipedia: [Compared to HashTable] Tries support ordered iteration I am not sure what is meant here first of all. Is it the same as sorted iteration? Additionally is this supposed to be an inherent feature of this…
Cratylus
  • 52,998
  • 69
  • 209
  • 339
2
votes
2 answers

Basic prefix tree implementation question

I've implemented a basic prefix tree or "trie". The trie consists of nodes like this: // pseudo-code struct node { char c; collection childnodes; }; Say I add the following words to my trie: "Apple", "Ark" and "Cat". Now when I…
MrDatabase
  • 43,245
  • 41
  • 111
  • 153
1
2 3 4