비선형 자료구조1 (트리)

안녕하세요

 

게임개발자가 되기위해 공부하고 있는 구구입니다.

오늘부터는 비선형 자료구조에 대해 알아보도록 하겠습니다.

---

• 트리

- 자료간의 관계가 계층 구조일 때 사용하는 비선형 자료구조

- 복잡하고 많은 파일들을 쉽게 정리

- 목적, 계획, 계층, 중요도에 맞게 나열 가능

 

- 노드로 이루어진 자료구조

- 하나의 루트 노드를 가짐

- 0개 이상의 자식 노드를 가짐

- 그 자식노드 또한 0개 이상의 자식노드를 가지고 이는 반복적으로 정의됨

 

 

 

• 트리 특징

- 그래프의 한 종류

- 최소 연결 트리

- 계층 모델

- DAG(Directed Acycle Graphs, 방향성 있는 비순환 그래프)의 한 종류

- 노드가 N개인 트리는 항상 N-1개의 간선(edge)를 가짐

- 루트에서 어떤 노드로 가는 경로는 유일

- 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한개의 부모 노드만을 가짐

- 순회는 Pre-order, In-order 아니면 Post-order 로 이루어짐

- 트리는 이진트리, 이진 탐색 트리, 균형 트리, 이진 힙

 

 

 

• 이진 트리

이진 트리: 노드의 최대 브랜치가 2인 트리. 즉, 자식 노드가 최대 2개인 트리

 

이진 탐색 트리(Binary Search Tree, BST): 이진 트리이면서, 왼쪽 노드가 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값인 조건을 만족하는 트리. 탐색 시 시간 복잡도는 O(log n)

 

포화 이진 트리(Full Binary Tree): 모든 노드가 2개의 자식 노드를 가지면서 모든 리프 노드가 동일한 레벨을 갖는 트리

 

완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 모든 리프 노드가 왼쪽에 있는 이진 트리. 노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입하는 트리

 

 

• 이진 트리의 순회

- 이진트리의 모든 노드를 특정한 순서대로 한번씩 방문하는 것

- 깊이우선탐색(DFS)와 너비우서탐색(BFS)안에 있음

 

 

 

1. 전위 순회(깊이 우선 순회)

- 노드를 방문

- 왼쪽 서브 트리를 전위 순회

- 오른쪽 서브 트리를 전위 순회

- (root, left. right)

 

 

2. 중위 순회(대칭순회)

- 왼쪽 서브트리를 중위 순회

- 노드 방문

- 오른쪽 서브트리를 중위 순회

- (left, root, right)

 

 

 

3.후위 순회

- 왼쪽 서브 트리를 후위 순회

- 오른쪽 서브 트리를 후위 순회

- 노드를 방문

- (left, right, root)

 

 

 

• 트리 관련 용어

루트 노드	부모가 없는 노드(Level 0)
리프 노드(말단 노드, 터미널 노드)	자식이 없는 노드
간선(링크, 브랜치)	노드를 연결하는 선
형제 노드	같은 부모를 가진 노드
부모 노드	어떤 노드의 상위 레벨에 연결된 노드
자식 노드	어떤 노드의 다음 레벨에 연결된 노드
레벨	루트 노드를 기준으로 하위에 연결된 노드의 깊이
깊이(Depth)	트리에서 노드가 가질 수 있는 최대 레벨