트리 자료구조

	검색 시간복잡도	조작 시 시간복잡도 (insert, delete, update)
배열	O(logN) 정렬이 되어 있다고 가정	O(log N) + O(n) insert 시 위치 찾기 후 데이터 재정렬
연결리스트	O(n) 정렬 여부에 상관 없음	O(n)/O(1)+ O(1)
tree	O(logn)	O(logn)+ O(1)

• 연결리스트의 삽입 삭제 시 데이터를 이동하지 않는 장점을 살리면서 연결리스트의 검색 시 노드의 처음부터 찾아가야하는 단점을 보완
• 데이터를 중간부터 찾아가는 이진검색의 장점 이용!
• 연결리스트의 포인터를 리스트의 중간에 두는 방법을 선택
  • 이진 트리는 연결 리스트의 link 노드를 앞 뒤로 배치한다.
• ⇒ 검색을 중간부터 시작하여 좌우 중 하나로 분기, 0.5씩 검색 대산을 줄여나감으로써 이진검색의 효과를 얻는다.
•  

트리의 개념

트리의 정의

• 트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음 조건을 만족한다.
  1. 트리에는 root라고 부르는 특별한 노드가 있다.
  2. 다른 노드들은 원소가 중복되지 않는 n개의 부속 트리(sub tree)가 있다.
     1. T1, t2,…Tn으로 나누어지며 Ti는 각각 루트의 부속트리라고 부른다.

트리자료는 왜 필요할까?

• 트리 구조에 저장하면 더 효율적인 자료들이 있다.
• ex)
  • 계층적인 데이터 형태들은 트리에 저장하면 자연스럽게 표현된다
  1. 회사, 정부 조직 구조
  2. 나라, 지방, 시, 군별, 계층적인 데이터의 저장
  3. 인덱스

 

트리에 관한 용어

• 노드의 차수 : 노드의 부속 트리의 개수
• 트리의 차수 : 트리의 최대 차수
• 맆 노드 : 단말노드, 차수가 0인 노드, 맨 끝에 달린 노드들이다
• 내부 노드 : 차수가 1 이상인 노드
• 부모 : 부속 트리를 가진 노드
• 자식 : 부모에 속하는 부속 노드
• 형제 : 부모가 같은 자식 노드들
• 조상 : 노드의 부모 노드들의 총 집합
• 자손 : 노드의 부속 트리에 있는 모든 노드들
• 레벨 : 루트 노드들로부터 깊이(루트 노드의 레벨 =1)
• 트리의 깊이 : 트리에 속한 노드의 최대 레벨

 

트리구조를 컴퓨터 내부에 저장하는 방법

n-링크 표현법

• 노드에 n개의 링크를 두고 자식의 개수만큼 링크에 저장한다. 모든 노드는 자식 노드수에 관계 없이 최대 n개의 링크를 갖는다. 각 링크는 부속 트리가 저장된 곳을 링크한다.
• 차수가 n인 경우 표현된 노드
  • 참고 : 트리를 리스트 형태로 표현하는 방법 - 괄호를 사용하여 같은 레벨에 있는 노드들을 같은 괄호로 묶는다.

data link 1 link2 ….. link n

왼쪽 자식 노드-오른쪽 형제 노드 표현 방법

• 기억장소의 낭비가 커서 잘 쓰지 않는다.
• 모든 노드에 링크를 2개를 둔다.
• 첫째 링크는 첫번째 자식노드를 표현하고 둘째 링크는 자신의 오른쪽 형제 노드를 표현한다.
• 노드의 길이가 2개로 고정되기 때문에 n-링크 방법보다 간편하다.

차수가 n인 트리를 차수가 2인 트리로 저장하는 방법

• 트리를 왼쪽 자식 노드-오른쪽 형제 노드로 변환하여 그린 다음 4시계 방향으로 돌리면 된다.
• 모든 노드가 2개 이하의 자식 노드를 갖는다.
• 차수가 n인 트리가 차수가 2인 트리가 된다.(이진트리)

 

이진트리

