트리의 개념
트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다.
트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사하다.
트리는 루트라는 하나의 데이터를 시작으로 여러개의 간선(Edge)로 연결된다. 각 데이터를 노드라고 하며 상위 노드를 부모 노드, 하위 노드를 자식 노드라고 부른다.
트리 내에는 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있기 때문에 재귀적 자료구조이기도하다.
컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있다. Root 폴더 아래에 여러개의 폴더가 자식 노드로 존재하고 자식 노드의 폴더에는 여러개의 파일 노드가 존재한다.
트리 관련 용어
트리의 구성요소
노드 (Node)
- 트리를 구성하고 있는 기본 요소
- 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.
- A, B, C, D, E, F, G, H, I, J
간선 (Edge)
- 노드와 노드 간의 연결선
루트 노드 (Root Node)
- 트리 구조에서 부모가 없는 최상위 노드
- root node : A
부모 노드 (Parent Node)
- 자식 노드를 가진 노드
- H, I에 부모 노드는 D
자식 노드 (Child node)
- 부모 노드의 하위 노드
- 노드 D의 자식 노드는 H, I
형제 노드 (Sibling node)
- 같은 부모를 가지는 노드
- H, I는 같은 부모를 가지는 형제 노드
외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 노드(leaf node)
- 자식 노드가 없는 노드
- H, I, J, F, G
내부 노드 (internal node, inner node), 비 단말 노드 (non-terminal node), 가지 노드 (branch node)
- 자식 노드 하나 이상 가진 노드
- A, B, C, D, E
깊이 (depth)
- 루트에서 어떤 노드까지의 간선(Edge) 수
- 루트 노드의 깊이 : 0
- D의 깊이 : 2
높이 (height)
- 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge) 수
- 리프 노드의 높이 : 0
- A 노드의 높이 : 3
깊이(depth)와 높이(height) 표현
Level
- 루트에서 어떤 노드까지의 간선(Edge) 수
Degree
- 노드의 자식 수
- Leaf node의 degree : 0; A의 degree : 2
Path
- 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
- A & H 경로 : A-B-D-H
Path Length
- 해당 경로에 있는 총노드의 수
- A & H 경로 길이 : 4
Size
- 자신을 포함한 자손의 노드 수
- 노드 B의 size : 6
Width
- 레벨에 있는 노드 수
- Level 2 width : 4
Breadth
- 리프 노드의 수
- Breadth : 5
Distance
- 두 노드 사이의 최단 경로에 있는 간선(Edge)의 수
- D와 J의 Distance : 3
Order
- 부모 노드가 가질 수 있는 최대 자식의 수
- Order 3 : 부모 노드는 최대 3명의 자식을 가질 수 있다.
트리 순회 알고리즘
전위 순회
[Root -> Left -> Right]
첫번째로 루트를 탐색하고 그 후에 왼쪽 노드, 오른쪽 노드로 탐색을 이어나가는 순회 방법이다. 자식 노드를 탐색할 때, 자식 노드가 서브 트리의 루트이면 그 서브 트리 내에서 다시, 루트 -> 왼쪽 노드 -> 오른쪽 노드 순서로 탐색을 이어 나간다.
중위 순회
[Left -> Root -> Right]
루트를 왼쪽 노드와 오른쪽 노드 중간에 탐색하는 순회 방법이다.
후위 순회
[Left -> Right -> Root]
왼쪽 노드와 오른쪽 노드를 탐색하고 루트를 제일 마지막에 순회하는 방법이다.
레벨 순회
가장 상위의 레벨부터 하위 레벨까지 왼쪽 노드에서 오른쪽 노드 순서로 트리를 순회하는 방법이다.
트리의 종류
이진 트리 (Binary Tree)
이진 탐색 트리
이진 탐색 트리는
