[알고리즘] 트라이

트라이

문자열을 효율적으로 저장하고 탐색하기 위해 만들어진 트리 형태의 자료구조.

 

- 문자열의 한 글자 한 글자가 트리의 노드가 됨. Root 노드는 비어 있고 자식 노드를 따라 내려가면서 단어가 완성되는 구조이다.

예를 들어 문자 APPLE, APPLY, BANANA, BAN을 저장한다고 생각해 보자.

일반적으로는 APPLE, APPLY... 각각 따로 저장할 텐데,

하지만 트라이는 공통 접두사를 공유함.

위 이미지에서 보면 APPLE와 APPLY에서 공통 접두사는 "APPL"까지임. 따라서 이제 이 공통되는 부분은 한 번만 저장하면 됨.

이런 접두사를 이용하는 문제에서 매우 쓸모 있는 자료구조.

 

- 자동완성 및 검색어 추천

- 사전

- 접두사 검색

....

시간 복잡도

문자열 S에 대해 ⇒ 삽입 / 탐색 / 삭제 → O(S)

 

트라이는 문자열의 길이만큼만 노드를 따라가서 찾으면 되므로 탐색과 삽입 모두 O(S)의 시간 복잡도를 가짐. 

 

구현 방법

 

기본으로 사용할 자료구조

using namespace std;
const int ROOT = 1; // 정점의 번호
int unused = 2;// 아직 사용되지 않은 정점의 번호 -> 즉 문자가 추가 될때 마다
// unused 를 ++시키면서 현재의 위치를 갱신함.
const int MX = 10000 * 500 + 5;// 최대 등장 가능한 글자의 수
bool chk[MX]; // 해당 정점이 문자열의 끝인지를 확인하는 배열
int nxt[MX][26]; // 각 정점에서 자식 정점의 번호 또한 알파벳 소문자로 26개
int c2i(char c)
{
    return c - 'A';
    //대문자 기준으로 작성
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for (int i = 0; i < MX; i++)
    {
        fill(nxt[i], nxt[i] + 26, -1); // 돌아 다니다가 -1만나면 자식 정점 존재 x라는 뜻 
    }
}

 

ROOT

 트라이의 시작 정점 번호. 항상 트라이에서 시작할 때는 루트부터 시작함.

 

unused

아직 사용하지 않은 정점 중에서 가장 작은 정점 번호. 즉 새 노드를 만든 다면 이 변수를 증가시키면서 갱신

 

bool chk [MX] 배열

각 정점이 하나의 완전한 문자열의 마지막 즉 끝 노드인지 표시하는 배열

예를 들어 BAN과 BANANA를 보면

​두 문자 모두 하나의 문자열이다. 이에 BAN과 BANANA를 구분하기 위해서

BAN의 마지막 N -> TRUE

BANANA의 마지막 A -> TRUE

로 표시를 해두어 두 문자열을 구분합니다.

 

int nxt[MX][26] 배열

nxt[현재 정점][각 알파벳의 문자 인덱스]를 의미. 해당 문자로 이동했을 때 나오는 자식의 정점 번호가 저장됨.

 

nxt [5][4] ⇒ 6 (E)

nxt [5][24] ⇒ 7 (Y)

nxt [5][나머지] ⇒ -1 (아무 문자 사용 X)

이렇게 각 다음 자식 노드의 문자를 알파벳 인덱스로 구분할 수 있음.

 

Insert 문자열 삽입 함수

void insert(string& s)
{  
	int cur = ROOT;//현재 보고 있는 정점
	for(int i=0;i<s.size();i++)
	 {
		 if(nxt[cur][c2i(s[i])]==-1)
		 {
			 nxt[cur][c2i(s[i])]=unused++;
		 }
		 cur =nxt[cur][c2i(s[i])];
	 }
	 chk[cur] =true;//그다음 이제 끝처리를 true로 함. 맨 마지막 단어확인
}

 

1. 루트에서 시작 (ROOT =1)

2. 문자열을 한 글자씩 확인.

3. 현재 문자에 해당하는 자식이 없으면 새 노드를 생성 if(nxt [cur][c2i(s [i])]==-1)

4. 해당 자식 노드로 이동.

5. 마지막 문자까지 이동한 뒤 chk를 true로 설정함.

 

Find 함수

