int search(const char* some_word);

dword ternary_tree::insert(const char* s);
dword ternary_tree::search(const char* s);

size_t ternary_tree::partial_match_search(const char *s, array<dword>& result_set );
size_t ternary_tree::neighbour_search(const char *s, int d, array<dword>& result_set);

namespace tool 
{
  template <typename CHAR>
    class ternary_tree
  {
    typedef unsigned int node_index;

  public:
    enum constants 
    {
        any_one_char = '?'
    };

    ternary_tree(): max_no(0) {}

    // 
    // returns number [1..max uint] of inserted or existing item.
    // does no insertion if item already exists. 
    //
    dword insert(const CHAR *s)
    {
      return (dword)nodes[insert(0, s)].eqkid;
    }

    // returns n[1..max_no] or zero if not found
    dword search(const CHAR *s) const
    {   
      node_index nid = 0; // root index;
      while (nid < total_nodes()) 
      {
         const node& n = nodes[nid];
         if (*s < n.splitchar)
             nid = n.lokid;
         else if(*s > n.splitchar)
             nid = n.hikid;
         else //(*s == p->splitchar) 
         {
            if (*s++ == 0)
                return n.value();
            nid = n.eqkid;
         } 
      }
      return 0;
    }
    // partial match search
    // e.g. 
    size_t partial_match_search(const CHAR *s, array<dword>& result_set ) const
    {
      partial_match_search(0,s,result_set);
      return result_set.size();
    }

    //
    // neighbour search 
    //
    // 'd' is Hamming distance of a query word: 
    //      A measure of the difference between two strings, 
    //      expressed by the number of characters that need to be changed to 
    //      obtain one from the other. 
    //      E.g., 0101 and 0110 has a Hamming distance of two 
    //      whereas "Butter" and "ladder" are four characters apart.
    //
    size_t neighbour_search(const CHAR *s, int d, array<dword>& result_set) const
    {
      neighbour_search(0, s, result_set, d);
      return result_set.size();
    }

 protected:
    typedef unsigned int node_index;
    
    struct node 
    {
       CHAR       splitchar;
       node_index lokid, eqkid, hikid;
       node():splitchar(0), lokid(-1), eqkid(-1), hikid(-1){}
       dword value() const 
       {
         assert(splitchar == 0);
         return (dword) eqkid;
       }
       void value(dword v)  
       {
         assert(splitchar == 0);
         eqkid = (node_index)v;
       }
    };

    array<node> nodes;
    dword       max_no;

    size_t      total_nodes() const { return (dword) nodes.size(); }
    
    node_index  insert(node_index nid, const CHAR *s)
    { 
       if (nid >= total_nodes()) 
       {
            node n; n.splitchar = *s;
            nodes.push(n);
            nid = nodes.last_index(); 
       }
       const node& n = nodes[nid];
       if (*s < n.splitchar)
          nodes[nid].lokid = insert(n.lokid, s);
       else if(*s > n.splitchar)
          nodes[nid].hikid = insert(n.hikid, s);
       else //*s == p->splitchar 
       {
          if (*s == 0)
          //"...we'll exploit the fact that a node with a 
          // null splitchar cannot have an eqkid, 
          // and store the data in that field."
              nodes[nid].value(++max_no);
          else
              nodes[nid].eqkid = insert(n.eqkid, ++s);
       }
       return nid;
    }

    //partial match search
    void partial_match_search(node_index nid, const CHAR *s, array<dword>& result_set ) const 
    {    
         if (nid >= total_nodes()) 
           return;
         const node& n = nodes[nid];
         if (*s == any_one_char || *s < n.splitchar)
            partial_match_search(n.lokid, s, result_set);
         if (*s == any_one_char || *s == n.splitchar)
            if (n.splitchar && *s)
                partial_match_search(n.eqkid, s+1, result_set);
         if (*s == 0 && n.splitchar == 0)
                result_set.push( (dword) n.value());
         if (*s == any_one_char || *s > n.splitchar)
                partial_match_search(n.hikid, s, result_set);
    }

    static int  length(const CHAR* s)
    {
      const CHAR* ps = s; while(*s) ++s; return s - ps;
    }

    void neighbour_search(node_index nid, const CHAR *s, array<dword>& result_set, int d) const
    {   
        if (nid >= total_nodes() || d < 0) return;

        const node& n = nodes[nid];      

        if (d > 0 || *s < n.splitchar)
            neighbour_search(n.lokid, s, result_set, d);
        if (n.splitchar == 0) 
        {
           if ( length(s) <= d)
              result_set.push(n.value());
        } 
        else
           neighbour_search(n.eqkid, *s ? s+1:s, result_set, (*s == n.splitchar) ? d:d-1 );
        if (d > 0 || *s > n.splitchar)
           neighbour_search(n.hikid, s, result_set, d);
    }


  };

}

