[자료구조] 트라이 (Trie)

📚 트라이 (Trie)

문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조

래딕스 트리(Radix tree), 접두사 트리(Prefix tree), 탐색 트리(Retrieval tree) 등으로 불리며

Trie는 Retrieval tree에서 파생된 단어다.

 

기본 구조

문자열 집합 {"apple", "app", "agree", "eight", "elephant", "zero"} 을 트라이로 직접 구현

장점

문자열을 빠르게 탐색 할 수 있다.

 

단점

필요한 메모리가 크다는 단점

총 메모리는 O(포인터의 크기 * 포인터 배열의 개수 * 총 노드의 개수) 만큼 필요

 

단점을 보완하기 위해 map 이나 vector 을 사용해 필요한 노드만 메모리에 할당하는 방식 채택

---

🦋 트라이의 사용사례

• 자동완성 기능
• 사전 검색

---

✍🏻 트라이 ADT (추상 데이터 타입)

create()	트라이 생성
insert(str)	문자열 삽입
delete(str)	문자열 삭제
search(str)	문자열 탐색

 

---

⚙️ 트라이 기능 & 동작원리

트라이 노드 생성

• 문자열을 이루는 알파벳, 다음 노드 쌍의 Map 과
• 현재 노드가 문자열의 끝 노드인지 확인하기 위한 boolean 타입의 isTerminal를 멤버로 갖는 클래스 생성

class Node {
    HashMap<Character, Node> child;
    boolean isTerminal;
    
    public Node() {
    	this.child = new HashMap<>();
        this.isTerminal = false;
    }
}

 

문자열 삽입

• 아무것도 들어있지 않은 root부터 시작
• 문자열을 앞에서부터 쪼개면서 문자를 하나씩 확인
• 이미 있는 문자라면 다음 노드로 이동
• 이미 있는 문자가 아니라면 새로운 노드 추가
• 문자열 끝 문자까지 넣었다면 그 노드의 isTerminal = true로 바꿔주고 return

// 슈도 코드

Node root;
public Trie() {
	this.root = new Node();
}

public void insert(String str) {
	Node cur = this.root;
    
    for (i = 0; str 끝까지) {
    	Character c = str.charAt(i);
        
        if (이미 있는 문자가 아니면) {
        	cur.child.put(c, new Node()); // 새로운 노드 생성
        } else (이미 있는 문자라면) {
        	cur = cur.child.get(c); // 다음 노드로 이동
        }
        
        if (str 끝까지 다 넣었다면) {
    		isTerminal = true;
            return;
        }
    }
}

 

문자열 삭제

• 문자를 하나씩 비교
• 찾으려는 문자가 있는지 확인 후 없으면 false 리턴
• 다음 노드를 확인하기 위해 index증가
• 증가한 index에 대해 문자열의 길이와 같아졌지만 isTerminal이 true가 아니라면 false 리턴
• true라면 찾으려는 문자열이기 때문에 삭제를 위해 isTerminal을 false로 먼저 바꿔줌
• 다음 노드가 없다면 현재 노드 삭제
• 문자열의 길이와 아직 같지 않은 노드에 대해서는 재귀함수 이용
• 재귀함수의 결과가 false라면 false 리턴

// 슈도 코드

public boolean delete(Node node, String str, int index) {
	Character c = str.charAt(index);
    
    if (문자가 포함되어 있지 않는다면) {
    	return false;
    }
    
    Node cur = node.child.get(c); // 다음 노드 저장
    index 하나 증가;
    
    if (index가 문자열의 길이와 같다면) {
    	if (isTerminal이 false라면) {
        	return false;
		}
        
        지우기 전에 isTerminal false로 바꿈;
        
        if (다음 노드가 없는게 맞다면) {
        	현재 노드 remove;
        }
    } else (index가 아직 문자열의 끝까지 안갔으면) {
		if (delete(cur, str, index)가 false라면) {
        	return false;
        }
        
        if (isTerminal이 false이고, 다음 노드가 없는게 맞다면) {
        	현재 노드 remove;
        }
	}
    return true;
}

---

⏱️ 트라이의 시간복잡도

제일 긴 문자열의 길이를 N, 총 문자열의 수를 M이라고 할 때,

• 생성 O(N*M)
• 탐색 O(N)
• 삽입만 O(N)

생성시 가장 긴 문자열의 길이 N을 M만큼 넣어야 하니 O(N*M)

탐색은 가장 긴 문자열의 길이만큼만 탐색하면 되기 때문에 O(N)

삽입은 문자열을 문자 하나씩 넣으면 되기 때문에 가장 긴 문자열의 길이 N만큼의 O(N)