trayは、文字列をすばやく検索できる資料構造の検索ツリーです.
木の根元から,サブストリングに沿って生成された文字列が1つの単語になった後,終了を表す変数endmarkを格納することで単語の終了を区別できる.
利点:単純なリスト比較文字列を保存してナビゲートするよりも、ナビゲーションの時間的複雑さが非常に高い.
欠点:各ノードのサブノードのポインタを配列として格納するため、空間的複雑度が高い.
使用:クエリーの自動完了、辞書の検索、文字列のチェックなど

写真の出所:https://twpower.github.io/187-trie-concept-and-basic-problem

コード概要（JS使用）

Trayは写真のように文字列リストをアルファベット単位で分割し、オブジェクトを作成して分類します.たとえば、[app,application]がある場合、これらの文字列はそれぞれオブジェクトツリーに分割されます.

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

以上の構造は三脚です.アルファベットをオブジェクトに分割し、単語が終わったらendmarkとして開発者に表示します.
次に、targetに入ると検索する文字列文字列が必要になり、それを分割して次のtrieに検索すると、対応するオブジェクトdeptsからインポートできます.オブジェクトをインポートしてdfs検索アルゴリズムを使用すると、サブノードに深くナビゲートできます.ナビゲーション時にキー値が「*」文字列の場合、配列にプッシュして出力すればよい.

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);