트리 - 트리 알아보기, 트라이

트리는 노드와 엣지로 연결된 그래프의 특수한 형태입니다.

 

트리의 특징

• 순환 구조(사이클)를 지니지 있지 않고, 1개의 루트 노드가 존재합니다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖습니다.
• 트리의 부분 트리 역시 트리의 모든 특징을 따릅니다.

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
엣지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
서브 트리	전체 트리에 속한 작은 노드

 

트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다.

 

트라이의 핵심 이론

트라이는 일반적으로 단어들을 사전 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행합니다.

 

트라이의 특징

• N진 트리: 문자 종류의 개수에 따라 N이 결정 된다.
• (예를 들어 알파벳은 26개의 문자로 이루어져 있으므로 26진 트리로 구성된다.)
• 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다.