• 자식 노드의 수가 2개 이하인 것을 이진트리 라고 한다.
• 대부분 응용에서 일반 트리보다는 원래부터 이진트리로 표현된 문제가 많다.
• 이진트리 : 유한개의 노드로 구성된 트리로
  1. 비어있거나
  2. 루트노드와 2개의 부속트리로 구성된다. 2개의 부속트리는 왼쪽 부속 트리, 오른쪽 부속 트리라고 부른다.
  • 노드가 없는 경우도 이진트리의 일종이다.
  
• 왼쪽과 오른쪽을 구분하기 때문에 다른 트리로 구분짓는다.

이진 트리의 성질

• 이진 트리는 자식의 개수가 2개 이하인 일반트리와 약간 다르다.
• 노드가 없는 트리도 이진트리가 된다.
• 부속 트리에 순서가 있다.
• 이진 트리의 최대 레벨이 i인 경우 트리의 최대 노드의 개수는 2^i-1이다.
• 이진트리의 맆 노드의 개수 n0와 차수 1인 노드의 개수 ni, 차수가 2인 노드의 개수 n2에 관한 다음의 등식 성립한다.
  • n0=n2+1
  1. n=n2+n1+n0
  2. n=2n2+121+0*n0+1
     • 전체노드 수는 자식 노드를 곱한 식에다 루트 노드 1을 더한다.

다양한 이진트리

스큐 이진트리

• 트리의 노드가 왼쪽이나 오른쪽으로 한쪽으로만 노드가 있는 트리이다.

포화 이진트리

• 트리의 깊이가 k(레벨을 1로 시작), 2^k-1 노드를 가진 이진트리

완전 이진트리

• n개의 노드를 가진 완전 이진트리는 포화 이진트리에서 노드에 1부터 n까지 번호를 붙였을 때 만들어진 트리이다.

Q 8.2

Question - 이진트리의 노드 수

(1) 깊이가 5인 이진트리의 노드의 최소개수는? 5개

(2) 깊이가 5인 이진트리의 노드의 최대 개수는? 41개

(3) 깊이가 5인 포화이진트리의 노드의 최소 개수는? 31개 ( 2kĸʞ³⁵-1 )

(4) 깊이가 5인 포화이진트리의 노드의 최대 개수는? 31개

(5) 깊이가 5인 완전이진트리의 노드의 최소 개수는? 16개

(6) 깊이가 5인 완전이진트리의 노드의 최대 개수는? 31개..?

(7) 이진트리에서 자식이 2인 노드의 개수가 4개 일때 맆노드의 개수는? 5개

이진 트리의 저장

배열을 이용한 저장

트리의 레벨 순서대로 배열에 저장을 해두는 방법이다. 트리의 노드를 레벨 순서대로 왼쪽에서 오른쪽으로 저장한다. 배열이름을 T[]라고 하면 루트노드는 T[0]에 레벨 2의 첫 노드는 T[1]에, 둘째 노드는 T[2]에 저장하는 방식이다.

배열에 저장할 경우 임의의 배열 원소의 부모와 왼쪽 오른쪽 자식을 찾는 함수는 다음과 같이 된다.

 

👉 1) 부모 노드의 위치 - parent(i) =(i-1) /2 if i≠0 parent(i)=0 if i=0 (루트 노드) 2) 왼쪽 자식의 위치 : left_child(i)=2*i+1 3) 오른쪽 자식의 위치 : right_child = 2*i+2

 

배열을 이용한 이진 트리 저장의 문제점

1. 배열의 이용하지 않는 저장 공간이 많다.
   • 깊이가 k인 트리에서 전체 필요한 공간은 S(k)=2^k-1이지만 skewed 이진 트리처럼 깊이에 비하여 노드 수가 적은 경우 기억 공간 활용율이 낮다.
   • complete 이진 트리의 저장에는 효과적이다.
2. 트리의 최대 깊이를 대비하여 많은 기억장소를 확보하고 트리가 예상보다 커지면 프로그램 수행을 종료해야 한다.

연결리스트를 이용한 이진트리 표현

1. 데이터
2. 왼쪽자식에 대한 포인터
3. 오른쪽자식에 대한 포인터

struct tnode{
	int data;
	struct tnode * left_child;
	struch tnode * right_child;};
