[자료구조] 트라이(Trie)

https://programmers.co.kr/learn/courses/30/lessons/60060?language=java

코딩테스트 연습 - 가사 검색

 

Trie 구현

 

먼저 Node 클래스를 만듭니다.

class Node {
    Map<Character, Node> childNodes = new HashMap<>();

    @Override
    public String toString(){
        return childNodes.keySet().toString();
    }
}

Node Class는 필드로 HashMap의 자식 노드를 가집니다.

자식 노드를 확인하기 위해 toString을 오버라이딩 해줍니다.

class Trie {

    Node rootNode = new Node();

    void insert(String s) {
        Node node = this.rootNode;

        for (int i = 0; i < s.length(); i++)
            node = node.childNodes.computeIfAbsent(s.charAt(i), key -> new Node());

    }

    boolean search(String s){
        Node node  = rootNode;

        for(int i = 0; i < s.length(); i++){

            node = node.childNodes.getOrDefault(s.charAt(i), null);

            System.out.print(node + " ");

            if(node == null)
                return false;
        }

        return true;
    }
}

Trie는 필드로 루트노드를 가집니다.

insert와 search를 구현했습니다.

 

insert

void insert(String s) {
        Node node = rootNode;

        for (int i = 0; i < s.length(); i++)
            node = node.childNodes.computeIfAbsent(s.charAt(i), key -> new Node());

    }

 

변수로 최상위 노드를 가집니다.

computeIfAbsent는 key를 찾아보고 해당하는 key가 있다면 value를 줍니다.

해당하는 key가 없다면 backupFunction을 실행하는데, 위 코드에서 backupFunction은 람다식으로 정의되어있습니다.

new Node() 즉 새로운 노드를 만듭니다.

그 결과 값을 node에 저장합니다. 여기서 결과 값은 ( key의 value 혹은 new Node()입니다. )

이것을 매개변수 s의 길이 만큼 반복합니다.

S가 "Hello" 일때를 예로 들겠습니다.

 

만약 "Hero"를 insert한다면

ComputeIfAbsent에서 Absent(부재)가 아님으로 new Node()를 만들지 않고 node변수를 E로 초기화 시킵니다.

"HER"을 insert한다면

이미 H의 자식 'E', E의 자식 'R'이 존재함으로 Node를 만들지 않습니다.

"HER"은 이미 있는 노드입니다.

search

 

boolean search(String s){
        Node node  = rootNode;

        for(int i = 0; i < s.length(); i++){

            node = node.childNodes.getOrDefault(s.charAt(i), null);

            System.out.print(node + " ");

            if(node == null)
                return false;
        }

        return true;
    }

 

마찬가지로 rootNode에서 시작합니다.

node의 자식노드를 찾습니다.

getOrDefault는 매개변수로 key와 default값을 받습니다.

key가 존재할 경우 value를 리턴하고 존재하지 않을 경우 default 값을 반환하게 됩니다.

즉 위의 코드로 본다면 해당 문자에 해당하는 key가 없다면 null을 반환하며 node가 null일 경우 false를 리턴합니다.

for문을 무탈하게 통과하면 true를 리턴합니다.

여기서 응용을 하려면 Node의 필드로 boolean 타입의 endOfWord를 가지게하고 현재 노드가 정점인지 확인할 수 있습니다.

"HEART"을 search하는 과정

정점에서 시작합니다.

ROOT -> 'H'

H -> 'E'

여기서 E -> 'A'를 해야되는데 A노드가 보이지 않습니다.

node = node.childNodes.getOrDefault(s.charAt(i), null);​

getOrDefault에서 default 값으로 null을 주었으니 node = null이 될 것입니다.

if(node == null)
    return false;

이렇게 false를 반환합니다.