Dr. Dobb's Journal June 1998

A Real Program

Robert Sedgewick and I described ternary search trees in the April 1998 issue of DDJ. When we worked on the data structure, we were both pleasantly surprised to find that a recursive search function was as fast as an iterative function (under optimizing compilers). The run times for the two functions are shown in the first two rows of Table 3. We therefore assumed that our other recursive search functions were competitive with the iterative versions. After performing the experiments in this article, I decided to go back and test the assumption.

The pmsearch function in (Listing Two) performs a partial-match search in a tree. The query can include dots as "don't care" characters, so ".at" matches bat, cat, and a dozen other three-letter words. pmsearch calls itself in three distinct places, and returns to do more work after two of those calls.

The function pmsearch2 is in Listing Three. It is almost twice as long as function pmsearch, but only a bit harder to understand. The new code has two primary blocks, depending on whether the current character is a dot. Both of the cases ended with a tail recursion, so I explicitly transformed that to a while loop. The speedups ranged from a third to a factor of three, which I felt was worth a dozen lines of code and a couple hours of programming. I took a similar approach to a function for near-neighbor searching in ternary search trees, with similar results in code length and run time. The code for these experiments is available electronically; see "Resource Center," page 3.

-- J.B.

Back to Main Article

  void pmsearch(Tptr p, char *s)
  {   if (!p) return;
      nodecnt++;
      if (*s == '.' || *s < p->splitchar)
          pmsearch(p->lokid, s);
      if (*s == '.' || *s == p->splitchar)
          if (p->splitchar && *s)
              pmsearch(p->eqkid, s+1);
      if (*s == 0 && p->splitchar == 0)
          srcharr[srchtop++] =
              (char *) p->eqkid;
      if (*s == '.' || *s > p->splitchar)
          pmsearch(p->hikid, s);
  }

Back to Text

 void pmsearch2(Tptr p, char *s)
 {   while (p) {
         nodecnt++;
         if (*s == '.') {
             pmsearch2(p->lokid, s);
             pmsearch2(p->hikid, s);
             if (p->splitchar == 0) return;
             p = p->eqkid;
             ++s;
         } else {
             if (*s < p->splitchar)
                 p = p->lokid;
             else if (*s > p->splitchar)
                 p = p->hikid;
             else /* *s == p->splitchar */ {
                 if (*s == 0) {
                     if (p->splitchar == 0)
                         srcharr[srchtop++] =
                             (char *) p->eqkid;
                     return;
                 }
                 p = p->eqkid;
                 ++s;
             }
         }
     }
 }

Back to Text