[알고리즘] 트리(Tree)

이번에 알아볼 알고리즘은 트리인데요! 트리는 방향성이 있는 '그래프'입니다.

트리는 방향성이 있기에 하나의 루트 노드가 존재합니다.

트리 순회(임의의 한 정점에서 시작하여 모든 정점을 한 번씩 방문)에는 DFS,BFS 중 Pre-,In-Post-Order 등이 있습니다.

트리의 예시로는 이진 트리, 이진 탐색 트리, 균형 트리, 이진합 등이 있습니다.

트리(Tree)

용어

1. 루트 노드 ; 부모가 없는 노드

2. 단말 노드(=말단 노드, 잎 노드) ; 자식 노드가 없는 노드

3. 내부 노드 ; 단말 노드가 아닌 노드

4. 간선(=link,branch) ; 노드를 연결하는 선

5. 형제 ; 같은 부모를 가지는 노드

6. 노드의 크기 ; 자신을 포함한 모든 자손 노드의 개수

7. 노드의 깊이(레벨) ; 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

8. 노드의 차수 ; 하위 트리 개수 / 간선 수 = 각 노드가 지닌 가지의 수

9. 트리의 차수 ; 트리의 최대 차수

8. 트리의 높이 ; 루트 노드에서 가장 깊숙히 있는 노드의 깊이. 트리의 최대 레벨 + 1

9. 포리스트 ; 트리들의 집합

 

특징

- 그래프의 한 종류로, '최소 연결 트리' 라고도 불림

- 계층 모델임(계층을 가짐)

- DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류로, 사이클이 없음

- 노드가 N개인 트리는 항상 N-1개의 간선을 가짐

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

- 구성 ; Pre-order, In-order, Post-order. 이 모두 DFS/BFS 안에 있음

- 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대 힙, 최소 힙) 등이 있음

 

이진 트리

; 최대 2개의 자식을 갖는 트리

▶ 중위 순회(on-order traversal) ; 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지

▶ 전위 순회(pre-order traversal) ; 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지

▶ 후위 순회(post-order traversal) ; 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드

 

이진 탐색 트리(BST, Binary Search Tree)

모든 노드가 "모든 왼쪽 자식들 <= 부모 노드 < 모든 오른쪽 자식들" 특징 순서를 따르는 이진 트리

- 모든 키를 정렬된 순서로 가져올 수 있음

ex) {50,15,62,80,7,54,11}를 이진 탐색트리로 표현한 트리

// postorder.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define  YES 1
#define  NO  0
#define  NUL 0

#define LIST struct list
LIST {
     char *data;
     LIST *nleft;
     LIST *nright;
};

LIST *node(LIST *rp, char *ndata);
int  inp(char *idata);
LIST *nalloc();
char *strsv(char *sl);
void prn(LIST *pp);


int main(int argc, char* argv[])
{
    LIST* root;
 char dat[15];
 int  key;
 
 root = NUL;
 do {
    printf("\n input-1    display-2      end-6 \n");
    printf("\n key -->");
    scanf("%d", &key);
    if (key == 1) {
       printf("\n -----------  input  ------------ ");
       printf("\n -------------------------------- ");
       printf("\n --- If data is q then exit.. --- ");
       printf("\n -------------------------------- ");
       while ( inp(dat) == NO)
	   {
	     root = node(root, dat);
	   }
    }
    if (key == 2) {
       printf("\n -------- display  data --------- \n");
       prn(root);
    }
    if (key == 6) {
       printf("\n -----------   end   ------------ \n");
       break;
    }
 } while (key == 1 || key == 2 || key == 6);

   return 0;
}

LIST *node(LIST *rp, char *ndata)
{
 LIST *nalloc();

 int cmp;
 if (rp == NUL) {
    rp = nalloc();
    rp->data = strsv(ndata);
    rp->nleft = rp->nright = NUL;
 }
 else if ((cmp = strcmp(ndata, rp->data)) == 0) {
	 printf("\n ------------------------------------------- \n");
	 printf("    DATA = %-15s \n", rp->data);
	 printf("\n ------------------------------------------- \n");
 }
 else if (cmp < 0)
      rp->nleft = node(rp->nleft, ndata);
 else
      rp->nright = node(rp->nright, ndata);
 return(rp);
}


