Back to TILs

C++ trie

Date: 2023-04-06Last modified: 2023-06-27
C++trie

Table of contents

Introduction

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.

Trie follows some property that If two strings have a common prefix then they will have the same ancestor in the trie. A trie can be used to sort a collection of strings alphabetically as well as search whether a string with a given prefix is present in the trie or not.

  Trie trie;
  trie.insert("hello");
  trie.insert("hello");
  trie.insert("world");

  auto printExists = [trie](const std::string& key) {
    fmt::print("{:20} -> {}\n", key, trie.search(key));
  };

  auto printStartsWith = [trie](const std::string& key) {
    fmt::print("{:20} -> {}\n", key, trie.startsWith(key));
  };

  printExists("hello");
  printExists("world");
  printExists("helloworld");
  printStartsWith("hell");
  printStartsWith("wor");
  printStartsWith("abc");

Possible output

hello                -> true
world                -> true
helloworld           -> false
hell                 -> true
wor                  -> true
abc                  -> false

References