[Data Structure] 7. 트리

이 카테고리에 정리된 내용은 강의시간에 필기한 내용이 주를 이룹니다. 교수님께서 강의 하신 내용들 중에 핵심들과 부가적인 내용들을 요약하여 게시했습니다. 강의시간에 생능출판사의 C언어로 쉽게 풀어쓴 자료구조 책을 사용했기 때문에 정리하는 순서도 이 책의 순서에 따라 하기로 했습니다. 순전히 정리용이기 때문에 시험기간이나 복습용으로는 적절하지만 순수한 학습용으로는 적절하지 않을 수 있습니다.

목록보기

 

7.1 트리의 개념

– 트리 : non-linear data type. 그래프의 특수한 형태. 계층구조(hierarchical structure)를 띔. 여러 노드가 한 노드를 가리킬 수 없음.

– 트리의 정의

1. 최소 하나의 root 필요.

2. 임의의 노드는 subtree를 n개 까지 가질 수 있다.

3. oriented tree: 근원만 같다면 동일 트리로 간주.

– 차수(degree) : 자식 노드의 개수.

– 트리의 구성요소

1. root

2. subtree : root를 제외한 모든 노드

3. edge : 노드들을 연결하는 선

4. leaf node(terminal node) : 차수가 0인 노드

5. branch node : 차수가 0이 아닌 노드

– 트리를 배열에 넣는 방법

1. 트리의 가장 큰 degree를 구함.

2. 첫 번째 인덱스에는 루트 삽입.

2. 두 번째 인덱스부터 degree만큼의 공간이 할당.

 

7.2 이진트리(binary tree)

– 이진트리의 정의

1. 모든 노드가 비어있어도 이진트리이다.

2. subtree의 개수는 0~2개이다.

3. ordered tree : 순서가 바뀐다면 다른 트리로 간주한다.

4. 각 subtree도 순환적으로 subtree를 갖는다.

– edge의 개수 : 전체 노드의 개수 – 1

– 이진트리 분류

1. 포화이진트리(full binary tree) : 정 이진트리. 트리의 각 레벨의 노드가 꽉 차있는 이진트리. level i의 node 수가 2^i -1 개인 것

2. 완전이진트리(complete binary tree) : 전 이진트리. root로부터 level 순으로 좌->우로 순서대로 memory에 저장할 때 빈 공간 없이 저장되는 이진트리.

 

7.3 이진트리의 표현

– 배열표현

1. i의 부모노드 인덱스 = i/2

2. i의 왼쪽 자식노드 인덱스 = 2i

3. i의 오른쪽 자식노드 인덱스 = 2i+1

– 링크 표현 : 왼쪽, 오른쪽 각각의 링크 필드를 가짐.

 

7.4 이진트리의 순회( 스택 사용)

– 순회(traversal)

1. 전위 순회(preorder) : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 방문

2. 중위 순회(inorder) : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문

3. 후위 순회(postorder) : 왼쪽서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문

 

7.6 스레드 이진트리(threaded binary tree)

-스레드 이진트리 : 중위순회 후 NULL링크가 있는 노드의 오른쪽 노드를 채우는 트리.

 

7.7 이진탐색트리 (binary search tree)

– 이진탐색트리 : 탐색시간을 O(n) -> O(log2n)으로 만들기 위한 알고리즘.

– 이진탐색트리 정의

1. 모든 원소의 키는 유일하다

2. 왼쪽 서브트리의 키들은 루트의 키보다 작다

3. 오른쪽 서브트리들의 키들은 루트의 키보다 크다

4. 왼쪽과 오른쪽 서브트리도 각각 이진탐색트리이다.

목록 보기