typedef struct tnode node;
typedef node * tree_ptr;

• 힙 영역에서 필요한 영역만 빌려온다.
• 자식을 찾기 쉬우나 부모를 찾기는 어렵다.
  • 재귀 탐색(리커시브한 탐색)을 이용해야 한다.
  • 그래서 연결리스트 이진트리에는 순환 알고리즘이 많이 나온다. 전위, 후위 탐색 등이 많이 나온다.
  
• 참고! 이진트리를 연결리스트로 표현하는 다른 방법
  • 필드를 한 개 더 추가하여 부모노드에 대한 포인터를 저장한다. 그러나 트리를 다룰 때 링크를 3개씩이나 관리해야 하므로 복잡하여 잘 사용하지 않는다.
  

배열을 이용한 이진 트리 저장의 문제점

1. 배열의 이용하지 않는 저장 공간이 많다.
   • 깊이가 k인 트리에서 전체 필요한 공간은 S(k)=2^k-1이지만 skewed 이진 트리처럼 깊이에 비하여 노드 수가 적은 경우 기억 공간 활용율이 낮다.
   • complete 이진 트리의 저장에는 효과적이다.
2. 트리의 최대 깊이를 대비하여 많은 기억장소를 확보하고 트리가 예상보다 커지면 프로그램 수행을 종료해야 한다.

연결리스트를 이용한 이진트리 표현

1. 데이터
2. 왼쪽자식에 대한 포인터
3. 오른쪽자식에 대한 포인터

struct tnode{
	int data;
	struct tnode * left_child;
	struch tnode * right_child;};
typedef struct tnode node;
typedef node * tree_ptr;

• 힙 영역에서 필요한 영역만 빌려온다.
• • 재귀 탐색(리커시브한 탐색)을 이용해야 한다.
  • 그래서 연결리스트 이진트리에는 순환 알고리즘이 많이 나온다. 전위, 후위 탐색 등이 많이 나온다.자식을 찾기 쉬우나 부모를 찾기는 어렵다.
• • 필드를 한 개 더 추가하여 부모노드에 대한 포인터를 저장한다. 그러나 트리를 다룰 때 링크를 3개씩이나 관리해야 하므로 복잡하여 잘 사용하지 않는다.참고! 이진트리를 연결리스트로 표현하는 다른 방법

배열	연결리스트
저장이 편하다. int T[max]; 노드의 위치를 쉽게 알 수 있다. 첨자가 0부터 시작한다고 가정할 때 m 레벨의 k번째 노드의 인덱스 위치는 (2^m-1)+(k-1), 노드는 T[(2^m-1)+(k-1)]에 위치 치명적인 단점 : 기억장소가 많이 필요하다.	트리의 크기와 깊이에 관계 없이 노드 수 만큼의 데이터를 저장 트리의 크기가 증가하여도 기억 장소에서 노드를 동적으로 확보하여 트리를 구성 트리 전체를 탐색하는 알고리즘이 배열보다는 복잡하다. 일반트리도 이진 트리로 변형하여 저장하는 것이 더 효율적이다.

 

Q 8.4

struct tnode {
int data;
struct tnode *left_child;
struct tnode *right_child;};

typedef struct tnode node;
typedef node *tree_ptr;

...
tnodes[i] =(tree_ptr)malloc(sizeof(node));
tnodes [i] ->data=number[i];
tnodes[i]->left_child = tnodes [i] —>right_child =NULL;
...
..

tree_ptr insert(tree_ptr head, int *number) {
tree_ptr tnodes [5] ; 
tree_ptr temp—NULL; 
int i=0; 
for(i=0;i<5, i++){
tnodes[i]=(tree_ptr)malloc(sizeof(node)); 
tnodes [i]->data=number[i] ; 
tnodes [i] —>left_child = tnodes [i] —>right_child =NULL;}

head=tnodes [0] ; 
tnodes [0] ->left_child=tnodes[1] ; 
tnodes [0]->right_child=tnodes[2] ; 
tnodes [1]->right_child = tnodes [3] ; 
tnodes [2]->left_child = tnodes[4] ; 
return head; }