Package com.everdro1d.libs.structs

Class Trie<T>

java.lang.Object
com.everdro1d.libs.structs.Trie<T>
Type Parameters:
T - the type of value stored in the Trie
public class Trie<T> extends Object

Definition

Trie data structure is defined as a Tree based data structure that is used for storing some collection of strings and performing efficient search operations on them.

The word Trie is derived from reTRIEval, which means finding something or obtaining it.

Properties of Trie:

  • Prefix-based: Tries are prefix-based data structures that can efficiently handle prefix matching, prefix searching, and prefix deletion.
  • Tree-based: Trie is a tree-structured data structure making it easily representable.
  • Fast-Search: Trie has search time complexity O(m), where m is the length of the key.
  • Memory requirement: Trie has more space requirements, but it can be optimized,
  • Easy to implement: Its iterative approach makes it easier to implement.

Applications of Trie:

Trie is involved wherever string manipulation or processing is involved. Here are a few usages of trie:
  • Autocomplete: Tries are commonly used in auto-complete applications, such as when typing in a search bar.
  • Spell checking: By storing a large dictionary of words in a trie, it can be used to quickly check if a given word is spelled correctly.
  • IP routing: Tries are also used in IP routing, where the prefix of an IP address is used to determine the network address to forward packets.
  • Text compression: Tries can also be used in text compression algorithms such as Huffman coding.

Advantages of Trie:

  • Tries can be optimized to use less memory by compressing common prefixes into a single node, reducing the overall size of the data structure.
  • Tries can easily handle partial matches, prefix searches, and autocomplete operations.
  • Tries offer fast and efficient search operations for large collections of strings or words. For example, to search a single name in a student database of universities.
  • Tries can store additional data associated with each key in the leaf nodes, making it easy to access additional information about the keys.

Disadvantages of Trie:

  • Tries can be memory-intensive, especially for large collections of long strings, as each node requires additional memory to store its character value and pointer references.
  • Tries may require extra time and space to build or update the data structure when keys are added or deleted.
  • Tries may be slower than hash tables or binary search trees for exact match operations.
Description source

  • Constructor Summary

    Constructors
    Constructor
    Description
    Trie()
    Creates a new Trie without any values.
    Trie(List<String> list)
    Creates a new Trie containing the keys given in the list.
    Trie(Map<String,T> map)
    Creates a new Trie containing the key-value pairs given in the map.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Clears the children of the root node.
    boolean
    contains(String key)
    Checks if the given key exists in the tree.
    boolean
    containsAll(List<String> list)
    Checks if all the given keys exist in the tree.
    boolean
    containsAny(List<String> list)
    Checks if any of the given keys exist in the tree.
    T
    get(String key)
    Get the value of a key in the Trie.
    void
    insert(String key)
    Inserts the given key into the Trie, creating nodes where necessary.
    void
    insert(String key, T value)
    Inserts the given key-value pair into the Trie, creating nodes where necessary.
    void
    insert(List<String> list)
    Inserts the list of keys into the Trie, creating nodes where necessary.
    void
    insert(Map<String,T> map)
    Inserts a map of key-value pairs into the Trie, creating nodes where necessary.
    boolean
    isEmpty()
    Checks if the Trie is empty.
    List<String>
    listKeys()
    List the keys in a Trie.
    List<String>
    listKeysMatching(String prefix)
    List the keys in a Trie that match the prefix.
    List<String>
    listKeysMatching(String prefix, int maxMatches)
    List the keys in a Trie that match the prefix with a limit on the number of matches.
    boolean
    remove(String key)
    Removes the given key from the Trie.
    boolean
    removeAll(List<String> list)
    Removes all keys in a given list from the Trie
    boolean
    set(String key, T value)
    Set the value for an existing key in the Trie.
    boolean
    startsWith(String prefix)
    Checks if any keys in the tree start with the given prefix.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Trie

      public Trie()
      Creates a new Trie without any values.

    • Trie

      public Trie(List<String> list)
      Creates a new Trie containing the keys given in the list.
      Parameters:
      list - list of key the tree should be init with

    • Trie

      public Trie(Map<String,T> map)
      Creates a new Trie containing the key-value pairs given in the map.
      Parameters:
      map - map of key-value pairs the tree should be init with

  • Method Details

    • insert

      public void insert(String key)
      Inserts the given key into the Trie, creating nodes where necessary.
      Parameters:
      key - key to insert

    • insert

      public void insert(String key, T value)
      Inserts the given key-value pair into the Trie, creating nodes where necessary.
      Parameters:
      key - key to insert
      value - value to associate with the key

    • insert

      public void insert(List<String> list)
      Inserts the list of keys into the Trie, creating nodes where necessary.
      Parameters:
      list - the list of keys to insert

    • insert

      public void insert(Map<String,T> map)
      Inserts a map of key-value pairs into the Trie, creating nodes where necessary.
      Parameters:
      map - the map of key-value pairs to insert

    • contains

      public boolean contains(String key)
      Checks if the given key exists in the tree.
      Parameters:
      key - key to check for
      Returns:
      true if all the nodes of the key exist in the Trie and the last node is EOW.

    • containsAny

      public boolean containsAny(List<String> list)
      Checks if any of the given keys exist in the tree.
      Parameters:
      list - the list of keys to check for
      Returns:
      true if any key in the list exists in the Trie and the last node of the key is EOW.

    • containsAll

      public boolean containsAll(List<String> list)
      Checks if all the given keys exist in the tree.
      Parameters:
      list - the list of keys to check for
      Returns:
      true if all keys in the list exists in the Trie and the last node of each key is EOW.

    • startsWith

      public boolean startsWith(String prefix)
      Checks if any keys in the tree start with the given prefix.
      Parameters:
      prefix - prefix to check for
      Returns:
      true if any key starts with or matches the prefix

    • isEmpty

      public boolean isEmpty()
      Checks if the Trie is empty.
      Returns:
      true if the root node has no children, else false.

    • clear

      public void clear()
      Clears the children of the root node.

    • remove

      public boolean remove(String key)
      Removes the given key from the Trie.
      Parameters:
      key - key to remove
      Returns:
      true if the key was removed, false otherwise (including key does not exist)

    • removeAll

      public boolean removeAll(List<String> list)
      Removes all keys in a given list from the Trie
      Parameters:
      list - list of keys to remove
      Returns:
      true if none of the given keys exist in the Trie, false otherwise

    • listKeys

      public List<String> listKeys()
      List the keys in a Trie.
      Returns:
      A list of all the keys in the Trie

    • listKeysMatching

      public List<String> listKeysMatching(String prefix)
      List the keys in a Trie that match the prefix.
      Parameters:
      prefix - prefix to match
      Returns:
      List of all matching keys in the Trie
      See Also:

    • listKeysMatching

      public List<String> listKeysMatching(String prefix, int maxMatches)
      List the keys in a Trie that match the prefix with a limit on the number of matches. Matches prefer the shortest keys first.
      Parameters:
      prefix - prefix to match
      maxMatches - maximum number of matches to return
      Returns:
      List of all matching keys in the Trie
      See Also:

    • get

      public T get(String key)
      Get the value of a key in the Trie.
      Parameters:
      key - the key to search for
      Returns:
      the value associated with the key

    • set

      public boolean set(String key, T value)
      Set the value for an existing key in the Trie.
      Parameters:
      key - key to search for
      value - value to set as
      Returns:
      true if value was set, false otherwise (including value does not exist)