본문으로 바로가기

2021.05.27 - [전체글] - 화일 처리 및 응용 공부 #15 (B*트리)


 

트라이(Trie)

  • 키를 구성하는 문자나 숫자의 순서를 이용해 키 값을 검색하는 자료구조
    - m 진 트리 이지만 m원 탐색 트리는 아님 : 키 값의 배열 순서가 다름
  • m진 트라이
    - 차수 m : 키 값을 표현하기 위해 사용하는 문자의 수

    - m진 트라이 : m개의 포인터를 표현하는 1차원 배열
  • 10진 트라이의 노드 구조

10진 트라이 노드 구조

 

키 7302 을 탐색할떄 다중포인터 마냥 쭉 따라가 마지막 키값의 주소에 담긴 값을 리턴

  • 트라이의 높이 = 키 필드의 길이
  • 10진 트라이의 레벨 j의 포인터 pi는 j번째 에 숫자가 i인 모든 키값을 나타내는 서브트리를 가리킴
       e.g 레벨 3에 있는 p4는 키값의 3번째 숫자가 4인 키값을 가진 서브트라이를 가리킴
  • 키 값 : 루트 노드의 pi 에서 리프 노트의 pj 까지의 경로를 각 포인터에 대응하는 기수 원소로 표현
  • 리프 노드에는 해당 키 값을 가진 레코드의 주소가 저장
  • 키 검색 뿐만 아니라 키의 존재 유무를 빠르게 결정
  • 트라이에서 널 포인터만 가지고 있는 공백노드는 생성 안함

트라이 연산

트라이에서 연산 과정


 


댓글을 달아 주세요