비선형 자료구조 - 트라이(Trie)

트라이(Trie)

• 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조
• 정렬된 트리 구조
• 문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름
• 길이가 N인 문자열 탐색의 시간 복잡도: O(N)
  • 생성 복잡도: O(N)
  • M: 문자열 개수

 

 

트라이 형태

• 문자열 구성
  • apple, april, ace, bear, best
  • 파란색 노드: 문자열의 끝을 표시하는 flag를 나타냄

 

 

트라이 - 삽입(1)

• 삽입 문자열: apple

 

트라이 - 삽입(2)

• 삽입 문자열: april

 

트라이 - 삽입(3)

• 삽입 문자열: app
  • app까지 있는 단어의 존재를 표시하기 위해 flag가 필요한 것임

 

 

트라이 - 삭제(1)

• 삭제 문자열: apple
  
  • e의 flag 표시를 해제하고 자식 노드들이 없으면 e를 지우고
  • l도 자식노드들이 없으므로 지움
  • p는 flag표시가 있으므로 해당 알파벳이 포함된 단어가 있다고 판단하고 지우지x

 

트라이 - 삭제(2)

• 삭제 문자열: app
  • app 단어의 끝 표시인 p의 flag를 해제하면 트라이 자료구조에서 삭제임을 인식

 

 

트라이 구현

• Key, Value로 이루어진 노드로 구성
  • Key: 알파벳
  • Value: 자식 노드
  • boolean: flag 표시

 

 

 

 

트라이 자료구조 자바 코드 구현

구현 코드

// 비선형 자료구조 - 트라이 (Trie)

import java.util.HashMap;

class Node {
    HashMap<Character, Node> child;
    // 단어 끝인지 체크 용
    boolean isTerminal;

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

class Trie {
    Node root;

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

    public void insert(String str) {
        Node cur = this.root;

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            // 현재 노드 기준 c 문자에 해당하는 노드가 없으면 추가
            //putIfAbsent: 현재 해당 문자로 시작하는 노드가 cur 기준으로 없으면 넣어주고 있으면 pass
            cur.child.putIfAbsent(c, new Node());
            // 이어서 추가하기 위해 다음 문자 쪽으로 이동
            cur = cur.child.get(c);

            // str 끝이면 true 체크 후 return
            if (i == str.length() - 1) {
                cur.isTerminal = true;
                return;
            }
        }
    }

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

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            // 해당 단어 있으면 이동, 없으면 false 반환
            if (cur.child.containsKey(c)) {
                cur = cur.child.get(c);
            } else {
                return false;
            }

            // i 가 str 끝에 도달했지만 cur 의 terminal 이 true 아니면
            // 해당 단어가 들어 있는 것은 아니므로 false 반환
            if (i == str.length() - 1) {
                if (!cur.isTerminal) {
                    return false;
                }
            }
        }
        return true;
    }

    public void delete(String str) {
        boolean ret = this.delete(this.root, str, 0);
        if (ret) {
            System.out.println(str + " 삭제 완료");
        } else {
            System.out.println(str + " 단어가 없습니다.");
        }
    }

    //재귀적으로 사용할 삭제 메소드
    public 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()) {
            // 끝에 도달했지만 terminal true 아닌 경우
            // 해당 단어와 일치하는 것은 아니므로 false 반환
            if (!cur.isTerminal) {
                return false;
            }

            // 해당 단어와 일치할 경우 먼저 isTerminal false 로 변경
            cur.isTerminal = false;
            // 그 외의 문자 없는 경우 삭제
            if (cur.child.isEmpty()) { // 파생되는 단어들이 없을 때
                node.child.remove(c);
            }
        } else { // 지워야 하는 단어를 찾기 전
            if (!this.delete(cur, str, idx)) {
                return false;
            }

            // 끝 문자 삭제 후 앞의 문자들에서 파생되는 단어들 없으면 함께 삭제
            if (!cur.isTerminal && cur.child.isEmpty()) {
                node.child.remove(c);
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        // Test code
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("april");
        trie.insert("app");
        trie.insert("ace");
        trie.insert("bear");
        trie.insert("best");
        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("april"));   // true
        System.out.println(trie.search("app"));      // true
        System.out.println(trie.search("ace"));     // true
        System.out.println(trie.search("bear"));    // true
        System.out.println(trie.search("best"));    // true
        System.out.println(trie.search("abc"));     // false

        System.out.println();
        trie.delete("apple");
        System.out.println(trie.search("apple"));   // false
        System.out.println(trie.search("april"));   // true
        System.out.println(trie.search("appl"));    // false
        trie.delete("apple");
    }
}

출력 결과

true
true
true
true
true
true
false

apple 삭제 완료
false
true
false
apple 단어가 없습니다.