Abstract

A trie, also called a digital tree or a prefix tree, is a tree data structure used to locate particular keys from within a set. This implementation considered keys as a strings, since it is most commonly encountered. A key is stored between multiple nodes linked to each other by an individual character of a key. To access a key from a trie, it is necessary to perform a depth-first search traverse algorithm.
As opposed to a binary search tree, a key associated with a node is not stored in it. Instead, it is defined by a node position in a trie.
Every children of the node have a common string prefix associated with the parent node. The root node is associated with an empty string.

Table Of Content

• Common Operations
  • Legend
  • Operation
• Applications
• Project Details
• How To Use
  • Local dependency
  • Source code
  • Compilation
• Author

Common Operations

Operations and structures were implemented following OOP paradigm.

Legend

• implemented
• not yet implemented

Operation

• Insertion: trie.insert(word: String): void
• Searching: trie.search(word: String): boolean
• Deletion: trie.erase(word: String): boolean

Applications

Tries are commonly used for text prediction, autocompleting dictionaries and approximate matching algorithms. They are especially efficient in spell checking and longest prefix match algorithms, since they occupy less space and enable faster searching when the set contains large number of short strings.

Project Details

• Language: Java 21 (Preview)
• Built with: Gradle (Kotlin)
• Test framework: JUnit 5

How To Use

Local dependency

1. Download a jar file attached to the release: v1.0.

2. You can verify SHA of downloaded file (details are in the release description).

3. Copy that jar file into a subdirectory of your project directory, e.g.: YourProject/libs/ and add as local dependency:

• Gradle (Kotlin):

Add into dependencies function in build.gradle.kts:

    implementation(files("./libs/Trie-1.0.jar"))

• Gradle (Groovy):

Add into dependencies function in build.gradle:

    implementation files('./libs/Trie-1.0.jar')

Source code

Copy files: Trie.java and TrieNode.java into a java package of your choice in your project.

Compilation

If you would like to use this implementation, you should know that at the moment when it was written (12.12.2023), the code is written in Java 21 Preview. Hence, if you are going to compile and run the project containing this implementation, you should use JDK 21 or possible any newer and add a flag --enable-preview, e.g.:

• Javac (Compile to bytecode)

    javac --enable-preview YourMainClass.java

• Java (Run)

    java --enable-preview YourMainClass

• Gradle (Kotlin)

build.gradle.kts:

    // ...
    // NEEDED IF YOU HAVE TEST CLASSES
    tasks.test {
        // ...
        jvmArgs("--enable-preview")
    }

    // REQUIRED
    tasks.withType<JavaCompile> {
        // ...
        options.compilerArgs.add("--enable-preview")
    }

• Gradle (Groovy)

build.gradle:

    // ...
    // NEEDED IF YOU HAVE TEST CLASSES
    test {
        // ...
        jvmArgs(['--enable-preview'])
    }

    // REQUIRED
    tasks.withType(JavaCompile).each {
        // ...
        it.options.compilerArgs.add('--enable-preview')
    }

• Compile & Run with IntelliJ:

1. Open Run/Debug Configuration of your project.
2. Expand list: Modify options.
3. Add VM option -> shortcut: ALT + V.
4. Paste --enable-preview into the VM options.
5. Confirm by clicking OK.

Author

@lucasmalara