Member Avatar for arrogant

can u ppl help me in implementing trie........... i need complete data structure of trie...............and how to implement it????

  • 6 Contributors
  • 6 Replies
  • 288 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Member #46692

Dani AI

Generated

Thread asks for a trie implementation and a bit of design guidance. started the request; ’s short definition is correct (tries store common prefixes). offered a C++ implementation and linked a BST resource (BSTs are different). Below is a compact, modern C++ example and practical notes that complement those replies.

Design notes (short):

  • Core node: boolean "is-word" + children for the alphabet.
  • For small fixed alphabets (lowercase a–z) use an array of 26 pointers for speed and predictable memory.
  • For large or sparse alphabets (Unicode, mixed chars) use std::unordered_map<char, …> to save memory.
  • Typical costs: insert/search = O(L) where L is string length. Memory can be large: nodes ~= sum of all inserted character positions. Consider compressed/radix tries for big datasets.

Minimal C++ (works for lowercase a–z, C++11+):

#include <array>
#include <memory>
#include <string>
#include <algorithm>
#include <cctype>

struct TrieNode {
bool isWord = false;
std::array<std::unique_ptr<TrieNode>, 26> next;
};

class Trie {
std::unique_ptr<TrieNode> root = std::make_unique<TrieNode>();
public:
void insert(const std::string& s) {
TrieNode* cur = root.get();
for (unsigned char ch : s) {
if (!std::islower(ch)) continue; // input sanitise for this example
int i = ch - 'a';
if (!cur->next[i]) cur->next[i] = std::make_unique<TrieNode>();
cur = cur->next[i].get();
}
cur->isWord = true;
}

bool search(const std::string& s) const {
    const TrieNode* cur = root.get();
    for (unsigned char ch : s) {
        if (!std::islower(ch)) return false;
        int i = ch - 'a';
        if (!cur->next[i]) return false;
        cur = cur->next[i].get();
    }
    return cur->isWord;
}

bool erase(const std::string& s) { return erase_impl(root.get(), s, 0); }

private:
bool erase_impl(TrieNode* node, const std::string& s, size_t d) {
if (!node) return false;
if (d == s.size()) {
if (!node->isWord) return false;
node->isWord = false;
return std::all_of(node->next.begin(), node->next.end(),
[](const auto& p){ return !p; });
}
unsigned char ch = s[d];
if (!std::islower(ch)) return false;
int i = ch - 'a';
if (!node->next[i]) return false;
bool childRemovable = erase_impl(node->next[i].get(), s, d+1);
if (childRemovable) node->next[i].reset();
return !node->isWord && std::all_of(node->next.begin(), node->next.end(),
[](const auto& p){ return !p; });
}
};

Practical points and traps:

  • Sanitize and normalize inputs (lowercase, strip accents) before using array-indexed tries.
  • Deletion is subtle; test cases for prefixes (e.g. insert "he", "her"; erase "her") are important.
  • For very large datasets, consider memory pooling, radix trees, or DAWGs to reduce node count.
    This complements the prior replies and gives a ready-to-compile C++ starting point.

Recommended Answers

All 6 Replies

Member Avatar for Member #46692

can u ppl help me in implementing trie........... i need complete data structure of trie...............and how to implement it????

Well, have you tried doing this yourself?
:surprised

Member Avatar for ivanCeras

what is a trie?....

Member Avatar for Narue

>what is a trie?....
A search tree that stores common prefixes in internal nodes, and the prefixes have some form of lexographical order. A search is done by matching the prefix nodes until you reach a leaf, which has the complete string. It's a surprisingly powerful data structure.

>i need complete data structure of trie...............and how to implement it????
That's not helping, that's doing it for you. We're not your personal homework service.

Member Avatar for fulyaoner

can u ppl help me in implementing trie........... i need complete data structure of trie...............and how to implement it????

Hi, I can help you if you want.
I have implemented a trie in C++, look for details

or send mail to fulya at fulyaoner dot com

Member Avatar for dubeyprateek

may be this can also help u

Member Avatar for Member #46692

>may be this can also help u

Would hurt to run your article through spell checker before you release it into the public domain? He he.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.