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

 

 

트라이(trie)란?

 

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조.

흔히 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조이다.

 

장단점

트라이는 문자열 검색이 빠르다.문자열을 탐색할때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 효율적이다.각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있음.

 

삽입 예제

apple, app, asia를 입력했을 때의 모습

 

처음 apple을 넣을 때 head의 자식노드에 아무것도 없으므로 a를 추가한다.

a노드의 자식도 없으므로 p를 넣어준다.

p의 자식도 없으므로 다음 글자인 p를 넣어준다. 

이런식으로 e까지 자식노드로 추가한 후 단어의 마지막임을 알리기 위해 e에 표시를 해준다.

 

다음 app을 넣을 때는 head에 a가 있으므로 a로 이동한다.

a의 자식중 p가 있으므로 p로 이동한다.

p의 자식중 p가 있으므로 p가 이동한다.

단어의 마지막이므로 p에 표시를 해준다.

 

이런식으로 삽입하면 된다.

 

탐색

탐색 또한 문자열을 한글자씩 쪼개어 읽으면서 해당 문자가 trie자료구조에 있나 확인하고 문자열의 끝에 왔을때 단어의 마지막임을 알리기 위해 한 표시가 있으면 해당 문자가 trie자료구조 안에 있다고 할 수 있다.

 

구현

 

package com.example.demo;

import javafx.application.Application;
import javafx.scene.Scene;
import javafx.scene.control.*;
import javafx.scene.layout.*;
import javafx.stage.Stage;

import java.util.HashMap;
import java.util.Map;

public class TrieVisualizer extends Application {

    private final Trie trie = new Trie(); // Trie 자료구조
    private final TreeItem<String> root = new TreeItem<>("Root"); // TreeView의 루트 노드
    private final TreeView<String> treeView = new TreeView<>(root); // 시각화를 위한 TreeView

    @Override
    public void start(Stage primaryStage) {
        // UI 구성
        TextField inputField = new TextField();
        inputField.setPromptText("Enter a word to insert");

        Button insertButton = new Button("Insert");
        insertButton.setOnAction(e -> {
            String word = inputField.getText().trim();
            if (!word.isEmpty()) {
                trie.insert(word); // Trie에 단어 삽입
                updateTreeView();  // TreeView 업데이트
                inputField.clear(); // 입력 필드 초기화
            }
        });

        VBox controls = new VBox(10, inputField, insertButton);
        controls.setStyle("-fx-padding: 10;");

        HBox layout = new HBox(10, controls, treeView);
        layout.setStyle("-fx-padding: 10;");

        // Scene 설정
        Scene scene = new Scene(layout, 600, 400);
        primaryStage.setTitle("Trie Visualizer");
        primaryStage.setScene(scene);
        primaryStage.show();
    }

    // TreeView를 Trie의 상태에 따라 업데이트
    private void updateTreeView() {
        root.getChildren().clear(); // 기존 트리 초기화
        buildTree(trie, root, "");
        root.setExpanded(true); // 루트 노드 확장
    }

    // Trie를 재귀적으로 탐색하며 TreeView 구성
    private void buildTree(Trie node, TreeItem<String> treeItem, String prefix) {
        if (node.isWord) {
            treeItem.getChildren().add(new TreeItem<>("Word: " + prefix));
        }
        for (Map.Entry<Character, Trie> entry : node.children.entrySet()) {
            char character = entry.getKey();
            Trie child = entry.getValue();
            TreeItem<String> childItem = new TreeItem<>(String.valueOf(character));
            treeItem.getChildren().add(childItem);
            buildTree(child, childItem, prefix + character);
        }
    }

    public static void main(String[] args) {
        launch(args);
    }

    // Trie 클래스 정의
    public static class Trie {
        private boolean isWord;
        private final Map<Character, Trie> children;

        public Trie() {
            isWord = false;
            children = new HashMap<>();
        }

        public void insert(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                node.children.putIfAbsent(c, new Trie());
                node = node.children.get(c);
            }
            node.isWord = true;
        }
    }
}