[알고리즘] 트라이(Trie) 알고리즘

💡트라이(Trie) 알고리즘이란?

트라이(Trie)

• 문자열을 저장하고, 빠르게 탐색하기 위한 트리 형태의 자료구조
• 접두사를 기준으로 탐색
• 문자열 배열에서 각 문자열 별 문자를 일일이 탐색하는 것보다 탐색 속도가 빠름
• 각 노드에서 자식에 대한 포인터를 배열로 저장한다는 점에서 메모리를 더 사용

 

트라이 구조

노드 구성

class Node{
    //노드의 자식 노드들을 저장
    HashMap<Character, Node> child;
    //이 노드가 단어의 끝인지 저장
    boolean endOfWord;
}

메소드 구성

삽입(insert)

“TO” 삽입

1. 루트 노드에 T 자식 없으므로 생성
2. T 노드에 O 자식 없으므로 생성
3. O 노드 이후 문자 단위 탐색 끝났으므로 endOfWord = true 설정

“TA” 삽입

1. 루트 노드에 T 자식 있으므로 T 자식으로 이동
2. T 노드에 A 자식 없으므로 생성
3. A 노드 이후 문자 탐색 끝났으므로 endOfWord = true 설정

“CAT” 삽입

1. 루트 노드에 C 자식 없으므로 생성
2. C 노드에 A 자식 없으므로 생성
3. A 노드에 T 자식 없으므로 생성
4. T 노드 이후 문자 탐색 끝났으므로 endOfWord = true 설정

“TREE” 삽입

1. 루트 노드에 T 자식 있으므로 T 자식으로 이동
2. T 노드에 R 자식 없으므로 생성
3. R 노드에 E 자식 없으므로 생성
4. E 노드에 E 자식 없으므로 생성
5. E 노드 이후 문자 탐색 끝났으므로 endOfWord = true 설정

 

탐색(search)

“TRE” 탐색

1. 루트 노드에 T 노드 있으므로 이동
2. T 노드에 R 자식 있으므로 이동
3. R 노드에 E 자식 있으므로 이동
4. E 노드에서 endOfWord 는 false 이므로 false 리턴

“TAKE” 탐색

1. 루트 노드에 T 노드 있으므로 이동
2. T 노드에 A 자식 있으므로 이동
3. A 노드에 K 자식 없으므로 false 리턴

삭제(delete)

“TA” 삭제

1. “TA” 탐색
2. 맨 마지막 문자 “A”의 endOfWord를 false 로 변경
3. “A”에 자식 노드가 있는지 확인. 있으면 return, 없으면 삭제 후 T 노드로 이동
4. “T”에 자식 노드가 있는지 확인. 있으면 return, 없으면 삭제 후 루트 노드로 이동

구현

Node 클래스

class Node{
    //노드의 자식 노드들을 저장
    HashMap<Character, Node> child;
    //이 노드가 단어의 끝인지 저장
    boolean endOfWord;
    
    public Node() {
        this.child = new HashMap<>();
        this.endOfWord = false;
    }
}

Trie 클래스

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

    public void insert(String str); //삽입
    boolean search(String str); //탐색
    public boolean delete(String str);//삭제
        
}

insert 메서드

public void insert(String str){
    //시작 노드를 루트노드로 설정
    Node node = this.root;

		// 문자열의 문자 단위로 탐색
    for(int i=0;i<str.length(); i++){
        char c = str.charAt(i);
        //  해당 문자가 현재 노드의 자식노드 중에 있는지 확인
        node.child.putIfAbsent(c,new Node());
        // 없으면 생성 후 자식노드로 이동
        node = node.child.get(c);
    }
    // 문자열 탐색 후 마지막 문자가 단어의 끝임을 명시
    node.endOfWord = true;
}

search 메서드

public boolean search(String str){
    Node node = this.root;

    //문자열을 문자 단위로 탐색
    for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);

            // 자식 노드에 찾는 문자가 없으면 false 리턴
            if(!node.child.containsKey(c)) return false;

            // 해당 노드가 있으면 자식 노드로 이동
            node = node.child.get(c);
    }
    // 마지막 노드 도달 시, endOfWord 반환
    return node.endOfWord;
}

