트 리 트 리사전 트 리(문자열 정렬)안내 및 구현

1.종합 서술
단어 찾기 트 리,트 리 라 고도 부 르 며 나무 구조 로 해시 나무의 변종 이다.전형 적 인 응용 프로그램 은 대량의 문자열 을 통계,정렬,저장 하 는 데 사용 되 기 때문에 검색엔진 시스템 에서 텍스트 주파수 통계 에 자주 사용 된다.문자열 의 공공 접 두 사 를 이용 하여 저장 공간 을 절약 하고 불필요 한 문자열 비 교 를 최대한 줄 이 며 조회 효율 이 해시 표 보다 높다 는 것 이 장점 이다.
트 리 구조의 장점 은 다음 과 같다.1)하위 노드 의 수량 을 제한 하지 않 는 다.2)사용자 정의 입력 직렬 화 는 구체 적 인 언어,응용의 제한 을 돌파 하여 통용 되 는 프레임 워 크 가 된다.3)최대 Tokens 시퀀스 길이 의 제한 을 할 수 있 습 니 다.4)정 해진 한도 값 에 따라 중 복 된 문자열 을 출력 합 니 다.5)단일 문자열 의 주파수 찾기 기능 을 제공 합 니 다.6)속도 가 빨 라 1998 년 1 월 인민 일보(19056 행)의 중복 문자열 추출 작업 을 2 분 안에 완성 한다.
2.성질
그것 은 세 가지 기본 적 인 성질 이 있다.1)     루트 노드 는 문 자 를 포함 하지 않 습 니 다.루트 노드 를 제외 한 모든 노드 는 하나의 문자 만 포함 합 니 다.2)     루트 노드 에서 특정한 노드 까지 경로 에 있 는 문 자 를 연결 하여 이 노드 에 대응 하 는 문자열 입 니 다.3)     각 노드 의 모든 하위 노드 에 포 함 된 문 자 는 같 지 않다.
3.기본 조작
그 기본 적 인 작업 은 찾기,삽입,삭제 입 니 다.물론 삭제 작업 은 드 물 습 니 다.저 는 여기 서 전체 트 리 에 대한 삭제 작업 만 실 현 했 을 뿐 하나의 워드 삭제 작업 도 간단 합 니 다.
4.실현 방법
사전 항목 을 검색 하 는 방법 은 다음 과 같 습 니 다.(1)루트 노드 에서 검색 을 시작 합 니 다.(2)키 워드 를 찾 을 첫 번 째 자 모 를 얻 고 이 자모 에 따라 해당 하 는 하위 트 리 를 선택 하여 이 하위 트 리 로 이동 하여 계속 검색 합 니 다.(3)해당 하위 트 리 에서 키 워드 를 찾 을 두 번 째 자 모 를 얻 고 해당 하 는 하위 트 리 를 선택 하여 검색 합 니 다.(4)교체 과정...(5)특정한 노드 에서 키워드 의 모든 자 모 를 꺼 내 면 이 노드 에 붙 어 있 는 정 보 를 읽 고 검색 을 완성 합 니 다.기타 조작 유사 처리 5.Trie 원리-Trie 의 핵심 사상 은 공간 교환 시간 이다.문자열 의 공공 접 두 사 를 이용 하여 조회 시간의 비용 을 낮 추어 효율 을 높이 는 목적 을 달성 하 다.6.코드 구현

const int branchNum = 26; //    
int i;

struct Trie_node
{
       boolisStr;                //           。
       Trie_node*next[branchNum];//         ,  0-25  26  
       Trie_node():isStr(false)
       {
              memset(next,NULL,sizeof(next));
       }
};

class Trie
{
 public:
     Trie();
     voidinsert(const char* word);
     boolsearch(char* word);
     voiddeleteTrie(Trie_node *root);
       // voidprintTrie(Trie_node *root);   //new add

private:
    Trie_node* root;
 };

Trie::Trie()
{
     root =new Trie_node();
}

void Trie::insert(const char* word)
 {
    Trie_node*location = root;
   while(*word)
     {
       if(location->next[*word-'a'] == NULL)//      
         {
           Trie_node *tmp = new Trie_node();
           location->next[*word-'a'] = tmp;
        }   
       location = location->next[*word-'a']; //     ，          ，       
       word++;
    }
   location->isStr = true; //    ,     
 }

bool Trie::search(char *word)
{
       Trie_node*location = root;
       while(*word&& location)
       {
              location= location->next[*word-'a'];
              word++;
       }
       return(location!=NULL && location->isStr);
 }

void Trie::deleteTrie(Trie_node *root)
{
       for(i =0; i < branchNum; i++)
       {
              if(root->next[i]!= NULL)
              {
                     deleteTrie(root->next[i]);
              }
       }
       deleteroot;
}

