9-1. 트리 알아보기
특징
- 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재함
- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐
- 트리의 부분 트리 역시 트리의 모든 특징을 따름
트리의 핵심 이론
트리의 구성 요소
- 노드: 데이터의 index와 value를 표현하는 요소
- 에지: 노드와 노드의 연결 관계를 나타내는 선
- 루트 노드: 트리에서 가장 상위에 존재하는 노드
- 부모 노드: 두 노드 사이의 관계에서 상위 노드에 해당하는 노드
- 자식 노드: 두 노드 사이의 관계에서 하위 노드에 해당하는 노드
- 리프 노드: 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
- 서브 트리: 전체 트리에 속한 작은 트리
9-2. 트라이
트라이(trie)
- 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조
트라이의 핵심 이론
- 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행함
특징
- N진 트리: 문자 종류의 개수에 따라 N이 결정됨
- 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지함
9-3. 이진 트리
이진 트리(binary tree)