트라이는 단어의 글자를 간선으로 저장하는 트리입니다. 같은 접두사로 시작하는 단어는 앞부분 노드를 공유합니다.
검색은 입력 글자를 따라 내려가며, 끝 표시가 있는 노드라야 완성된 단어입니다. 자동완성은 접두사 노드 아래의 단어 끝을 수집하지만 후보가 많으면 결과 수를 제한해야 합니다.
언제 쓰나
접두사 검색, 자동완성, 라우팅 규칙에 유용합니다.
트라이 접두사 트리
Trie prefix tree
공유 접두사를 노드로 묶어 문자열을 글자 단위로 찾습니다.
···
<div class="v"><header><b>PREFIX TRIE</b><span id="state"></span></header><main><div class="query">prefix <b id="prefix">c</b></div><div class="words" id="words"></div></main><footer>shared prefix narrows matches</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .query{text-align:center;height:35%;padding-top:8px;color:var(--muted)}.query b{color:var(--accent);font:700 1.3em ui-monospace,monospace}.words{display:flex;justify-content:center;gap:6px;align-items:center;height:56%}.word{padding:7px;border:1px solid var(--line);border-radius:6px;font:600 .9em ui-monospace,monospace}.word em{font-style:normal;color:var(--accent)}let n=0;const prefixes=["c","ca","car"];function draw(){const p=prefixes[n];document.getElementById("prefix").textContent=p;document.getElementById("words").innerHTML=["car","cart","cat"].map(w=>"<div class=\"word "+(w.startsWith(p)?"":"muted")+"\"><em>"+w.slice(0,p.length)+"</em>"+w.slice(p.length)+"</div>").join("");document.getElementById("state").textContent="match "+[3,3,2][n];n=(n+1)%3}draw();setInterval(draw,1100)