duminică, 30 ianuarie 2011

Implementation of the prefix tree(trie) data structure in C#

Update: all the source code for this article can be accessed from here

A prefix tree is a data structure with many uses. I won't go into details about this data structure Wikipedia does a better job than I could. What I will do is post a C# implementation of this data structure and in a following post I will show how to use this data structure when implementing an auto-complete solution.

These are the properties of a prefix tree:
  • it stores strings(finite sequences of chars)
  • it had nodes :) (doooooooh!)
  • each node stores a character
  • each node can have a number of subnodes(0,1,2, ... infinity)
  • the char stored in a subnode is the one following the char stored by the node in a string
  • each node has a flag which is raised if a word ends there(this doesn't mean it can't have subnodes for example a prefix tree can store the words "cat" and "catastrophy" in this case node 3 stores 't' and has a subnode that stores 'a')

And now the code:
The node:



The tree:



The main program:

2 comentarii:

  1. The AddWord and Find function seem to be incomplete. I dont understand why they have the XML nodes and the Node class ends with . Am I missing something?

    RăspundețiȘtergere
  2. @Mujahid Shariff yes there seems to be some kind of an error with the code highlighting script
    I'll try and fix it first time I get

    RăspundețiȘtergere

The Trie: A Neglected Data Structure

From the very first days in our lives as  programmers , we’ve all dealt with data structures: Arrays, linked lists, trees, sets, stacks and...