자료구조 Trie

Trie는 문자열을 효율적으로 저장하기위해 만든 자료구조이다.
이진탐색트리 구조에서는 문자열을 탐색하기위한 시간 O(logn)에 글자수(m)을 곱해서 총 O(mlogn)만큼의 시간이 든다.

이러한 단점을 보완하기 위해서 Trie에서는 아래 그림처럼 각 노드에 하나의 문자를 저장하게된다.
이렇게 하면 문자열을 찾을 때 까지 총 O(m)만큼의 시간이 들게 된다.
또, trie는 이진트리가 아닌 다진트리이다. 따라서 한 노드에서 여러 방향으로 가지치기를 할 수 있다.

Insert

문자열을 삽입할 때에는 다음과 같은 과정을 거친다.

1. 문자열을 삽입할 때에는 문자열에 첫번째 문자에 화살표를 지정하고,
2. 노드를 내려갈 때 마다 화살표를 한칸씩 다음문자로 이동시켜준다.
3. 현재 위치에 화살표가 가리키는 문자가 있다면 바로 그 문자가 가리키는 노드로 이동을 해준다.
4. 현재 위치에 화살표가 가리키는 문자가 없다면 새로 문자를 할당해주고
5. 화살표가 문자열의 끝까지 이동했다면 문자열의 끝이라는 '*'문자를 할당해주고 끝낸다.
   

1. 문자열을 삽입할 때에는 문자열에 첫번째 문자에 화살표를 지정하고,

2. 노드를 내려갈 때 마다 화살표를 한칸씩 다음문자로 이동시켜준다.

3. 현재 위치에 화살표가 가리키는 문자가 있다면 바로 그 문자가 가리키는 노드로 이동을 해준다.

4. 현재 위치에 화살표가 가리키는 문자가 없다면 새로 문자를 할당해주고 그 문자가 가리키는 노드로 이동해준다.

5. 화살표가 문자열의 끝까지 이동했다면 문자열의 끝이라는 '*'문자를 할당해주고 끝낸다.

Search

문자열을 탐색할 때에는 다음과 같은 과정을 거친다.

1. 삽입때와 마찬가지로 해당위치에 화살표가 가리키는 문자가 있다면
2. 그 위치가 가리키는 곳으로 노드를 옮겨주고 화살표를 다음문자로 이동시켜준다.
3. 만약 화살표가 가리키는 문자가 없다면 false를 return 해준다.
4. 화살표가 마지막까지 갔다면 해당 노드에 '*'문자가 있는지 확인 해 주고
5. '*'문자가 없다면 false return, 있다면 true return .**
   
   

1. 삽입때와 마찬가지로 해당위치에 화살표가 가리키는 문자가 있다면

2. 그 위치가 가리키는 곳으로 노드를 옮겨주고 화살표를 다음문자로 이동시켜준다.

4. 화살표가 마지막까지 갔다면 해당 노드에 '*'문자가 있는지 확인 해 주고

5. '*'문자가 없다면 false return, 있다면 true return .

Delete

문자열을 삭제할 때에는 다음과 같은 과정을 거친다.

1. 탐색할 때와 마찬가지로 탐색을 하고, 마지막에 '*' 문자가 있다면
2. 그 노드에 연결되어있는 노드가 없다면 해당 노드를 삭제해 주고,
3. 부모노드로 올라가면서 더 연결되어있는 노드가 없다면 해당 노드를 삭제해준다.
4. 만약 삭제하려는 노드에 연결되어있는 노드가 더 있다면 해당되는 문자만 지워주고 끝.
   

1. 탐색할 때와 마찬가지로 탐색을 하고, 마지막에 '*' 문자가 있다면

2. 그 노드에 연결되어있는 노드가 없다면 해당 노드를 삭제해 주고,

3. 부모노드로 올라가면서 더 연결되어있는 노드가 없다면 해당 노드를 삭제해준다.

4. 만약 삭제하려는 노드에 연결되어있는 노드가 더 있다면 해당되는 문자만 지워주고 끝.

장단점

장점 : 문자열을 추가, 탐색, 삭제가 모두 O(m)안에 끝난다.

단점 : 문자마다 메모리할당을 하게되어 문자열의 길이가 길어질수록 메모리를 많이 차지한다.

trie 참고 영상