[박혜웅] 트라이 (trie)

• trie의 특징

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

    • 분기노드는 자식노드에 대한 포인터만 저장. 값 없음

    • 잎(데이타)노드에 데이타(문자열) 저장. 검색시 이 데이타가 키값임

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

  • tree와의 비교

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

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

 

• trie의 구조

  • trie의 구조와 삽입