bool find(string& s)
{
	int cur =ROOT;
	
	for(int i=0;i<s.size();i++) // 자식 정점으로 계속 이동
	{
		if(nxt[cur][c2i(s[i])]==-1) return false;
		// 존재 하지 않는 자식 점점을 만나면 바로 false 반환
		cur = nxt[cur][c2i(s[i])];
	}
	return chk[cur];// 마지막 정점에 도달되는 경우는 chk 리턴
}

 

1. 루트 노드에서 시작

2. 문자열을 한 글자씩 확인

3. 현재 문자에 해당하는 자식 노드가 없으면 해당 문자열은 존재하지 않으므로 false반환

4. 자식 노드가 존재하면 해당 노드로 이동시킴

5. 문자열의 마지막 문자까지 이동한 뒤 현재 노드가 실제 문자열의 끝인지 확인함.

경로가 중간에 끊기면 false이고 끝까지 도착하더라도 chk [cur]이 true여야지 해당 문자열이 실제로 저장되어 있다고 판단함. 

 

 

void erase (string& s)
{
	int cur=ROOT;
	for(int i=0;i<s.size();i++)
	{
		if(nxt[cur][c2i(s[i])]==-1) return;
		//반드시 트라이에 존재하는 문자열에 대해서만 erase할때에는 위에 삭제
		cur = nxt[cur][c2i(s[i])];
	}
	chk[cur]=false;
}

 

1. 루트에서 시작

2. 문자열을 한 글자씩 확인.

3. 현재 문자에 해당하는 자식 노드가 없으면 삭제할 문자열이 존재하지 않다는 것이므로 함수 종료

4. 자식 노드 존재하면 해당 노드로 이동

5. 마지막 노드까지 이동한 뒤 문자열의 끝 표시를 제거함.

 

 

트라이 사용 문제

Design Add and Search Words Data Structure - LeetCode

/*
트라이 사용한 문자열 탐색
*/
class WordDictionary {
public:
static const int root=1;// 정점의 번호
static const int max=250005;
int unused=2;// 아직 사용되지 않은 정점의 번호
//문자가 추가될 때 마다 시작 될 위치
bool chk[max];
int nxt[max][28];//각 정점에서의 문자들
    WordDictionary() {
    memset(chk,false,sizeof(chk));
    memset(nxt,-1,sizeof(nxt));
    }
    
    int func(char c)//문자를 int형으로 바꿔주는 함수
    {
        return c-'a';
    }
    void addWord(string word) {
        int cur=root;//1번 정점 부터
        for(int i=0;i<word.size();i++)//삽입 될 문자의 길이 만큼 동작해줌
        {
            char curWord=word[i];
            if(nxt[cur][func(curWord)]==-1)//자식 정점이 없을때
            {
                nxt[cur][func(curWord)]=unused++;
                // 새로운 정점번호 unused를 자식 정점으로 부여
            }
            cur=nxt[cur][func(curWord)];//다음 위치로 이동
        }
        chk[cur]=true;
    }
    
    bool search(string word) {
        int cur=root;
        
        if(word.find('.')==string::npos)// . 없을때는 걍 일반적인 트라이 탐색 사용.
        {
             for(int i=0;i<word.size();i++)
            {
                char curWord=word[i];
                if(nxt[cur][func(curWord)]==-1) return false;
                cur=nxt[cur][func(curWord)];
            }
        }
        else
        {
           return dfs(root,0,word);//만일 .이 있을때는모든 경로를 탐색함
        }
        return chk[cur];
    }
    bool dfs(int node, int idx,string& word)
    {
        if(idx==word.size()) // 문자 끝까지 도달했으면 단어 종료 여부 확인함
        {
            return chk[node];
        }
        if(word[idx]=='.')// 이제 . 을만나면 모든 경우의 수를 확인해봐야함.
        {
            for(int i=0;i<26;i++)
            {
                if(nxt[node][i]!=-1)// 자식있는 곳(문자 있는지)만 탐색
                {
                    if(dfs(nxt[node][i],idx+1,word))
                    //여러 경로중 하나라도 성공하면 true 
                    {
                        return true;
                    }
                }
            }
            return false;
        }
        //일반 적인 경로로 탐색하는 경우  -> . 없을때는 일반적으로 dfs탐색ㄱㄱ
        int c=func(word[idx]);
        if(nxt[node][c]==-1) return false;
        return dfs(nxt[node][c],idx+1,word);
    }
};

 

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다.