트라이

wellsbabo·2023년 4월 7일
0

자료구조

목록 보기
7/7

트라이

개요

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

트라이 형태

  • 문자열 구성: apple, april, ace, bear, best
  • 같은 위치의 공통된 글자에 대해서는 중복되서 들어가지 않음
  • 각 문자열의 끝을 의미하는 flag가 있음

삽입

1) 삽입 문자열: apple

2) 삽입 문자열: april

3) 삽입 문자열: app

  • flag를 세움. flag가 3개로 총 3개의 단어가 있음을 알 수 있다

삭제

1) 삭제 문자열: apple

  • 쭉 따라가서 끝 문자부터 삭제
  • 모두 지우는게 아니라, 남겨진 단어들에게 필요하지 않은 문자만 삭제

    2) 삭제 문자열: app
  • flag만을 삭제

구현

  • Key, Value로 이루어진 해시맵 노드로 구성
    • Key: 알파벳
    • Value: 자식 노드
class Node{
	HashMap<Character, Node> child;
    booleand isTerminal; //문자열 끝을 구분하는 flag
}

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

import java.util.HashMap;

class Node {
    HashMap<Character, Node> child;
    boolean isTerminal; //문자열의 끝인지 체크하는 flag

    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 문자에 해당하는 노드가 없으면 추가
            cur.child.putIfAbsent(c, new Node());

            //이어서 추가하기 위해 다음 문자 쪽으로 이동
            //get(c)를 해야 노드가 나옴
            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;
    }


    //재귀로 처리하기 위해
    //delete 메소드를 2개로 나눔
    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()){
            //끝에 도달했지만, 문자열의 끝을 의미하는 isTermianl이 true가 아닐 경우
            //해당 문자열과 일치하는 것이 아니므로 false 반환
            if(!cur.isTerminal){
                return false;
            }

            // 해당 문자열과 일치할 경우 isTerminal false로 변경 = 해당 문자열을 삭제하는 것
            cur.isTerminal = false;

            // 이후의 글자 없으면 삭제
            if(cur.child.isEmpty()){
                node.child.remove(c);
            }
        }
        //단어의 끝에 도달하지 않았을 때
        else{
            //delete를 계속 진행하면서 false가 나오면 return false하여 종료
            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");
    }
}

0개의 댓글