delete 메서드

public boolean delete(String str) {
    boolean result = delete(this.root, str, 0);
    return result;
}

private boolean delete(Node node, String str, int idx) {
    char c = str.charAt(idx);

    // 지워야 할 문자가 자식노드에 없으면 문자열 없어서 삭제 실패, false 리턴
    if(!node.child.containsKey(c)){
            return false;
    }

    Node cur = node.child.get(c);
    idx++;
    // 문자열 길이 만큼 탐색하여 도달
    if(idx == str.length()){
            // 문자열 끝이 endOfWord 가 아니면 문자열 없어서 삭제 실패, false 리턴
            if(!cur.endOfword){
                     return false;
            }
            // 문자열 끝의 endOfWord를 false로 변경
            cur.endOfWord = false;

            // 지우려는 문자열의 뒤에 다른 자식이 없다면 현재 노드에서 자식노드 삭제
    // 문자열 뒤에 다른 자식이 있다면 탐색 끝나고 돌아가기
    if(cur.child.isEmpty()){
        node.child.remove(c);
    }
    }
    else {
            // 삭제 실패
            if(!this.delete(cur, str, idx)){
                    return false;
            }

            // true를 반환받았고, 현재 노드의 자식노드가 비어있으면 현재 노드를 부모의 자식에서 삭제
    if(!cur.endOfWord && cur.child.isEmpty()){
        node.child.remove(c);
    }

    }

    return true;
		
}

 

전체 코드

class Node{
    //노드의 자식 노드들을 저장
    HashMap<Character, Node> child;
    //이 노드가 단어의 끝인지 저장
    boolean endOfWord;
    
    public Node() {
        this.child = new HashMap<>();
        this.endOfWord = false;
    }
}

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

    public void insert(String str){
    //시작 노드를 루트노드로 설정
        Node node = this.root;

            // 문자열의 문자 단위로 탐색
        for(int i=0;i<str.length(); i++){
            char c = str.charAt(i);
            //  해당 문자가 현재 노드의 자식노드 중에 있는지 확인
            node.child.putIfAbsent(c,new Node());
            // 없으면 생성 후 자식노드로 이동
            node = node.child.get(c);
        }
        // 문자열 탐색 후 마지막 문자가 단어의 끝임을 명시
        node.endOfWord = true;
    }
    
    
    public boolean search(String str){
		Node node = this.root;
		
		//문자열을 문자 단위로 탐색
		for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);

            // 자식 노드에 찾는 문자가 없으면 false 리턴
            if(!node.child.containsKey(c)) return false;

            // 해당 노드가 있으면 자식 노드로 이동
            node = node.child.get(c);
		}
		// 마지막 노드 도달 시, endOfWord 반환
		return node.endOfWord;
	}
    
    
    public boolean delete(String str) {
		boolean result = delete(this.root, str, 0);
		return result;
	}

	private boolean delete(Node node, String str, int idx) {
		char c = str.charAt(idx);
		
		// 지워야 할 문자가 자식노드에 없으면 문자열 없어서 삭제 실패, false 리턴
		if(!node.child.containsKey(c)){
				return false;
		}
		
		Node cur = node.child.get(c);
		idx++;
		// 문자열 길이 만큼 탐색하여 도달
		if(idx == str.length()){
            // 문자열 끝이 endOfWord 가 아니면 문자열 없어서 삭제 실패, false 리턴
            if(!cur.endOfword){
                     return false;
            }
            // 문자열 끝의 endOfWord를 false로 변경
            cur.endOfWord = false;
				
			// 지우려는 문자열의 뒤에 다른 자식이 없다면 현재 노드에서 자식노드 삭제
            // 문자열 뒤에 다른 자식이 있다면 탐색 끝나고 돌아가기
            if(cur.child.isEmpty()){
                node.child.remove(c);
            }
        }
        else {
            // 삭제 실패
            if(!this.delete(cur, str, idx)){
                    return false;
            }

            // true를 반환받았고, 현재 노드의 자식노드가 비어있으면 현재 노드를 부모의 자식에서 삭제
            if(!cur.endOfWord && cur.child.isEmpty()){
                node.child.remove(c);
            }
		
		}
		
		return true;
		
	}
    
}