비선형 자료구조 - Trie

트라이 (Trie)

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

트라이 형태

문자열 구성 (apple, april, ace, bear, best)

트라이 구현

Key, Value로 이루어진 노드로 구성

• Key : 알파벳
• Value : 자식 노드

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

insert

public void insert(String str){
    Node cur = this.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;
        }
    }
}

search

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;
}

delete

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;
}

}