트라이는 자료구조의 탐색트리의 일종으로 문자열 탐색을 아주 빠르게 해주는 자료구조이다.

트리의 루트부터 자식들을 따라가며 생성한 문자열로 이루어 지며, 하나의 단어가 되면 끝을 표시하는 변수 end mark를 저장하여 단어의 끝을 구분할 수 있다.

장점 : 단순 리스트 저장해서 문자열을 비교하면서 탐색하는것에 비해 탐색의 시간복잡도가 매우 좋다.

단점 : 각 노드에 대한 자식에 대한 포인터를 배열로 저장하므로 공간 복잡도가 높다.

사용 : 검색어 자동완성, 사전 찾기, 문자열 검사 등에 사용됨

사진 출처 : https://twpower.github.io/187-trie-concept-and-basic-problem

코드 소개(with JS)

트라이는 사진처럼 문자열 리스트를 각 알파벳 단위로 쪼개고 객체를 만들어 분류한다 예를 들면 [app, application]이 있다면 이 문자열들을 각각 쪼개어 객체 트리 형태로 만든다고 할때

a : {
  p : {
    p : {
     //단어 한개가 끝났으니 표시하기 위해, end mark로 * : '해당 단어' 형태로 만들었다
      * : "app",
      l : {
        i : {
          c : {
            a : {
              t : {
                i : {
                  o : {
                    n : {
                      * : "application",
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

위와 같은 구조가 트라이이다. 알파벳을 쪼개어 객체에 넣어주고, 단어가 끝나면 end mark 형태로 개발자 원하는 형태로 표시해두면 된다.

그리고 target 되는 즉 찾아야 하는 string 문자열이 들어 오면, 그걸 쪼개어 아래 trie에 검색해주면 해당하는 객체 depts 부터 가져올수 있는데, 그 객체를 갖고와서 dfs 탐색 알고리즘 사용하면 자식 노드로 깊게 들어가면서 탐색하게 된다. 탐색하면서 key 값이 "*" 문자열일때 array에 push해서 출력해주면 된다.

const list = ["cat", "cats", "dog", "dogs", "app", "application"];
const trie = {};

const solution = (list) => {
  const newTrie = buildTrie(list);
};

const searchDFS = (target) => {
	//여기서도  trie를 레퍼런스 참조 변수에 넘긴다.
  let rootDict = trie;

  const result = [];

  //찾아야 하는 문자가 있으면 trie에서 깊이로 들어간다
  for (let i = 0; i < target.length; i++) {
    const curTargetChar = target[i];
    if (!rootDict[curTargetChar]) return [];
    rootDict = rootDict[curTargetChar];
  }

  //찾아야하는 문자 총 길이까지 깊이로 들어가고, 그 이상의 깊이는 DFSAlg()함수에 넣어준다. 즉 DFSAlg함수에서 단어의 end mark *를 찾아서 list에 push해서 리턴해주면 답이 된다.
  DFSAlg(rootDict, result);
  return result;
};

const DFSAlg = (curRoot, result) => {
  // console.log(curRoot);
  for (let [key, val] of Object.entries(curRoot)) {
    if (key === "*") {
      result.push(val);
      continue;
    }
    DFSAlg(val, result);
  }
};

//Trie를 만들어주는 함수다.
const buildTrie = (list) => {
  if (!list.length) return {};
  for (let l = 0; l < list.length; l++) {
    const currentWord = list[l];

    //trie를 사용하기 편하게 레퍼런스 참조변수를 만들어준다.
    let currentRoot = trie;
    
    for (let c = 0; c < currentWord.length; c++) {
      //선택한 단어를 각 문자 단위로 선택한다.
      const curChar = currentWord[c];
      //trie에 선택한 문자 단위가 없으면, 문자단위를 키로 value={} 로 만들어 준다.
      if (!currentRoot[curChar]) {
        currentRoot[curChar] = {};
      }
      //문자 단위가 있으면 해당 위치를 currentRoot에 할당해준다.
      currentRoot = currentRoot[curChar];
    }
    //단어가 끝나면  * :{ } 형태로 만들어준다.
    currentRoot["*"] = currentWord;
  }
};

solution(list);

//찾아야 할 문자열을 아래 target에 넣어주면된다.
searchDFS(target);