Stack Overflow
Stack Overflow

Questions tagged [radix-tree]

A radix tree is a trie where each node with only one child is merged with its child as form of space optimization.

44 questions
130
votes
4 answers

What is the difference between trie and radix trie data structures?

Are the trie and radix trie data structures the same thing? If they aren't the same, then what is the meaning of radix trie (AKA Patricia trie)?
Aryak Sengupta
  • 1,727
  • 2
  • 18
  • 23
15
votes
6 answers

Trie implementation

I am attempting to implement a very simple Trie in Java that supports 3 operations. I'd like it to have an insert method, a has method (ie is a certain word in the trie), and a toString method to return the trie in string form. I believe I have…
dc.
  • 1,429
  • 2
  • 17
  • 29
9
votes
3 answers

What's the space complexity of a radix tree?

I've been always concerned with the space usage of a radix tree, but I didn't find any helpful discussions on this. Now let's say we have a radix tree implementation same as linux radix-tree.c, which takes a integer and use every 6 bits to index…
Jun
  • 426
  • 1
  • 7
  • 16
7
votes
1 answer

Significance of the term "Radix" in Radix Tree

While it is hard to find an unanimous definition of "Radix Tree", most accepted definitions of Radix Tree indicate that it is a compacted Prefix Tree. What I'm struggling to understand is the significance of the term "radix" in this case. Why…
KGhatak
  • 6,995
  • 1
  • 27
  • 24
6
votes
1 answer

How to create, update and read a radix tree that won't fit into memory?

I’m interested in using a radix tree (or Patricia trie) to store a hash/dict/array of strings -> values. However, I'm finding that I have too many strings to fit into memory. I found an article by Algolia about how they solved this problem with…
Xeoncross
  • 55,620
  • 80
  • 262
  • 364
5
votes
1 answer

how to traverse page cache tree (radix tree) of a file address space in linux kernel

I need to get page-cache statistics of an open file. There is a address_space pointer(f_mapping) in file struct which in turn has the root of the radix tree called page_tree. I need to traverse that tree to get information about all the cached pages…
Sushmita Bhattacharya
  • 453
  • 2
  • 7
  • 15
5
votes
2 answers

Huffman encoding with variable length symbols

I'm thinking of using a Huffman code to compress text, but with symbols of variable length (strings). For example (using an underscore as a space): huffman-code | symbol ------------------------------------ 00 | _ 01 | E 100 …
Laurent Grégoire
  • 4,006
  • 29
  • 52
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
4
votes
1 answer

Why in linux kernel radix_tree_preload returns with preemption disabled

I was going through an article on linux kernel radix tree implementation, link of article is mentioned below: http://lwn.net/Articles/175432/ In this article it mentions that radix_tree_preload allocates sufficient memory so that the subsequent…
pastum
  • 609
  • 1
  • 5
  • 4
3
votes
2 answers

How to retrieve all the data/words in a radix trie in Javascript

I've been able to cook up a Radix tree example in JavaScript (not optimised, so don't judge) So far I have been able to Add, Transverse and Find nodes. I'm having trouble writing a function that can retrieve all nodes, this is where I require…
Knights
  • 1,467
  • 1
  • 16
  • 24
2
votes
4 answers

Speed/Memory usage estimate for different data structures

I'm trying to decide which data structure to use for the following. Lets say I have maybe 10 million keys that contain pointers to unique objects containing some data. The keys are UUID's think of them as 16 byte binary arrays. The UUID's are…
hookenz
  • 36,432
  • 45
  • 177
  • 286
2
votes
1 answer

Golang Serialize go-radix Tree to file?

I've been working on serializing a radix tree (used for indexing) to a file in golang. The radix tree nodes are storing 6-bit roaring bitmaps (see https://github.com/RoaringBitmap/roaring). The following code is what I am using, and the output I am…
danthegoodman
  • 501
  • 4
  • 10
2
votes
0 answers

How to access Apache PatriciaTrie TrieEntry key?

In my app i have about 50Mb of strings that have lot's of common parts. I'd like to reduce memory consumption by using Radix Trie (Patricia Tree), eg. Apache collections impl. The goal is to keep references to entries and get full strings once they…
4ntoine
  • 19,816
  • 21
  • 96
  • 220
2
votes
1 answer

Longest Prefix Lookup from Disk

I currently have some implementation which performs Longest Prefix Lookup (LPM) from a radix tree data structure. This data structure contains IP prefixes (radix tree with max depth of 128 bits), and it is currently fully maintained in memory. The…
michael
  • 530
  • 4
  • 16
2
votes
1 answer

What is the complexity of retrieving all elements of a given prefix in a prefix tree (trie)?

I know that searching for a given prefix in a trie is in O(M) where M is the maximum length of any word inserted into the trie. But what is the time-complexity of retrieving all elements that start with a specific prefix? I thought about a possible…
flackbash
  • 488
  • 2
  • 16
1
2 3