Замечания по имплементации:
1) Я использую свой array который может быть легко заменен на std::vector

Time Complexity

In a balanced ternary search tree with n nodes where all the keywords
of the nodes are k characters long, we want to search a k character long input string. The total number of character-to-character comparisons is at most

lg n + k.

For a balanced binary search tree of n-nodes and k character long keywords, the total number of character-to-character comparisons is at most

k * lg n

which is substantially larger than lg n + k for large n.

In what order should you insert the nodes into a tree? No matter in what order you insert the nodes, you end up with the same digital search trie -- the data structure is totally insensitive to insertion order.
Binary search trees are at the opposite end of the spectrum: If you insert the nodes in a good order (middle element first), you end up with a balanced tree. If you insert the nodes in sorted order, the result is a long skinny tree that is very costly to build and search. Fortunately, if you insert the nodes in random order, a binary search tree is usually close to balanced.

The input order of data cells into a ternary search trie is still important to create balanced tree, but less important than in a binary search tree.
According to many authors ([Mehlhorn79] and [Bentley and Saxe79]), by choosing the true median of a set of data-cells as the starting node, we can create a well-balanced ternary tree without the randomizing proces

CS>  int search(const char* some_word);
CS>

 node_index  insert(node_index nid, const CHAR *s)
    { 
       if (nid >= total_nodes()) 
       {
            node n; n.splitchar = *s;
            nodes.push(n);
            nid = nodes.last_index();        // здесь ошибка
         }

#include <vector>

typedef unsigned int dword;

namespace tool 
{
  template <typename CHAR>
    class ternary_tree
  {
    typedef unsigned int node_index;

  public:
    enum constants 
    {
        any_one_char = '?'
    };

    ternary_tree(): max_no(0) {}

    // 
    // returns number [1..max uint] of inserted or existing item.
    // does no insertion if item already exists. 
    //
    dword insert(const CHAR *s)
    {
      return (dword)nodes[insert(0, s)].eqkid;
    }

    // returns n[1..max_no] or zero if not found
    dword search(const CHAR *s) const
    {   
      node_index nid = 0; // root index;
      while (nid < total_nodes()) 
      {
         const node& n = nodes[nid];
         if (*s < n.splitchar)
             nid = n.lokid;
         else if(*s > n.splitchar)
             nid = n.hikid;
         else //(*s == p->splitchar) 
         {
            if (*s++ == 0)
                return n.value();
            nid = n.eqkid;
         } 
      }
      return 0;
    }
    // partial match search
    // e.g. 
    size_t partial_match_search(const CHAR *s, std::vector<dword>& result_set ) const
    {
      partial_match_search(0,s,result_set);
      return result_set.size();
    }

    //
    // neighbour search 
    //
    // 'd' is Hamming distance of a query word: 
    //      A measure of the difference between two strings, 
    //      expressed by the number of characters that need to be changed to 
    //      obtain one from the other. 
    //      E.g., 0101 and 0110 has a Hamming distance of two 
    //      whereas "Butter" and "ladder" are four characters apart.
    //
    size_t neighbour_search(const CHAR *s, int d, std::vector<dword>& result_set) const
    {
      neighbour_search(0, s, result_set, d);
      return result_set.size();
    }

 protected:
    typedef unsigned int node_index;
    
    struct node 
    {
       CHAR       splitchar;
       node_index lokid, eqkid, hikid;
       node():splitchar(0), lokid(-1), eqkid(-1), hikid(-1){}
       dword value() const 
       {
         //assert(splitchar == 0);
         return (dword) eqkid;
       }
       void value(dword v)  
       {
         //assert(splitchar == 0);
         eqkid = (node_index)v;
       }
    };

    std::vector<node> nodes;
    dword       max_no;

    size_t      total_nodes() const { return (dword) nodes.size(); }
    
    node_index  insert(node_index nid, const CHAR *s)
    { 
       if (nid >= total_nodes()) 
       {
            node n; n.splitchar = *s;
            nodes.push_back(n);
            nid = nodes.size() - 1; 
       }
       const node& n = nodes[nid];
       if (*s < n.splitchar)
          nodes[nid].lokid = insert(n.lokid, s);
       else if(*s > n.splitchar)
          nodes[nid].hikid = insert(n.hikid, s);
       else //*s == p->splitchar 
       {
          if (*s == 0)
          //"...we'll exploit the fact that a node with a 
          // null splitchar cannot have an eqkid, 
          // and store the data in that field."
              nodes[nid].value(++max_no);
          else
              nodes[nid].eqkid = insert(n.eqkid, ++s);
       }
       return nid;
    }

    //partial match search
    void partial_match_search(node_index nid, const CHAR *s, std::vector<dword>& result_set ) const 
    {    
         if (nid >= total_nodes()) 
           return;
         const node& n = nodes[nid];
         if (*s == any_one_char || *s < n.splitchar)
            partial_match_search(n.lokid, s, result_set);
         if (*s == any_one_char || *s == n.splitchar)
            if (n.splitchar && *s)
                partial_match_search(n.eqkid, s+1, result_set);
         if (*s == 0 && n.splitchar == 0)
                result_set.push_back( (dword) n.value());
         if (*s == any_one_char || *s > n.splitchar)
                partial_match_search(n.hikid, s, result_set);
    }

    static int  length(const CHAR* s)
    {
      const CHAR* ps = s; while(*s) ++s; return s - ps;
    }

    void neighbour_search(node_index nid, const CHAR *s, std::vector<dword>& result_set, int d) const
    {   
        if (nid >= total_nodes() || d < 0) return;

        const node& n = nodes[nid];      

        if (d > 0 || *s < n.splitchar)
            neighbour_search(n.lokid, s, result_set, d);
        if (n.splitchar == 0) 
        {
           if ( length(s) <= d)
              result_set.push_back(n.value());
        } 
        else
           neighbour_search(n.eqkid, *s ? s+1:s, result_set, (*s == n.splitchar) ? d:d-1 );
        if (d > 0 || *s > n.splitchar)
           neighbour_search(n.hikid, s, result_set, d);
    }


  };

}

uw>Вот тот же код, слегка переделанный под std::vector, вроде работает.

  vector<dword> resultSet;

    int i;
    tool::ternary_tree<char> TST;
    TST.insert("Andy");
    TST.insert("Andyx");
    i = TST.neighbour_search("Andy",1, resultSet); // здесь i = 2 как положено


    for(vector<dword>::iterator it = resultSet.begin(); it != resultSet.end(); it++)
        cout << *it << endl; //здесь что-то не то

А>Написание сбалансированного третичного дерева оставим студентам в качестве домашнего задания

#define MAXWORDS 250000
#define MAXCHARS 3000000
char space[MAXCHARS], *a[MAXWORDS];

void rinsall(char *a[], int n)
{   int m;
    if (n < 1) return;
    m = n/2;
    insert(a[m]);  // insert - ф-ция вставки
    rinsall(a, m);
    rinsall(a + m+1, n-m-1);
}

void main()
{
   char *s = space;
    int    n = 0
    a[0] = s;
    FILE *fp = fopen("file.txt");
     while ((i = getc(fp)) != EOF) 
    {    
        if (i == '\n')
        {
            *s++ = 0;
           a[++n] = s;
       }
        else
        *s++ = i;
    }
    rinsall(a, n);    
}

DG>> node_index  insert(node_index nid, const CHAR *s)
DG>>    { 
DG>>       if (nid >= total_nodes()) 
DG>>       {
DG>>            node n; n.splitchar = *s;
DG>>            nodes.push(n);
DG>>            nid = nodes.last_index();        // здесь ошибка
DG>>         }
DG>>

    tool::array<unsigned int> resultSet;
    TST.insert("andy");
    TST.neighbour_search("aldy",1,resultSet);
    cout << resultSet[0] << endl;

DG>Видимо, вместо const element& нужно int? Подправил — работает

inline const element&  last  () const;
  inline int last_index () const
  {
    return _size - 1;
  }

class lookup {

   ternary_tree<char> index;
   vector<string>     values; 

   void insert(const char* s)
   {
     int i = index.insert(s) - 1;
     if(i >= values.size()) 
     {
       assert(i == values.size()); 
       values.push_back(s);
     }
   }
   string get_value_by_id(int idx) const { return (idx > 0)? values[idx-1] : "{unknown}"; }
};

//-------------------------------------------------
#include <vector>
#include <cassert>
//------------------------------------------------
namespace tool 
{
    typedef unsigned int dword;

    template <typename CHAR>
    class ternary_tree
    {
        typedef unsigned int node_index;
    public:
        ternary_tree(): max_no(0) {}

        dword insert(const CHAR *s)
        {
            return (dword)nodes[insert(0, s)].eqkid;
        }

        // returns n[1..max_no] or zero if not found
        dword search(const CHAR *s) const
        {   
            node_index nid = 0; // root index;
            while (nid < total_nodes()) 
            {
                const node& n = nodes[nid];
                if (*s < n.splitchar)
                    nid = n.lokid;
                else if(*s > n.splitchar)
                    nid = n.hikid;
                else //(*s == p->splitchar) 
                {
                    if (*s++ == 0)
                        return n.value();
                    nid = n.eqkid;
                } 
            }
            return 0;
        }

    protected: 
        struct node 
        {
            CHAR       splitchar;
            node_index lokid;
            node_index eqkid;
            node_index hikid;

            node() : splitchar(0), lokid(-1), eqkid(-1), hikid(-1) {}

            dword value() const 
            {
                assert(splitchar == 0);
                return (dword)eqkid;
            }
            void value(dword v)  
            {
                assert(splitchar == 0);
                eqkid = (node_index)v;
            }
        };

        std::vector<node> nodes;
        dword             max_no;

        size_t     total_nodes() const { return nodes.size(); }

        node_index insert(node_index nid, const CHAR *s)
        { 
            if (nid >= total_nodes()) 
            {
                node n; n.splitchar = *s;
                nodes.push_back(n);
                nid = nodes.size() - 1; 
            }
            const node& n = nodes[nid];
            if (*s < n.splitchar)
                nodes[nid].lokid = insert(n.lokid, s);
            else if(*s > n.splitchar)
                nodes[nid].hikid = insert(n.hikid, s);
            else //*s == p->splitchar 
            {
                if (*s == 0)
                //"...we'll exploit the fact that a node with a 
                // null splitchar cannot have an eqkid, 
                // and store the data in that field."
                    nodes[nid].value(++max_no);
                else
                    nodes[nid].eqkid = insert(n.eqkid, ++s);
            }
            return nid;
         }

        static int length(const CHAR* s)
        {
            const CHAR* ps = s; while(*s) ++s; return s - ps;
        }
    };
}

int main()
{
    tool::ternary_tree<char> ttree;

    ttree.insert("accent-height");
    ttree.insert("accumulate");
    ttree.insert("alignment-baseline");
    ttree.insert("alphabetic");
    ttree.insert("amplitude");
    ttree.insert("animate");
    ttree.insert("arabic-form");
    ttree.insert("ascent");
    ttree.insert("attributeType");
    ttree.insert("azimuth");
    ttree.insert("baseFrequency");
    ttree.insert("baseProfile");
    ttree.insert("baseline-shift");
    ttree.insert("bbox");
    ttree.insert("bias");
    ttree.insert("by");
    ttree.insert("calcMode");
    ttree.insert("cap-height");
    ttree.insert("class");
    ttree.insert("clip");
    ttree.insert("clip-path");
    ttree.insert("clip-rule");
    ttree.insert("clipPathUnits");
    ttree.insert("color");
    ttree.insert("color-interpolation");
    ttree.insert("color-interpolation-filters");
    ttree.insert("color-profile");
    ttree.insert("color-rendering");
    ttree.insert("contentScriptType");
    ttree.insert("contentStyleType");
    ttree.insert("cursor");
    ttree.insert("cx");
    ttree.insert("cy");
    ttree.insert("d");
    ttree.insert("descent");
    ttree.insert("diffuseConstant");
    ttree.insert("direction");
    ttree.insert("display");
    ttree.insert("divisor");
    ttree.insert("dominant-baseline");
    ttree.insert("dur");
    ttree.insert("dx");
    ttree.insert("dy");
    ttree.insert("edgeMode");
    ttree.insert("elevation");
    ttree.insert("enable-background");
    ttree.insert("end");
    ttree.insert("exponent");
    ttree.insert("externalResourcesRequired");
    ttree.insert("feColorMatrix");
    ttree.insert("feComposite");
    ttree.insert("feGaussianBlur");
    ttree.insert("feMorphology");
    ttree.insert("feTile");
    ttree.insert("fill");
    ttree.insert("fill-opacity");
    ttree.insert("fill-rule");
    ttree.insert("filter");
    ttree.insert("filterRes");
    ttree.insert("filterUnits");
    ttree.insert("flood-color");
    ttree.insert("flood-opacity");
    ttree.insert("font-family");
    ttree.insert("font-size");
    ttree.insert("font-size-adjust");
    ttree.insert("font-stretch");
    ttree.insert("font-style");
    ttree.insert("font-variant");
    ttree.insert("font-weight");
    ttree.insert("format");
    ttree.insert("from");
    ttree.insert("fx");
    ttree.insert("fy");
    ttree.insert("g1");
    ttree.insert("glyph-name");
    ttree.insert("glyph-orientation-horizontal");
    ttree.insert("glyph-orientation-vertical");
    ttree.insert("glyphRef");
    ttree.insert("gradientTransform");
    ttree.insert("gradientUnits");
    ttree.insert("hanging");
    ttree.insert("height");
    ttree.insert("horiz-adv-x");
    ttree.insert("horiz-origin-y");
    ttree.insert("id");
    ttree.insert("ideographic");
    ttree.insert("image-rendering");
    ttree.insert("in");
    ttree.insert("in2");
    ttree.insert("intercept");
    ttree.insert("k");
    ttree.insert("k1");
    ttree.insert("k2");
    ttree.insert("k3");
    ttree.insert("k4");
    ttree.insert("kernelMatrix");
    ttree.insert("kernelUnitLength");
    ttree.insert("kerning");
    ttree.insert("keyPoints");
    ttree.insert("keySplines");
    ttree.insert("keyTimes");
    ttree.insert("lang");
    ttree.insert("lengthAdjust");
    ttree.insert("letter-spacing");
    ttree.insert("lighting-color");
    ttree.insert("limitingConeAngle");
    ttree.insert("local");
    ttree.insert("marker");
    ttree.insert("marker-end");
    ttree.insert("marker-mid");
    ttree.insert("marker-start");
    ttree.insert("markerHeight");
    ttree.insert("markerUnits");
    ttree.insert("markerWidth");
    ttree.insert("mask");
    ttree.insert("maskContentUnits");
    ttree.insert("maskUnits");
    ttree.insert("mathematical");
    ttree.insert("max");
    ttree.insert("media");
    ttree.insert("method");
    ttree.insert("min");
    ttree.insert("mode");
    ttree.insert("name");
    ttree.insert("numOctaves");
    ttree.insert("offset");
    ttree.insert("opacity");
    ttree.insert("operator");
    ttree.insert("order");
    ttree.insert("orient");
    ttree.insert("orientation");
    ttree.insert("origin");
    ttree.insert("overflow");
    ttree.insert("overline-position");
    ttree.insert("overline-thickness");
    ttree.insert("panose-1");
    ttree.insert("path");
    ttree.insert("pathLength");
    ttree.insert("patternContentUnits");
    ttree.insert("patternTransform");
    ttree.insert("patternUnits");
    ttree.insert("pointer-events");
    ttree.insert("points");
    ttree.insert("pointsAtX");
    ttree.insert("pointsAtY");
    ttree.insert("pointsAtZ");
    ttree.insert("preserveAlpha");
    ttree.insert("preserveAspectRatio");
    ttree.insert("primitiveUnits");
    ttree.insert("r");
    ttree.insert("radius");
    ttree.insert("refX");
    ttree.insert("refY");
    ttree.insert("rendering-intent");
    ttree.insert("repeatCount");
    ttree.insert("repeatDur");
    ttree.insert("requiredExtensions");
    ttree.insert("restart");
    ttree.insert("result");
    ttree.insert("rotate");
    ttree.insert("rx");
    ttree.insert("ry");
    ttree.insert("scale");
    ttree.insert("seed");
    ttree.insert("shape-rendering");
    ttree.insert("slope");
    ttree.insert("spacing");
    ttree.insert("specularConstant");
    ttree.insert("specularExponent");
    ttree.insert("spreadMethod");
    ttree.insert("startOffset");
    ttree.insert("stdDeviation");
    ttree.insert("stemh");
    ttree.insert("stemv");
    ttree.insert("stitchTiles");
    ttree.insert("stop-color");
    ttree.insert("stop-opacity");
    ttree.insert("strikethrough-position");
    ttree.insert("strikethrough-thickness");
    ttree.insert("stroke");
    ttree.insert("stroke-dasharray");
    ttree.insert("stroke-dashoffset");
    ttree.insert("stroke-linecap");
    ttree.insert("stroke-linejoin");
    ttree.insert("stroke-miterlimit");
    ttree.insert("stroke-opacity");
    ttree.insert("stroke-width");
    ttree.insert("style");
    ttree.insert("surfaceScale");
    ttree.insert("systemLanguage");
    ttree.insert("tableValues");
    ttree.insert("target");
    ttree.insert("targetX");
    ttree.insert("targetY");
    ttree.insert("text-anchor");
    ttree.insert("text-decoration");
    ttree.insert("text-rendering");
    ttree.insert("textLength");
    ttree.insert("title");
    ttree.insert("to");
    ttree.insert("transform");
    ttree.insert("type");
    ttree.insert("u1");
    ttree.insert("u2");
    ttree.insert("underline-position");
    ttree.insert("underline-thickness");
}

nodes[nid].hikid = insert(n.hikid, s);

 node_index i = insert(n.lokid, s);
 nodes[nid].lokid = i;