[자료구조] 비선형 자료구조 - 트라이

1. 트라이(Trie)란 무엇일까

---

• 문자열을 저장하고 빠르게 탐색하기 위한 정렬된 트리 형태의 자료 구조
• 문자열을 저장하기 위한 메모리가 추가적으로 필요하지만 탐색이 빠르다.
• 길이가 N인 문자열 탐색의 시간 복잡도 : O(N)
• 단어의 마지막에는 노드에 표시를 한다.

 

 

(1) 트라이 형태

• 문자열 구성 : apple, april, ace, bear, best

 

 

 

(2) 트라이 삽입 / 삭제

• 문자열 "apple" , "april"이 삽입되어 있는 상태에서 , "app"을 삽입할 때
• 동일한 단어가 있으면 그 노드를 타고 내려가다가 단어의 마지막일 때 표시한다.

 

 

• "apple"을 삭제

 

• "app" 을 삭제

 

 

---

 

 

2. 트라이(Trie) 구현

---

• Key와 Value 로 이루어진 노드로 구성
• Key : 알파벳  /  Value : 자식 노드

class Node {
	HashMap<Character, Node> child;
  	boolean isTerminal;
}

 

 

코드로 구현하기

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 = root;
        for(int i=0; i<str.length();i++) {
            char c = str.charAt(i);
            
            cur.child.putIfAbsent(c,new Node());
            cur = cur.child.get(c);
            
            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);
            
            if(cur.child.containsKey(c)) {
                cur = cur.child.get(c));
            } else {
                return 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);
        if(!node.child.containsKey(c)) {
            return false;
        }
        Node cur = node.child.get(c);
        idx++;
        if(idx == str.length()) {
            if (!cur.isTerminal) {
                return 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;
    }
}