트리 (Tree)

개념
트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음과 같은 조건을 만족함. (1) 트리에는 루트(root)라고 부르는 특별한 노드가 있음. (2) 다른 노드들은 원소가 중복되지 않는 n개의 부속트리(subtree)로 나누어짐.

I. 트리 (Tree)의 개요

가.  트리의 정의

- 트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음과 같은 조건을 만족함.

(1) 트리에는 루트(root)라고 부르는 특별한 노드가 있음.

(2) 다른 노드들은 원소가 중복되지 않는 n개의 부속트리(subtree)로 나누어짐.

 

나.  트리의 특징

- 계층적인 데이터 형태를 저장하기에 적합함. (조직구조, 지역구분 등)

- 인덱스 파일의 생성에 적합함.

 

Ⅱ. 트리의 관련된 용어 및 트리 순회 방식

가.  트리에 관련된 용어

용어

설명

한글

영어

노드의 차수

degree

노드의 부속 트리의 개수

트리의 차수

degree of tree

트리의 최대 차수

단말 노드

leaf, terminal

차수가 0인 노드, 즉 맨 끝에 달린 노드

내부 노드

internal

차수가 1이상인 노드

부모

parent

부속 트리를 가진 노드

자식

child

부모에 속하는 부속 노드

형제

sibling

부모가 같은 자식 노드들

조상

ancestor

노드의 부모 노드들의 총 집합

자손

descendant

노드의 부속 트리에 있는 모든 노드들

레벨

level

루트 노드들로부터 깊이

트리의 깊이

depth of tree

트리에 속한 노드의 최대 레벨

 

나.  트리 순회 방식

방식

트리 순회 순서

방향 및 표식

전위

(Preorder)

중위

(Inorder)

후위

(Postorder)

 

Ⅲ. 이진 트리 (Binary Tree)의 개요

   가.  이진 트리의 정의

- 노드의 차수(degree)가 2 이하로 구성된 트리

 

나.  이진 트리의 특성

- 깊이가 k인 이진 트리의 최대 노드의 수: 2k-1

- 이진 트리의 레벨 i에서 최대 노드의 수: 2(i-1)

- n0 = n2 + 1  (n0 : 이진 트리의 터미널노드,  n2 :차수가 2인 노드 수)

 

Ⅳ. 이진 트리의 저장

가.  배열을 이용한 저장

- 트리의 레벨 순서대로 배열에 저장하는 방법

- T[] 배열에 루트노드는 T[0]에, 레벨2의 첫째노드는 T[1]에,,, 저장하는 방식

 

(1)   부모 노드의 위치: parent(i) = (i-1)/2  (단, i=0 인 경우는 parent(i) = 0)

(2)   왼쪽 자식의 위치: left_child(i) = 2*i +1

(3)   오른쪽 자식의 위치: right_child(i) = 2*i +2

 

나.  연결 리스트를 이용한 저장

- 데이터, 왼쪽 자식에 대한 포인터, 오른쪽 자식에 대한 포인터로 구성하는 방법

 

struct tnode {

int data;

struct tnode * left_child;

struct tnode * right_child;

};

typedef struct tnode node;

typedef node * tree_ptr;

 

다.  이진 트리 저장 방식의 비교

배열을 이용한 저장

연결리스트를 이용한 저장

- 저장이 편함.

- 노드의 위치를 쉽게 알 수 있음.

- 트리의 크기와 깊이에 관계없이 노드 수 만큼의 데이터를 저장함.

- 트리 전체를 탐색하는 알고리즘이 배열보다 복잡함.

 

Ⅴ. AVL 트리의 개요

  가.  AVL 트리의 정의

- 좌우 서브트리의 높이 차이가 1이하인 이진 탐색 트리

 

나.  AVL 트리의 특성

- O(log N)의 검색 성능 보장

- AVL 형태로 트리 유지

- Balanced Factor: +1,0,-1 경우만 허용, 그 외의 경우는 Rotation

 

Ⅵ. AVL 트리의 회전

  가.  AVL트리의 회전방식

    11.JPG

 

  나. LL 회전

6.JPG

 

  다.  LR 회전

12.JPG

 

라.  RL 회전

23.JPG

 

 마.  RR 회전

    55.JPG

 

 

 

댓글