RadixTree

General

Category
Free
Tag
Data Structures
License
Apache License, Version 2.0
Registered
Jan 13, 2022
Favorites
0
Link
https://github.com/aminography/RadixTree
See also
rtree
javatuples
SparseBuilders
GroupOfX
Solid

Additional

Language
Kotlin
Version
v1.2.0 (Dec 29, 2021)
Created
Feb 15, 2021
Updated
Dec 29, 2021
Owner
Amin Hassani (aminography)
Contributor
Amin Hassani (aminography)
1
Activity
Badge
Generate
Download
Source code

Announcement

RadixTree

This project provides an implementation of RadixTree data-structure, which is a great tool for indexing a large number of records with string keys and performing a prefix search with an optimal time complexity.


Table of Contents


Main Characteristics

  • Space and time efficient.
  • Retrieves elements sorted, when elements insertion is sorted.

Complexity Order

RadixTree or compressed trie is the compact and space-optimized form of prefix tree, which enables us to find all nodes whose keys start with a prefix string, by a O(L + V) complexity order, where L is the length of input prefix, and V stands for number of nodes that will be discovered.

In case of large datasets, the length of keys are dramatically lower than number of items, which means that the time complexity of prefix search using RadixTree is significantly better than linear search.


Download

RadixTree is available on MavenCentral to download using build tools systems.

• Gradle

Add the following lines to your build.gradle file:

dependencies {
    implementation 'com.aminography:radixtree:1.2.0'
}

• Maven

Add the following lines to your pom.xml file:

<dependencies>
    <dependency>
        <groupId>com.aminography</groupId>
        <artifactId>radixtree</artifactId>
        <version>1.2.0</version>
    </dependency>
</dependencies>