tstree.c

多重搜索树算法

#include "tstree.h"
#include <stdlib.h>

/*******************  Membership Searching ***************/
/*
 * a recursive version of the search function. 
 * It returns 1 if string s is in the subtree rooted at p, 
 * and 0 otherwise; 
 * it is originally called as rsearch(root, s):
 */

int rsearchTST(TSTptr p, char *s)
{   
	if (!p) return 0; 
	if (*s < p->splitchar) 
		return rsearchTST(p->lokid, s); 
	else if (*s > p->splitchar) 
		return rsearchTST(p->hikid, s); 
	else { 
		if (*s == 0) return 1; 
		return rsearchTST(p->eqkid, ++s); 
	} 
}

/*
 * a iterative version of the search function. 
 * It returns 1 if string s is in the subtree rooted at p, 
 * and 0 otherwise; 
 * it is originally called as rsearch(root, s):
 */
int searchTST(TSTptr p,char *s) 
{    
    while (p) { 
       if (*s < p->splitchar) 
           p = p->lokid; 
       else if (*s == p->splitchar) { 
          if (*s++ == 0) 
              return 1; 
          p = p->eqkid; 
      } else 
          p = p->hikid; 
    } 
    return 0;
}

/*
 * another recursive version of the search function. 
 * It returns 1 if string s is in the subtree rooted at p, 
 * and 0 otherwise; 
 * it is originally called as rsearch(root, s):
 */
int rsearchTST2(TSTptr p, char *s) 
{ 
	return (!p ? 0 : ( 
        *s == p->splitchar 
		? (*s ? rsearchTST2(p->eqkid, ++s) : 1) 
		: (rsearchTST2(*s < p->splitchar ? 
		p->lokid : p->hikid, s)) 
		)); 
}

/******************* Inserting a New String **********************
 * The insert function inserts a new string into the tree, 
 * and does nothing if it is already present.
 * We insert the string s with the code root = insert(root, s);. 
 * The first if statement detects running off the end of new node,
 * initializes it, and falls through to the standard case. 
 * Subsequent code takes the appropriate branch, 
 * but branches to eqkid only if characters remain in the string. 
 *
 
 * The resulting tree stores the strings themselves, 
 * but no other information. 
 * Real symbol tables store additional data with each string.
 * To illustrate this problem, 
 * we'll store a pointer to every string in the tree; 
 * this data will be used by later search algorithms. 
 * We could add a new info field to each node, 
 * but that would be wasteful. 
 * Instead, we'll exploit the fact that a node with a null splitchar cannot have an eqkid,
 * and store the data in that field. 
 * We could make a union that contains the two possible pointers,
 * but that would be syntactically clumsy --
 * (we would have to refer to the union at each reference). 
 * We will instead use the sleazy hack of coercing a string into a Tptr. 
 * The code inside *s == p->splitchar test, therefore, becomes the following:

		if (*s == 0) 
			p->eqkid = (Tptr) insertstr; 
		else 
			p->eqkid = insert(p->eqkid, ++s);
 */


TSTptr insertTST(TSTptr p, char *s)
{ 
	if (p == 0) { 
		p = (TSTptr) malloc(sizeof(TSTnode)); 
		p->splitchar = *s; 
		p->lokid = p->eqkid = p->hikid = 0; 
	} 
	if (*s < p->splitchar) 
		p->lokid = insertTST(p->lokid, s); 
	else if (*s == p->splitchar) { 
		if (*s != 0) 
			p->eqkid = insertTST(p->eqkid, ++s); 
	} else 
		p->hikid = insertTST(p->hikid, s); 
	return p; 
}

/******************* Faster Insertion Functions *******************