int inp(char *idata)
{
 printf("\n  data   -->");
 scanf("%s", idata , 15);
 if (*idata == 'q' || *idata == 'Q')
    return(YES);
 return(NO);
}

LIST *nalloc()
{
  return((LIST*) malloc(sizeof(LIST)));
}

char *strsv(char *sl)
{
 char *p;
 int n = strlen(sl) + 1;
 if ((p = (char *)malloc(n)) != NUL)
    strcpy(p, sl);
 return(p);
}


void prn(LIST *pp)
{
 if (pp != NULL) {
	 prn(pp->nleft);
     printf("%-15s \n", pp->data);
	 prn(pp->nright);
	
	
  }
}

 

완전 이진 트리(Complete Binary Tree)

; 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리, 즉 마지막 레벨을 제외하고 모든 레벨이 완전이 채워짐

- 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 함

- 마지막 레벨 h에서 (1~2h-1)개의 노드를 가질 수 있음

 

전 이진 트리(Full Binary Tree)

; 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

포화 이진 트리(Perfect Binary Tree)

; 전 이진 트리 + 완전 이진 트리

- 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 함

- 모든 내부 노드가 두 개의 자식 노드를 가짐

- 모든 말단 노드가 동일한 깊이 또는 레벨을 가짐

- 노드의 개수 ; (2^k)-1 (k ; 트리의 높이)

 

경사 이진트리

; 왼쪽 또는 오른쪽으로 편향되게 채워져 있는 트리

 

일반이진트리

; 차수가 2 이하인 이진트리

 

 

이진 힙

; 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

- 여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

- 일종의 반정렬 상태(느슨한 정렬 상태) 유지 ; 큰 값이 상위 레벨에, 작은 값이 하위 레벨에

- 중복된 값 허용(이진 탐색 트리에서는 허용 x)

▶ 최대 힙(Min Heap)

; 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리(내림차)

 

▶ 최소 힙(Max Heap)

; 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리(오름차순)

- N개가 힙에 들어가 있으면 높이는 log(N)

 

---

 

 

트리의 구현 방법

▶ 인접 배열 이용

1. 1차원 배열에 자신의 부모 노드만 저장하는 방법 => 부모 노드를 0개 ; 루트 노드

2. 이진 트리의 경우 2차원 배열에 자식 노드를 저장 => A[i][0] ; 왼쪽 자식 노드, A[i][1] ; 오른쪽 자식 노드

- 부모 노드에 대한 접근이 용이

- 정이진트리의 경우 기억장소 낭비 없음

- 순차적인 구조로 표현할 경우 기억장소의 낭비 초래

- 데이터의 추가와 삭제 시 많은 데이터 이동 필요

- 부모 노드 = i/2 , 왼쪽 자식 노드 = 2i, 오른쪽 자식 노드 = 2i+1

 

▶ 인접 리스트 이용

1. 가중치 없는 트리의 경우

ArrayList<ArrayList> List=new ArrayList<>();

2. 가중치 있는 트리의 경우

classNode{int num,dist; //노드 번호, 거리}

ArrayList[] List=new ArrayList[정점의 수+1];

- 트리의 노드 차수에 따라 각 노드는 차수만큼의 링크필드 필요

- k진트리는 n*k개의 링크가짐 -> nk-(n-1) 개의 NULL link가짐 -> 기억장소의 낭비 많음

 

트리의 운행

-  Inorder(중위순회) : left> root> right

-  Preorder(전위순회) ; root> left> right

-  Postorder(후위순회) ; left> right> root

 

 

---

 

쓰레드 이진트리

; 이지트리에서 2n개의 전체링크와 n+1개의 NULL link를 가지며, 사용되지 않는 NULL link를 tree의 운행에 이용

- bit=1 ; 정상연결, 0 ; 비정상연결 ->트리의 운행시 특정 노드에 대한 직전, 직후 노드에 대한 정보 제공

* 빈 링크 ; 처리순서에서 현재노드 좌/우를 작성

예시)

node	Llink	Rlink	Lbit	Rbit
a	b	c	1	1
b	d	e	1	1
c	a	f	0	1
d	null	b	0	0
e	b	a	0	0
f	c	null	0	0

위는 in-order방식을 쓰레드 이진트리로 나타낸 것