참고자료
- https://chanhuiseok.github.io/posts/ds-3
- https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree
- https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0
- https://rosweet-ai.tistory.com/55
- https://elisha0103.tistory.com/20
1. 트리(Tree)란?
자료구조의 생김새가 마치 뒤집어 놓은 나무 같다고 해서 붙여진 이름이다.
List처럼 선형 구조가 아닌 비선형 구조로써
- 원소들 간 계층 관계를 가지는 "계층형 자료 구조"
- 상위 원소에서 하위 원소로 내려가면서 확장되는 "나무 모양의 구조"
라 볼 수 있다.
2. 트리의 구조와 용어
1) 구조
- 노드(node) : 위 그림의 검정색 동그라미, 데이터가 담기는 대상
- 간선(edge) : 노드와의 관계를 표시하는 선
- 노드 A가 노드 B를 가리킬 때
- A는 B의 부모 노드(parent node)
- B는 A의 자식 노드(child node)
- 노드 A가 노드 B를 가리킬 때
- 루트 노드(root node) : 부모 노드가 없는 최상위 노드
- 잎 노드(leaf node) : 자식 노드가 없는 노드
- 내부 노드(internal node) : 잎 노드가 아닌 노드
- 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
- 형제 노드(Sibling node) : 트리의 같은 레벨선상에 있는 노드들
2) 관련 용어 예시
- 노드(node) : 1, 2, 3, 4, 5
- 간선(edge) : 1-2, 1-3, 2-4, 2-5
- 루트 노드(root node) : 1
- 잎 노드(leaf node) : 3, 4, 5
- 내부 노드(internal node) : 1, 2
- 형제 노드(Sibling node)
- 1번 부모에게서 나온 2번, 3번끼리 형제 노드
- 2번 부모에게서 나온 4번, 5번끼리 형제 노드
- 조상 노드(Ancestor node) : 간선을 따라 루트 노드까지 가는 경로상에 있는 모든 노드들
- 5번의 조상 노드는 2번, 1번
- 자손 노드(Descendent node) : child node라고도 하며, 2번의 자손 노드는 4번과 5번
- 차수(degree) : 노드에 연결된 자식 노드의 수
- 1의 차수는 2
- 2의 차수는 2
- 높이(height) : root node에서 leaf node에 이르는 가장 긴 경로의 엣지 수
- 4번과 5번의 높이가 2로 가장 크므로 트리의 높이는 2
3. 트리의 속성
루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 가진다. 이 속성 때문에 트리는 다음과 같은 성질을 만족한다.
- 임의의 노드에서 다른 노드로 가는 경로는 유일이다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 간선을 하나 자르면 트리가 두 개로 분리된다.
- 간선의 수 는 노드의 수에서 1을 뺀 것과 같다.
1) 속성 예시
(1) 회로
위 두 예시는 회로가 존재하기 때문에 트리가 아니다.
(2) 유일
1에서 4로 가는 경로가 유일하지 않기 때문에 트리가 아니다.
(3) 연결
연결되지 않은 노드가 존재하기 때문에 트리가 아니다.
4. 트리의 용도
일상 생활에서 볼 수 있는 '윈도우 탐색기', '가계도', '조직도', '토너먼트 대진표' 등이 있고 '데이터베이스 모델', '프로그램의 구문' 등 컴퓨터의 자료 처리에도 쓰인다.
5. 트리의 종류
1) 이진 트리(Binary Tree)
- 차수가 2 이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리
(1) 정 이진 트리(Full binary tree)
- 각 내부 노드가 두 개의 자식 노드를 갖는 순서화된 트리
(2) 완전 이진 트리(Complete binary tree)
- 부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 트리
(3) 포화 이진 트리(Perfect binary tree)
- 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
(4) 균형 이진 트리(Balanced binary tree)
- 왼쪽 자식, 오른쪽 자식 노드의 갯수가 정확하게 일치해야 할 필요는 없지만 지나치게 한쪽으로 치우치지 않은 트리
(5) 변질 이진 트리(Degenerate binary tree)
- 각 부모 노드가 오직 한 개의 연관 자식 노드를 갖는 트리
2) 이진 탐색 트리(Binary Search Tree)
- 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리
- 모든 노드의 왼쪽 서브 트리는 노드의 값보다 작은 값만 가지고, 모든 노드의 오른쪽 서브 트리는 노드의 값보다 큰 값들만 가지는 트리
- 이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제를 가능하게끔 고안됨
(1) 균형 잡힌 이진 탐색 트리
- 노드가 추가, 삭제될 때, 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리
1. AVL 트리
- Adelson-Velsky and Landis Tree라 불린다.
- 두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형을 잡는 이진 탐색 트리
2. 레드-블랙 트리
- 각 노드는 빨강 또는 검정의 색상을 가지고 있으며, 색깔에 따른 규칙을 통해 스스로 균형을 잡는 이진 탐색 트리
- 노드가 추가, 삭제될 때, 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리
늦깎이 애아빠 개발지망생