SY DevLog

트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트 lotuslee.tistory.com 위의 글에서는 트라이 개념, 트라이 노드 특징(Map, isLastChar)에 대해 설명했었다. 이번에는 트라이(Trie)의 동작 1. 단어 삽입 2. 단어 포함 여부 3. 단어 삭제 에 대해서 자세하게 다룰 것이다. 트라이 위의 트라이 그림에서 포함되어 있는 단어는 "bird", "big", "beer", "girl", "god", "grow" 여섯 가지이다. 트라이노드(TrieNode)의 클래스는 아래와 같이 구현할 수..

트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 시간복잡도 : O(m) (m은 문자열 길이) 트라이 예 트라이(Trie) 특징 트라이(Trie) 노드 특징 1. 트라이의 각 노드는 문자와 자식 노드를 맵 형태로 가지고 있다. -> Map 예를 들어, 루트노드의 경우, 자식노드가 2개이므로 Key가 'b' 이고, Value에 왼쪽 자식 노드를 가지고 있으며, Key가 'g' 이고, Value에는 오른쪽 자식 노드를 가지고 있다. 루트의 왼쪽 자식 노드도 마찬가지이다. 이 노드는 그림에서 보면 'b'를 가지고 있는 것처럼 보이지만, 사실은 특정 문자를 가지고 있는 것..