Is it possible to generate all possible terms findable in a ternary search tree?

Question

From what I understand of ternary search trees, they are inverse deterministic in the items that can be sought and found (not sure about correct terms). What I mean, if you create a ternary tree for cat, bicycle, axis and you give someone the ternary tree, he should be able to deduct those three words from it.

Is this correct?

I'm asking, because I have a ternary tree structure that contains words like ISMAP, SELECTED and COMPACT (indeed, attributes of HTML 4) and I wonder if I could get the complete list of items that is stored in that tree (original documentation is gone). The structure looks like this:

internal static byte [] htmlAttributes = {
   72,5,77,0, 82,0,0,0, 69,0,0,0, 70,0,0,0, 0,0,0,1, 67,12,40,0, 79,7,0,0,
   77,31,0,0, 80,0,0,0, 65,0,0,0, 67,0,0,0, 84,0,0,0, 0,0,0,2, 73,11,18,0,
   84,0,0,0, 69,0,0,0, 0,0,0,1, 65,0,0,0, 67,0,0,0, 84,0,0,0, 73,0,0,0,
   79,0,0,0, 78,0,0,0, 0,0,0,1, 72,0,0,0, 69,0,0,0, 67,0,0,0, 75,0,0,0,
   69,0,0,0, 68,0,0,0, 0,0,0,2, 76,0,0,0, 65,0,0,0, 83,0,0,0, 83,0,0,0,
   73,0,0,0, 68,0,0,0, 0,0,0,1, 68,0,0,0, 69,0,0,0, 66,0,0,0, 65,0,0,0,
   83,0,0,0, 69,0,0,0, 0,0,0,1, 68,0,28,0, 69,7,15,0, 67,0,22,0, 76,0,0,0,
   65,0,0,0, 82,0,0,0, 69,0,0,0, 0,0,0,2, 65,0,0,0, 84,0,0,0, 65,0,0,0,
   0,0,1,1, 83,0,0,0, 82,0,0,0, 67,0,0,0, 0,0,0,1, 73,0,0,0, 83,0,0,0,
   65,0,0,0, 66,0,0,0, 76,0,0,0, 69,0,0,0, 68,0,0,0, 0,0,0,2, 70,0,0,0,
   69,0,0,0, 82,0,0,0, 0,0,0,2, 70,0,0,0, 79,0,0,0, 82,0,0,0, 0,0,0,1,
   78,8,48,0, 79,36,0,0, 83,30,55,0, 72,0,0,0, 65,0,0,0, 68,0,0,0, 69,0,0,0,
   0,0,0,2, 77,9,0,0, 85,0,0,0, 76,0,0,0, 84,0,0,0, 73,0,0,0, 80,0,0,0,
   76,0,0,0, 69,0,0,0, 0,0,0,2, 73,0,6,0, 83,0,0,0, 77,0,0,0, 65,0,0,0,
   80,0,0,0, 0,0,0,2, 76,0,0,0, 79,0,0,0, 78,0,0,0, 71,0,0,0, 68,0,0,0,
   69,0,0,0, 83,0,0,0, 67,0,0,0, 0,0,0,1, 72,0,9,0, 82,0,0,0, 69,0,0,0,
   70,0,0,0, 0,0,0,2, 65,0,0,0, 77,0,0,0, 69,0,0,0, 0,0,0,1, 82,0,0,0,
   69,0,0,0, 83,0,0,0, 73,0,0,0, 90,0,0,0, 69,0,0,0, 0,0,0,2, 82,14,22,0,
   69,0,0,0, 65,0,0,0, 68,0,0,0, 79,0,0,0, 78,0,0,0, 76,0,0,0, 89,0,0,0,
   0,0,0,2, 87,0,0,0, 82,0,0,0, 65,0,0,0, 80,0,0,0, 0,0,0,2, 80,0,0,0,
   82,0,0,0, 79,0,0,0, 70,0,0,0, 73,0,0,0, 76,0,0,0, 69,0,0,0, 0,0,0,1,
   83,0,12,0, 82,3,0,0, 67,0,0,0, 0,0,0,1, 69,0,0,0, 76,0,0,0, 69,0,0,0,
   67,0,0,0, 84,0,0,0, 69,0,0,0, 68,0,0,0, 0,0,0,2, 85,0,0,0, 83,0,0,0,
   69,0,0,0, 77,0,0,0, 65,0,0,0, 80,0,0,0, 0,0,0,1, 
};

Lou Franco · Accepted Answer · 2011-11-16T13:12:12.497

I think the algorithm is something like this

printOutWords(root, wordSoFar)
     if (!root.hasMiddle)
        print wordSoFar + root.char

     if (root.hasMiddle)
        printOutWords(root.middle, wordSoFar + root.char)
     if (root.hasLeft)
        printOutWords(root.left, wordSoFar)
     if (root.hasRight)
        printOutWords(root.right, wordSoFar)

