[트리] 트라이

✔ 트라이

트라이란?

• 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조
• 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행
• 문자 종류의 개수인 N에 따라 N진 트리가 결정됨
• 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지

트라이 과정

1. 루트 노드는 공백을 유지하고 첫 번째 단어의 각 알파벳에 해당하는 노드를 생성
2. 두 번째 단어를 삽입할 때는 루트 노드에서부터 검색을 수행
3. 검색 노드가 공백 상태이면 신규 노드를 생성하고, 아니면 이동