sâmbătă, 5 martie 2011

Radix tree implementation in C#

Update: you can find the entire source code here 

This is my implementation of a radix tree data structure. This is a data structure very similar to a trie. Basically instead of having each one of your nodes hold a char you have each one of your nodes store a string or as wikipedia puts it, it is a trie where "each node with only one child is merged with its child".
As I understand it the names radix tree and crit bit tree are only applied to trees storing integers and Patricia trie is retained for more general inputs.
As usual I am outputting the code for each class.

First, the node:

Then the actual tree
And the test program:

5 comentarii:

  1. Hello Andrei,

    Thanks for sharing your solutions.

    Sorry to ask this but, what do you intend to do on line 055?

    054 if ((matches == 0) || (curNode == _root) ||
    055 ((matches > 0) && (matches <>= curNode.Label.Length)))

    Using the operator <>=

    Also on line 074

    074 else if(matches < commonroot =" wordPart.Substring(0," branchpreviouslabel =" curNode.Label.Substring(matches," branchnewlabel =" wordPart.Substring(matches," label =" commonRoot;" newnodepreviouslabel =" new" newnodenewlabel =" new" matches ="="> curNode.Label.Length)

    Did I miss the definition of commoroot?

    Also on line 101

    101 for (int i = 0; i <>

    Have you finished the cycle, or you left it for us to finish it by ourselves?

    Thanks!!!

    RăspundeţiȘtergere
    Răspunsuri
    1. Hi,
      Sorry about that. It's the syntax highlighter messing up the code.
      Anyway this is the proper code for line 74:
      if ((matches == 0) || (curNode == _root) ||
      ((matches > 0) && (matches < wordPart.Length) && (matches >= curNode.Label.Length)))
      and this one for 101:
      //go throught the two streams
      for (int i = 0; i < minLength; i++)
      {
      //if two characters at the same position have the same value we have one more match
      if(word[i] == curNode.Label[i])
      matches++;
      else
      //if at any position the two strings have different characters break the cycle
      break;
      }
      //and return the current number of matches
      return matches;
      }

      If anyone can suggest a better syntax highlighter please do so. This one has lots of bugs.

      I promise I'll upload all these codes to github or something like that as soon as I find the time.

      Ștergere
  2. Hi this is somashekhar i want to ask in the internal node of particia tree what it contains plz reply me???

    RăspundeţiȘtergere
    Răspunsuri
    1. Grab the code from here: https://github.com/paratechnical/RadixTree I will try to update the code don't know why nothing is visible anymore

      Ștergere