Structure of a Trie

Explore the structure of a trie and its implementation in C#. Understand how trie nodes represent alphabets, manage children pointers, and mark word endings. This lesson helps you develop a trie class in C# to efficiently store and search English words.

We'll cover the following...

- Introduction
- The trie node class
- The trie class

The trie node class

The node of a trie represents an alphabet. For example, if you want to insert “hello” in the trie, you will need to add 5 nodes; one for each alphabet. A typical node in a trie consists of three data members:

[] children: An array which consists of pointers to children nodes. The size of this array depends on the number of alphabets. By default, all are set to null.
isEndWord: It is a flag to indicate the end of a word. It is set to false by default and is only updated when a word ends during insertion.

Here is the implementation in C#:

namespace chapter_7
{
    class TrieNode
    {
        const int ALPHABET_SIZE = 26;

        public TrieNode [] children = new TrieNode[ALPHABET_SIZE];
        public bool isEndWord;

        public TrieNode()
        {
            this.isEndWord = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
            {
                this.children[i] = null; ;
            }
        }
        public void markAsLeaf()
        {
            this.isEndWord = true;
        }
        public void unMarkAsLeaf()
        {
            this.isEndWord = false;
        }
    }
}

The trie class

The Trie will be implemented using the TrieNode class. As discussed above, a trie node represents one alphabet that keeps pointers to its children nodes. Each node can have 26 children at max if you are storing English words.

A root node is placed at the top and contains 26 pointers (one per alphabet). These pointers hold either null or another trieNode. The root is similar to the headNode from linked lists.

The index of the children pointers is decided based on the sequence of the alphabets (starting from 0). For instance, the node containing the alphabet a (if it exists) will be stored at the “0th” index. B is at the 1st, and node z will come at the 25th index.

All the words are stored in a top-bottom manner. While storing the last character, you should always set the isEndWord flag as true to indicate the end of a word. This technique helps you search for the existence of a certain word. A typical trie class looks like this in C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace chapter_7
{
    class TrieNode
    {
        const int ALPHABET_SIZE = 26;

        public TrieNode[] children = new TrieNode[ALPHABET_SIZE];
        public bool isEndWord;

        public TrieNode()
        {
            this.isEndWord = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
            {
                this.children[i] = null; ;
            }
        }
        //Function to unMark the currentNode as Leaf
        public void markAsLeaf()
        {
            this.isEndWord = true;
        }
        //Function to unMark the currentNode as Leaf
        public void unMarkAsLeaf()
        {
            this.isEndWord = false;
        }

    }
    class Trie
    {
        public Trie()
        {
            
        }
        //Function to get the index of a character 't'
        public int getIndex(char t)
        {
            return t - 'a';
        }
        //Function to insert a key,value pair in the Trie
        public void insertNode(string key)
        {

        }
        //Function to search given key in Trie
        public bool searchNode(string key)
        {
            return false;
        }
        //Function to delete given key from Trie
        public bool deleteNode(string key)
        {
            return false;
        }
    } 
}

1.Introduction to Complexity Measures

2.Introduction to Arrays

3.Introduction to Linked Lists

4.Introduction to Stack/Queues

5.Introduction to Graphs

6.Introduction to Trees

7.Trie

8.Introduction to Heap

9.Introduction to Hashing

10.Summary of Data Structures

Structure of a Trie

Introduction

The trie node class

The trie class