void main() //    
{
       Trie t;
       t.insert("a");        
       t.insert("abandon");

       char * c= "abandoned";
       t.insert(c);
       t.insert("abashed");

       if(t.search("abashed"))
       {
          printf("true
");  //     
       }
}

때때로 우 리 는 문자열 에 대한 정렬 을 만 날 수 있 습 니 다.전형 적 인 정렬 알고리즘 을 사용 하면 시간 복잡 도 는 보통 O(n*lgn)이지 만 Trie 트 리 를 사용 하면 시간 복잡 도 는 O(n)에 불과 합 니 다.트 리 는 또 이름 전 트 리 로 글자 의 의미 에서 이해 할 수 있다.이 트 리 의 구 조 는 영문 사전 처럼 인접 한 단어 들 은 일반적으로 접두사 가 같 고 시간 복잡 도가 낮은 이 유 는 공간 으로 시간 을 바 꾸 는 전략 을 사 용 했 기 때문이다.아래 그림 은 문자열 을 정렬 하 는 Trie 트 리 입 니 다.모든 문자열 을 trie 트 리 에 삽입 하고 특정한 끝 노드 에 도착 할 때 이 노드 에 표 시 를 합 니 다.예 를 들 어'afb'를 삽입 하면 첫 번 째 자 모 는 a 이 고 a 를 따라 내 려 간 다음 에 두 번 째 자 모 는 f 입 니 다.f 를 따라 내 려 가 고 세 번 째 는 b 입 니 다.b 를 따라 내 려 갑 니 다.문자열 의 마지막 문자 가'\0'이기 때문에 끝나 고 더 이상 내 려 가지 않 습 니 다.그 다음 에 이 노드 에 afb.count+를 표시 합 니 다.즉,개수 가 1 증가 한 후에 이 나 무 를 앞 순 으로 옮 겨 다 니 면 문자열 이 작은 순서 에서 큰 순 서 를 얻 을 수 있 습 니 다.실현 코드 는 다음 과 같다(g+,VC++모두 컴 파일 통과).

#include <iostream>
#include <string.h>
using namespace std;
#define NUM 26
class Node
{
public:
    int count; //         
    Node* char_arr[NUM];  //  
    char* current_str;   //                     
    Node();
};
class Trie
{
public:
    Node* root;
    Trie();
    void insert(char* str);
    void output(Node* &node, char** str, int& count);
};
//     delete    
int main()
{
    char** str = new char*[12];
    str[0] = "zbdfasd";
    str[1] = "zbcfd";
    str[2] = "zbcdfdasfasf";
    str[3] = "abcdaf";
    str[4] = "defdasfa";
    str[5] = "fedfasfd";
    str[6] = "dfdfsa";
    str[7] = "dadfd";
    str[8] = "dfdfasf";
    str[9] = "abcfdfa";
    str[10] = "fbcdfd";
    str[11] = "abcdaf";
    //  trie 
    Trie* trie = new Trie();
    for(int i = 0; i < 12; i++)
        trie->insert(str[i]);
    int count = 0;
    trie->output(trie->root, str, count);
    for(int i = 0; i < 12; i++)
        cout<<str[i]<<endl;
    return 0;
}
Node::Node()
{
    count = 0;
    for(int i = 0; i < NUM; i++)
        char_arr[i] = NULL;
    current_str = new char[100];
    current_str[0] = '\0';
}
Trie::Trie()
{
    root = new Node();
}
void Trie::insert(char* str)
{
    int i = 0;
    Node* parent = root;
    // str[i]   trie  
    while(str[i] != '\0')
    {
        //    str[i]     ，      
        if(parent->char_arr[str[i] - 'a'] == NULL)
        {
            parent->char_arr[str[i] - 'a'] = new Node();
            //                     
            strcat(parent->char_arr[str[i] - 'a']->current_str, parent->current_str);
            char str_tmp[2];
            str_tmp[0] = str[i];
            str_tmp[1] = '\0';
            // str[i]            
            strcat(parent->char_arr[str[i] - 'a']->current_str, str_tmp);
            parent = parent->char_arr[str[i] - 'a'];
        }
        else
        {
            parent = parent->char_arr[str[i] - 'a'];
        }
        i++;
    }
    parent->count++;
}
//      
void Trie::output(Node* &node, char** str, int& count)
{
    if(node != NULL)
    {
        if(node->count != 0)
        {
            for(int i = 0; i < node->count; i++)
                str[count++] = node->current_str;
        }
        for(int i = 0; i < NUM; i++)
        {
            output(node->char_arr[i], str, count);
        }
    }
}