Then, start it with

printOutWords(ternaryTree, "")

I don't know how to decode your array, but if you can implement these operations, I think it's something like this.

Ok, here is some C# code that works based on a simple array representation. I used the tree from this wikipedia article

http://en.wikipedia.org/wiki/Ternary_search_tree

I represented it as an array where the root is element 0, and then its kids are 1, 2, 3. 1's kids are 4,5,6 and so on. '\0' is used to represent that there is no more kid. The algorithm is the same as above.

using System;
using System.Text;

namespace TreeDecode
{
    class Program
    {
        // http://en.wikipedia.org/wiki/Ternary_search_tree
        //The figure below shows a ternary search tree with the strings "as", "at", "cup", "cute", "he", "i" and "us":
        internal static char[] searchTree = {
                                                                               'c', 
                              'a',                                             'u',                                               'h', 
               '\0',          't',          '\0',            '\0',             't',           '\0',              '\0',            'e',            'u',
         '\0','\0','\0', 's','\0','\0','\0','\0','\0',  '\0','\0','\0',  'p','e','\0',   '\0','\0','\0',    '\0','\0','\0', '\0','\0','\0',   'i','s','\0',
        };

       static void printOutWords(char[] tree, int root, string wordSoFar) {
          if (!HasMiddle(tree, root))
              Console.WriteLine(wordSoFar + CharAt(tree, root));

          if (HasMiddle(tree, root))
              printOutWords(tree, MiddleKid(root), wordSoFar + CharAt(tree, root));
          if (HasLeft(tree, root))
              printOutWords(tree, LeftKid(root), wordSoFar);
          if (HasRight(tree, root))
              printOutWords(tree, RightKid(root), wordSoFar);

        }    

        private static int RightKid(int root)
        {
            return root * 3 + 3;            
        }

        private static bool HasRight(char[] tree, int root)
        {
            int rightIndex = RightKid(root);
            return (rightIndex < tree.Length && tree[rightIndex] != 0);
        }

        private static int LeftKid(int root)
        {
            return root * 3 + 1;
        }

        private static bool HasLeft(char[] tree, int root)
        {
            int leftIndex = LeftKid(root);
            return (leftIndex < tree.Length && tree[leftIndex] != 0);
        }

        private static int MiddleKid(int root)
        {
            return root * 3 + 2;
        }

        private static bool HasMiddle(char[] tree, int root)
        {
            int middleIndex = MiddleKid(root);
            return (middleIndex < tree.Length && tree[middleIndex] != 0);
        }

        private static int NumKids(char[] tree, int root)
        {
            return (HasMiddle(tree, root) ? 1 : 0) + (HasRight(tree, root) ? 1 : 0) + (HasLeft(tree, root) ? 1 : 0);
        }


        private static string CharAt(char[] tree, int root)
        {
            return new String(tree[root], 1);
        }


        static void Main(string[] args)
        {
            printOutWords(searchTree, 0, "");
        }
    }
}

This prints

cute
cup
at
as
he
us
i

Thanks for giving me a hand. So at least you're confirming what I thought was possible. Now I'll try to implement it. — Abel, Nov 15 '11 at 22:04
I put in a sample tree and some C# code to show how to do it. I didn't figure out how to read your array, but if you know that, this code should basically work. — Lou Franco, Nov 15 '11 at 22:53
given the information in @jwpat7's answer -- just reimplement HasLeft, LeftKid, etc. and it should work on your array as well. — Lou Franco, Nov 16 '11 at 00:56

score 2 · Answer 2 · answered Nov 15 '11 at 22:53

The data structure isn't precisely a ternary tree since the third branch is implicit (i.e., the next entry after current entry). It's sort of like a trie implemented within a binary tree structure. Each 4 numbers correspond to a struct like struct { char letter, Loff, Roff, flag}. For example, entry 0 = 72,5,77,0 is letter 'H', left offset 5, right offset 77, flag 0 (probably meaning not terminal). Following left offset, 5 entries after #0 we have 67,12,40,0 which is C, 12, 40, 0; 12 entries after #5, 65,0,0,0 is A,0,0,0. It and the next 5 entries (with 65,67,84,73,79,78) apparently correspond to string ACTION. Following right offset, 77 entries after #0 we have 78,8,48,0, 79,36,0,0, 83,30,55,0, 72,0,0,0, 65,... or N, O, and S entries with branches, followed by H, A, D, E entries with no explicit branches, to make NOSHADE.

As you follow the tree toward leaves, add letters to current string (as in traversing within a trie) and as you go back up (away from leaves) drop letters from end of current string.

Is it possible to generate all possible terms findable in a ternary search tree?

2 Answers2