Coding Notes

Ideas and thoughts from Seth Long

Ternary Search Tree in C#

My blog is now located at http://www.WhoIsSethLong.com

I recently had the urge to create a Ternary Search Tree in C# (doesn’t everyone get these urges?).  My first stop was  at http://www.ddj.com/windows/184410528 for a GREAT article on how Ternary Search Trees work and how to create them.  If you’re really unfamiliar with Ternary Search Trees, I’d recommend starting with the wikipedia article on them before reading this.

For this project, I began by creating a class called TSTree and another called TSNode.  The TSNode class is a very simple class that simply contains properties for the split char, low node, equal node and hi node (later we will add a value).   Here is an example of the TSNode class:

    class TSNode
    {
        private char splitChar;
        private TSNode lowNode;
        private TSNode eqNode;
        private TSNode hiNode;
        private object value;
        public char SplitChar
        {
            get { return this.splitChar; }
            set { this.splitChar = value; }
        }
        public TSNode LowNode
        {
            get { return this.lowNode; }
            set { this.lowNode = value; }
        }
        public TSNode EqNode
        {
            get { return this.eqNode; }
            set { this.eqNode = value; }
        }
        public TSNode HiNode
        {
            get { return this.hiNode; }
            set { this.hiNode = value; }
        }
        public object Value
        {
            get { return this.value; }
            set { this.value = value; }
        }
    }

Later on we can add more to the class but for now that is a good start.  So lets briefly go over what it all does. The first property SplitChar holds the char that this node represents. The LowNode holds a reference to a node that holds a SplitChar that is less then the value of this Node, HiNode holds a reference to a node that holds a SplitChar that is greater then the value of this Node and of course EqNode holds a reference to a node that has a SplitChar that is equal.  Pretty much like a binary tree node but with a reference to an equal node added (Binary = 2, Ternary = 3).

The next step is to add an Add method to the TSTree class.  What the Add method is going to do is add a node for each char in a string to the tree.  For example, if we have an empty tree and add the key “cat” to it, it will add nodes for ‘c’, ‘a’, and ‘t’ to the tree.  Since our word is “cat”, the root node will have a SplitChar value of ‘c’.  In it’s EqNode property it will contain a reference to another node with a SplitChar value of ‘a’.  This node will also contain a EqNode reference to another node with a SplitChar value of ‘t’.  So we have three nodes in our tree whos collective SplitChar values spell out “cat”.

Here is the code for the Add method:

        public TSNode Add(TSNode p, string s, int pos, object value)
        {
            if (p == null)
            {
                p = new TSNode();
                p.SplitChar = s[pos];
            }
            if (s[pos] < p.SplitChar)
            {
                p.LowNode = Add(p.LowNode, s, pos, value);
            }
            else if (s[pos] == p.SplitChar)
            {
                if (pos < s.Length – 1)
                {
                    p.EqNode = Add(p.EqNode, s, ++pos, value);
                }
                else
                {
                    p.Value = value;
                }
            }
            else
            {
                p.HiNode = Add(p.HiNode, s, pos, value);
            }
            return p;
        }

Now, when we want to add another word things get interesting.  So, lets add the word “cab” to our tree and see what happens next.  We start by looking at the root node in our tree and see that ‘c’ matches the first letter in our word “cab”.  Since it matches, we follow the EqNode reference and check the next SplitChar value.  In this case it is ‘a’, which again matches the next char in our word “cab”.  Again, we follow the EqNode reference and check the next SplitChar value.  This time, the value of the SplitChar does not equal the last value of our word.  So we have to check if the SplitChar value is greater then or less then the value of ‘b’.  ‘b’ is less then the value of ‘t’ so we will follow the path of the LoNode. In this example the LoNode value is null so we create another node and set its SplitChar value to ‘b’.  That’s how we add items to the tree.

Searching for a string in our tree is going to work a lot like adding an item to it.  If we were searching for the word “cab” in the previous tree we created, we would start by checking the root node’s SplitChar value and compairing it to the value of the first char in our search word.  In this case the ‘c’ in our search word matches the SplitChar value of the root node.  So we follow the reference in the EqNode property to the next node.  The next node contains a SplitChar value of ‘a’ and again matches the second char in our search word of “cab”.  Again, we follow the EqNode reference to the next node and check the SplitChar value.  This time they are not equal so we then determine if ‘b’ is greater then or less then the ‘t’ that is stored in the SplitChar value.  ‘b’ is less then ‘t’ so we take the LoNode to the next node.  This node contains a SplitChar value of ‘b’ so we have found our match!  Here is the code for the search:

        public object Search(string s)
        {
            TSNode p = root;
            int x = 0;
            while (p != null)
            {
                if (s[x] < p.SplitChar)
                {
                    p = p.LowNode;
                }
                else if (s[x] == p.SplitChar)
                {
                    x++;
                    if (x == s.Length && p.Value != null)
                    {
                        return p.Value;
                    }
                    p = p.EqNode;
                }
                else
                {
                    p = p.HiNode;
                }
            }
            return null;
        }

So those are the major methods of a Ternary Search Tree.  I will post the complete code up here shortly.  It’s also important to remember that even though a Ternary Search Tree is similar in use to other key-value type data structures it does have some major differences.  First, the key MUST be a string. Second, the Ternary Search Tree has the ability to return partial matches and even similar matches. Very Cool!

– Seth Long

Advertisements

February 1, 2008 - Posted by | Data Structures

4 Comments »

  1. I like the example you have posted. Any chance of you posting the complete code.

    Comment by William Rhoten | April 26, 2008 | Reply

  2. Agreed, I’d love to see a C# implementation of the ternary search tree.

    Comment by John Q | August 16, 2008 | Reply

  3. Can you post complete code, please ? It´s perfect, but I have a little problem with searching

    Comment by Perry | October 18, 2008 | Reply

  4. Can you post complete code, please ? It´s perfect, but I have a little problem with searching

    Comment by Hijab Khan | January 8, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: