본문 바로가기

자료구조 & 알고리즘/트라이(Trie)

[박혜웅] 트라이 (trie)

  • trie의 특징

    • 분기(내부)노드와 데이타(외부,잎)노드로 구성

      • 분기노드는 자식노드에 대한 포인터만 저장. 값 없음
      • 잎(데이타)노드에 데이타(문자열) 저장. 검색시 이 데이타가 키값임

        • 문자열대신 텍스트에서의 위치로 저정해도 됨.
    • reTRIEval 에 유용하다고 하여 Fredkin이 명명함
    • tree와의 비교

      • 키 비교: tree는 key의 전체를 비교하지만 trie는 key의 일부만 비교한다. 따라서 비교속도가 빠르다.

        • 일부만 비교한다는 것은 문자열비교가 아니라, 글자 또는 비트의 비교를 의미한다.
        • trie도 leaf node에서는 키값 전체를 비교해야 한다.
      • 키값이 없는 경우: tree는 leaf까지 가야 값이 존재하는지 확인이 가능하다. 하지만 trie는 leaf이전에 확이 가능하다

 

  • trie의 구조

    • trie의 구조와 삽입