Tree(트리)

계층적 자료를 표현하는데 사용하는 자료구조이다.
실제 나무를 거꾸로 한 것과 같은 모양이다.

용어

• 노드 : 데이터를 저장하는 기본적 단위
• 루트 노드 : 최상위 노드
• 단말 노드 : 자식이 없는 노드
• 내부 노드 : 단말 노드가 아닌 노드
• 간선 : 노드와 노드를 연결하는 선 (경로라고도 함)
• 형제 : 같은 부모를 가지는 노드
• 크기 : 자신을 포함한 자손의 노드 수
• 깊이 : 루트에서 부터의 간선의 수
• 레벨 : 특정 깊이를 가지는 노드의 집합
• 보조 트리 : 전체 트리에 속하는 작은 트리

특징

1. 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다.
2. 트리의 구조는 저장보다 효과적인 탐색을 위한 구조이다.
3. 트리는 방향성이 있는 비순환 그래프(DAG)로 loop, circuit과 같은 사이클이 없다.
4. 루트에서 특정 노드로 가는 경로는 유일하다.
5. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.

종류

삼항 트리

최대 3개의 하위 노드를 갖는 트리 구조

이진 트리

최대 2개의 하위 노드를 갖는 트리

• 이진 검색 트리 : 부모의 왼쪽에는 부모보다 작은 값, 오른쪽은 큰 값 + 중복이 없는 이진 트리
• 완전 이진 트리 : 왼쪽에서 오른쪽으로 순서대로 차곡차곡 쌓여있는 이진 트리
• 포화 이진 트리 : 모든 노드의 차수가 2이고 동일 레벨이 가득 차 있는 이진 트리
• 전 이진 트리 : 모든 노드의 차수가 2, 0만 존재하는 이진 트리
• 편향 이진 트리 : 모든 노드가 부모의 왼쪽이나 오른쪽 한 방향으로 편향된 이진 트리

이진트리의 종류는 이진트리에서 자세히 작성할 예정이다.