트라이(Trie)는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조다.
트라이는 검색을 뜻하는 ‘retrieval’에서 따왔으며 전형적인 다진 트리의 형태를 띤다.
ex)
다음과 같은 트라이에서 단어 apple을 찾을 때 단 5번 만에 apple 문자열 존재 여부를 파악할 수 있다. 문자열의 길이만큼 탐색하면 되기 때문이다.
트라이는 문자열을 위한 트리 형태로 문자 개수만큼 자식이 있어야 하므로 많은 자식 노드를 갖고 있는 트리이다
트라이의 insert, search, startsWith 메소드를 구현하라