[JAVA/자료구조] 트라이(Trie) 개념, 직접 구현하기

트라이(Trie)

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

문자열 저장을 위한 메모리를 사용하지만, 탐색속도가 매우 빠르다. O(N)

 

(Java에서 Queue,Stack,List와 다르게 Trie를 직접적으로 구현해놓은 라이브러리는 없다.)

---

트라이의 형태

Trie에 들어있는 문자열 

apple, april

bus, busy, beer, best

트라이의 구조(특징)

루트 노드

• 루트노드는 항상 비어있다.
• 루트노드의 자식노드는 각 단어들의 첫 글자들이다.

endOfWord 표시

• 파란색으로 칠해져 있는 노드는 각 문자열의 마지막 글자이다.

각 노드 구성

• 각 노드의 자식노드들을 Map에 저장한다.
• 해당 노드가 단어의 마지막을 뜻하는 endOfWord를 저장할 boolean형 필드를 갖는다.

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

---

삽입(insert) 방법

루트노드부터 자식노드를 담은 Map에서 삽입할 문자열의 한 문자씩 찾아본 뒤, 없으면 추가하고 있으면 타고 들어간다.

문자열의 마지막 문자가 되면 노드에 마지막 노드라는 표시를 한다.

그림에서는 파란색 색칠을, 코드로는 endOfWord = true 로 바꿔준다.

---

탐색(search) 방법

Trie에 "best"가 존재하는지 탐색해보자.

중간에 한번이라도 원하는 값이 존재하지 않으면 트라이에는 "best"가 들어있지 않는 것이다.

1. root node의 자식노드들 중 'b' 가 있는지 찾아본다. - 이제 b로 이동해서 찾는다.
2. 'b' 노드의 자식노드들 중에서 'e' 가 있는지 찾아본다. - 이제 e로 이동해서 찾는다.
3. 'e' 노드의 자식노드들 중에서 's' 가 있는지 찾아본다. - 이제 s로 이동해서 찾는다.
4. 's' 노드의 자식노드들 중에서 't' 가 있는지 찾아본다.  - t로 이동한다.
5. 't'는 "best"의 마지막 글자이다. 't'의 endOfWord를 확인해보고 endOfWord=true면 탐색 성공이다.
6.  't'의 endOfWord를 확인했는데 endOfWord=false면 탐색 실패이다. (트라이에 "best"가 없다.)

---

삭제(delete) 방법

이번엔 "apple"을 삭제해보자.

1. 위의 탐색 방법으로 "apple"을 탐색하여 "apple"의마지막 노드로 이동한다.
2. 'e'의 endOfWord를 확인하여 true면 삭제 성공이다. 'e'의 endOfWord를 false로 바꿔준다. (삭제한다는 것은 더이상 이 트라이에서 해당 문자열을 찾을 수 없다는 것이다.)
3. 'e'의 자식노드가 있는지 확인한다. 없으면 이제 거꾸로 타고올라가면서 노드를 삭제해준다.
4. 'l'에 'e'를 제외한 다른 자식노드가 있는지 확인한 후 없으면 'l' 노드를 삭제한다.
5. apple 까지 도착했다. 찾아보니 p를 제외한 다른 자식노드('r') 이 존재한다. p는 삭제하지 않는다.

---

구현

구현은 Node 클래스, Trie 클래스로 나뉜다.

Node 클래스는 자식노드들을 담을 Map, 마지막글자 여부를 확인할 boolean endOfWord 필드를 갖는다.

---

Node 클래스

생성할때, child HashMap을 만들어주고, endOfWord는 false로 설정한다.

child 맵은 key값으로 자식노드의 문자를 갖고, value로 자식노드의 Node 객체를 갖는다.

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

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

---

Trie 클래스

Trie 클래스는 root 노드를 필드로 갖는다.

또한, 생성할 때 root에 new Node() 객체를 만들어준다.

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);//삭제
        
}

---

삽입 메서드

맨 처음에 node = this.root로 루트노드부터 시작한다.

for문을 돌며 한 문자씩 각 노드의 child 노드에 값이 있나 확인하고,

있으면 해당 노드로 이동하고, 없으면 이번 문자 노드를 생성하고 그 노드로 이동한다.

 

for문이 종료되면 node에는 마지막 문자에 해당하는 노드가 저장되어있을테니,

해당 노드의 endOfWord를 true로 바꿔준다.

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(str.charAt(i)); (putIfAbsent는 값 존재시에 value를 반환
        //없을 때 : 새로운 노드를 생성해서 넣음
        node = node.child.get(c); //자식노드로 이동
    }
    //for문이 끝나면 현재 노드는 마지막 글자이기 때문에 단어의 끝임을 명시
    node.endOfWord = true;
}

---

탐색 메서드

삽입 메서드와 비슷하게 자식노드들 중 원하는 문자가 있는지 확인한다.

중간에 하나라도 없으면 탐색 실패이다.

마지막 문자까지 찾으면 마지막으로 endOfWord가 true인지 확인한다.

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

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

        if(node.child.containsKey(c)){//자식노드에 c가 있을 때 계속 탐색 진행
            node = node.child.get(c);
        }else{
            return false;
        }
    }
    //마지막 노드까지 도달 시
    return node.endOfWord; //마지막 노드의 endOfWord를 반환
}

---

삭제메서드

삭제 메서드는 사용자가 삭제 요청 시 사용하는 public boolean delete(String str); 메서드, 

내부에서 재귀를 통해 삭제하는private boolean delete(Node node, String str, int idx) 메서드로 나뉜다.

 

위의 메서드에서 아래 메서드를 한번 호출해주고 아래 메서드에서 재귀적으로 노드들을 찾는다.

//사용자가 삭제 요청 시 사용하는 메서드
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);

    //현재 노드의 자식노드에서 c를 지워야되는데 없으면 return false
    if(!node.child.containsKey(c)){
        return false;
    }

    Node cur = node.child.get(c);
    idx++;
    if(idx == str.length()){//문자열 끝에 도달했을 때
        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를 반환받았고, 자식노드가 비어있으면 현재 노드를 삭제
        // "node"는 "cur"의 부모노드임. 즉,"cur"노드를 "node"의 자식 Map에서 삭제하는 것
        if(!cur.endOfWord && cur.child.isEmpty()){
            node.child.remove(c);
        }
    }
    return true;
}