<div id="readability-page-1" class="page"><time>2019-10-15 에 작성하고, 2020-03-09 14:21:00 에 업데이트한 문서입니다. ✅</time> — <a href="/tags/data-structure">Data Structure</a> — 2 min read<section>geohash 관련한 PR을 보고 있었는데, 다른 팀원분이 Trie로 접근해볼 것을 제안해주시더군요. Trie 자료구조, 분명히 입사 전에는 알고 있었는데 기억안나서 정리해봅니다. 😉<h2>Trie 자료구조 🌴</h2>어.. 어떻게 읽어야할까요? Trie의 용어를 만든 Edward Fredkin은 <code>retrieval</code> 의 중간 발음이다 - 라는 의미에서 <code>트리</code> 라고 읽었다고 합니다. 하지만 그러면 기존에 있던 트리 자료구조와 헷갈리니까, 다른 저자들은 <code>트라이</code> 라고 읽기 시작했고요. 이 글에서는 트라이라고 읽습니다. 검색을 목적으로 하는 트리의 일종입니다. 동적인 set, 혹은 서로 관련이 있는 array를 저장하기 위해 주로 사용되는데, 이때 키는 주로 <code>string</code> 입니다. 좀 정리해보면, string 저장하는데 그 string들 끼리의 관계도 표현해줄 수 있는 자료구조가 됩니다. 같은 노드의 자식들은 같은 prefix를 갖게 됩니다.추가) 그 자체로 트리 모양의 DFA(Deterministic finite automaton, 각 입력 심볼에 대해서 유일한 상태 변화를 취하는 유한 상태기계) 라고도 할 수 있습니다. 표현이 어려운데요. 이 부분은 계산이론이나 프로그래밍언어 같은 강의를 참고하여 나중에 보충하겠습니다.
 
 <img alt="Trie 56b6b7df 2bea 421d bc56 38232a04281b" title="Trie 56b6b7df 2bea 421d bc56 38232a04281b" src="https://juneyr.dev/static/aed9bcd455fbe6935cd6e6deb9c92b6a/7d769/Trie-56b6b7df-2bea-421d-bc56-38232a04281b.png" sizes="(max-width: 960px) 100vw, 960px" loading="lazy">
 위 그림을 볼까요. string값을 위와 같이 저장합니다. 같은 부모 노드를 가진 자식 노드 <code>te</code> 그리고 <code>to</code> 는 prefix가 <code>t</code>입니다. 아래도 마찬가지입니다. te의 자식 노드들은 모두 te로 시작합니다.이렇게, Trie는 탐색에 있어서 이점을 갖는 자료구조입니다. Trie에 저장된 것 중 가장 긴 string의 길이를 m이라고 하면, worst-case 탐색 시간이 O(m)이 걸립니다🤔 Trie를 대개 쓰는 곳은 자동완성 입니다. Trie는 빠르게 검색할 수 있고, 요소들을 삽입삭제하는 데도 편리합니다. 그래서 맞춤법 검사나 hypenation(글자가 하이픈으로 연결되었는지 판단) 프로그램에도 유용하다고 하네요.
위에서 잠깐 말했지만, geohash 검색에도 유용할 것 같은데요. 간단한 설명을 붙이자면, geohash는 전세계 지역을 hash 값으로 표현한 것입니다. 좌표 -&gt; hash 값으로 변형한 것이죠. 다만, 조금만 인풋이 비슷해도 완전히 다른 결과가 나와야하는 기존의 hash 알고리즘의 특성과는 다르게, geohash는 근접한 지역일 수록 비슷한 hash를 갖습니다. 사실상 큰 단위에서 같은 지역에 포함되어있다면 prefix가 완전히 같습니다. xn21421, xn21489 라는 해시는 큰 분류가 같은 지역이라고 생각하시면 됩니다. <h3>구현은 어떻게?</h3>어떻게 구현하는 건지 간단하게 알아봐야겠습니다! =)
<a href="https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/trie/TrieNode.java">문서</a>를 참고하여 java 구현도 함께 소개합니다. <h2>Patricia Trie 혹은 Radix Trie</h2>
 
 <img alt="PatriciaTrie bd8918c1 13f7 45bb a6a4 7bd9779bceba" title="PatriciaTrie bd8918c1 13f7 45bb a6a4 7bd9779bceba" src="https://juneyr.dev/static/0d9735bc9c2cae023f3ffb8db81d49cd/7d769/PatriciaTrie-bd8918c1-13f7-45bb-a6a4-7bd9779bceba.png" sizes="(max-width: 960px) 100vw, 960px" loading="lazy">
 Trie의 개선버전입니다. 공간 사용을 최소한으로 하는 Trie를 말합니다. 어떻게 하는 거죠? 만약 각 노드가 유일한 자식이라면, 그 부모와 합쳐 버립니다. 외동인 (!!!) 자식들이 없도록 합쳐버렸으니, 각 내부 노드가 자식이 있다면 모두 두 명 이상이 됩니다. (루트노드를 제외하구요) 원래는 각자 하나의 노드를 가졌어야할 외동 노드들이 모두 합쳐져 버렸으니까 <code>space-effient</code>, <code>space-optimized</code> 되었다고 얘기하고요.일반적인 트리와는 다르게, 가지가 요소 한개 혹은 여러개가 있는 레이블을 가질 수 있습니다. 이러한 특징 덕분에, <ul><li>긴 String이고</li><li>작은 set이고</li><li>긴 prefix를 공유하는 string들</li></ul>일 수록 유리합니다.<hr>Trie는 알고리즘 수업이나 자료구조에서는 많이 다루지 않지만 다양한 곳에서 사용되는 자료구조라고 합니다. 한번 나중에 더 깊게 파봐야겠네요! 대부분의 내용은 위키피디아를 참고하였습니다! 틀린 점이 있으면 둥글게 코멘트 주세요. 무례한 댓글은 삭제합니다. 👽<h2>참고</h2><a href="https://en.wikipedia.org/wiki/Trie">https://en.wikipedia.org/wiki/Trie</a><a href="https://en.wikipedia.org/wiki/Radix_tree">https://en.wikipedia.org/wiki/Radix_tree</a><a href="https://www.baeldung.com/trie-java">https://www.baeldung.com/trie-java</a><a href="https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/trie/TrieNode.java">https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/trie/TrieNode.java</a></section></div>

Juneyr.dev RSS Feed

June Kim

geohash 관련한 PR을 보고 있었는데, 다른 팀원분이 Trie로 접근해볼 것을 제안해주시더군요. Trie 자료구조, 분명히 입사 전에는 알고 있었는데 기억안나서 정리해봅니다. 😉 Trie 자료구조 🌴 어.. 어떻게 읽어야할까요? Trie의 용어를 만든 Edward Fredkin은  retrieval…

Trie 구조 츄라이🙆‍♀️

댓글