Tree
1. 개념
- 나무를 거꾸로 뒤집어 놓은 듯한 구조
- 그래프의 여러 구조 중 무방향 그래프의 한 구조로 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
- 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조
- 아래로만 뻗어나가기 때문에 사이클이 없음
- 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결
- 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가짐
- 깊이와 높이, 레벨 등을 측정할 수 있음
2. 관련 용어
- 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
- 루트(Root) : 트리 구조의 시작점이 되는 노드
- 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
- 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
- 리프 노드(leaf Node) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드
3. 특징
1) 깊이 (depth)
- 루트로부터 하위 계층의 특정 노드까지의 깊이(depth) 표현 가능
- 루트 노드 : 깊이 0에서 시작
2) 레벨(Level)
- 같은 깊이를 가지고 있는 노드의 묶음
- depth가 0인 루트의 level은 1
- 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node)라고 함
3) 높이(Height)
- 리프 노드를 기준으로 루트까지의 높이(height)
- 리프 노드와 직간접적으로 연결된 노드의 높이를 표현
- 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이
- 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 함
4) 서브 트리(Sub tree)
- 트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리
이진 트리 및 이진 탐색 트리
- 이진 트리(binary tree) : 자식 노드가 최대 2개인 노드들로 구성된 트리
*왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있음 - 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉨
- Balnced Tree : 모든 leaf node의 level 차이가 최대 1인 트리로 트리의 주 목적인 '탐색'을 위한 AVL tree, red-black tree 와 같은 자료구조들의 기반이 됨
1. 이진 트리(binary tree)
1) 정 이진 트리(Full binary tree)
- 각 노드가 0 개 혹은 2 개의 자식 노드를 갖음
2) 포화 이진 트리(Perfect binary tree)
- 정 이진 트리이면서 완전 이진 트리인 경우
- 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
3) 완전 이진 트리(Complete binary tree)
- 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함
2. 이진 탐색 트리 (Binary Search Tree)
- 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐
- 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있음
- 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가해야 함
Tree traversal
- 트리 순회 : 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
- 트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 존재
1. 전위 순회
25 > 20 > 10> 5 > 12 > 22 > 36 > 30 > 28 > 40 > 38 > 48
- 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색
2. 중위 순회
5 > 10 > 12 > 20 > 22 > 25 > 28 > 30 > 36 > 38 > 48 > 40
- 루트를 가운데에 두고 순회
- 제일 왼쪽 끝에 있는 노드부터 순회하기 시작
- 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 탐색
3. 후위 순회
5 > 12 > 10 > 22 > 20 > 28 > 30 > 38 > 48 > 40 > 36 > 25
- 루트를 가장 마지막에 순회
- 제일 왼쪽 끝에 있는 노드부터 순회하기 시작
- 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문
✏️