SelfStudyBook(3)-Tree

Chapter 6. 트리(Tree)

x의 형제가 누구인지 묻는 문제.

x의 부모는 y이고 y의 부모는 w이다.
t와 n은 w의 자손이다. 등

주어진 자료를 어떻게 저장하는 것이 효율적일까?

위와 같은 구조는 마치 나무와 같다. 프로그래밍에서는 이것을 트리라는 용어로 부른다. 트리의 개념은 다음과 같다. 자료들 사이가 1:n (n>=0)의 관계를 가지며 부분 집합도 재귀적으로 같은 정의가 적용되는 자료의 구조를 뜻한다.

이러한 트리 구조를 통해 다음과 같은 질문에 답할 수 있다.

자손이 없는 사람은 몇 명인가?
자손이 가장 많은 사람은 누구이며 몇 명인가?
부모와 자손을 한 세대라고 하면 가장 긴 세대는 몇 세대인가?
가장 긴 세대의 부모와 자손을 나열해 보자
전체 가족 구성원을 빠짐없이 나열해 보자
트리 구조가 아니라면 위의 질문에 쉽게 답할 수 있을지 생각해보자.

6.1 대표문제. 중위순회

중위순회(in-order) 형식으로 순회하여 각 노드를 읽으면 원래 단어를 알 수 있다고 한다.

위 트리를 중위순회 형식으로 순회할 경우 SOFTWARE라는 단어를 읽을 수 있다.

트리

트리란 무엇일까? 추상화된 개념을 아래와 같이 정리할 수 있다.

비선형 구조
원소들 간에 1:n 관계를 가지는 자료구조
원소들 간에 계층관계를 가지는 계층형 자료구조
상위 원소에서 하위 원소로 내려가면서 확장되는 트라 모양의 구조

트리의 정의

한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.

노드 중 최상위 노드를 루트(root)라 한다.
나머지 노드들은 n(n >= 0)개의 분리 집합 T1,…,TN으로 분리될 수 있다.
이들은 T1,…,TN은 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리(subtree)라 한다.

트리 용어 정리

노드 : 트리의 원소
간석(edge) : 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
루트 노드 : 트리의 시작 노드
형제 노드 : 같은 부모 노드의 자식 노드들
조상 노드 : 간선에 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
자손 노드 : 서브 트리에 있는 하위 레벨의 노드들
노드의 차수 : 노드에 연결된 자식 노드의 수
트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
단말 노드(리프 노드) : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨

binary tree

한 노드가 최대 두 개의 자손 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자손 노드는 왼쪽, 오른쪽으로 불린다.

이진트리의 특징

각 노드가 자손 노드를 최대한 2개 까지만 가질 수 있는 트리 (왼쪽 자손 노드 (left child node), 오른쪽 자손 노드 (right child node))

이진 트리의 특성

레벨 i에서의 노드의 최대 개수는 2^i개이다. 그리고 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^h+1 -1) 개가 된다.

이진 트리의 종류

포화 이진 트리 (Full Binary Tree) 모든 레벨에 노드가 포화상태로 차 있는 이진 트리이다. 높이가 h일 때, 최대의 노드 개수인 (2^h+1 -1)의 노드를 가진 이진 트리이다. 루트를 1번으로 하여 2^h+1 -1까지 정해진 위치에 대한 노드 번호를 가진다.

완전 이진 트리 (Complete Binary Tree)

높이가 h이고 노드 수가 n개일 때의 이진 트리이다. 포화 이진 트리의 노드를 좌에서 우로, 위에서 아래로 번호를 붙였을 때, 번호가 큰 뒤쪽 노드만 생략할 수 있다.

편향 이진 트리 (Skewed Binary Tree) 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자손 노드 만을 가진 이진 트리이다.

지금까지 배운 트리로 어떤 작업을 하려면 트리의 모든 노드를 한 번씩 방문하는 순회의 개념을 알아야 한다. 그래야 노드의 값 출력, 검색 또는 삭제 등의 작업을 할 수 있다. 이제 이진트리의 순회에 대해 배워보자.

이진 트리의 순회

순회(traversal)란 트리의 각 노드를 중복되지 않게 전부 방문하는 것을 말하는 데 트리는 비 선형 구조이기 떄문에 선형구조에서와 같이 선후 연결 관계를 알 수 없다. 따라서 특별한 방법이 필요하다.

대표문제. 중위순회와 같이 순회의 방법은 중위 순회를 포함한 총 3가지의 순회 방법이 있다. 전위, 중위, 후위 순회가 기본적인 순회 방법이다.

전위 순회(preorder traversal) : 자손 노드보다 루트노드를 먼저 방문한다. VLR
중위 순회(inorder traversal ) : 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문한다. LVR
후위 순회(postorder traversal) : 루트 노드보다 자손을 먼저 방문한다. LRV

전위 순회

전위순회부터 살펴보자. 전위 순회 방법은 먼저 현재 노드 n을 방문하여 퍼리한다(v) 그리고 현재 노드 n의 왼쪽 서브트리로 이동한다.(L) 마지막으로 현재 노드 n의 오른쪽 서브트리로 이동한다.(R) 이와 같은 순서로 트리의 전체를 순회한다.

preorder_traverse(T)
if(T is not null)
{
	visit(T);
    preorder_traverse(T.left);
    preorder_traverse(T.right);
}
End preorder_traverse

루트를 우선 적으로 처리해야 하므로 자신의 데이터를 visit 함수로 출력한다. visit함수 호출은 순회 중에 하고자 하는 작업에 해당한다. 이 함수 안에서 해당하는 작업을 하면 된다.

중위 순회

inorder_traverse(T)
if(T is not null)
{
	inrder_traverse(T.left);
	visit(T);
    inorder_traverse(T.right);
}
End inorder_traverse

후위 순회

postorder_traverse(T)
if(T is not null)
{
	postorder_traverse(T.left);
    postorder_traverse(T.right);			visit(T);
}
End postorder_traverse

이제 간단한 연습문제를 풀어보자.

구조체

struct Node
{
	int data;
    Node *left ;
    NOde *right;
};
Node *Root;

데이터를 넣는다고 생각해보자

데이터를 넣을 Node 생성
데이터가 현재 노드의 왼쪽 노드에 들어갈 것인지, 오른쪽 노드에 들어갈 것인지 판단하고 부모 노드와 현재 노드가 참조되는 형태를 만든다.

Root = (Node*)malloc(sizeof(Node));//루트 노드 생성
Root -> data = data; // 루트노드에 값 삽입

/* 반복 과정 */

NOde *New // 새로운 노드 생성
New = (Node *)malloc(sizeof(Node)); // 새로운 노드
New -> data = data; // 새로운 노드 값 삽입
New->left = NULL;빈값으로 초기화
New->right = NULL;
if(bLeft) { // 부모 노드가 새로운 노드를 찾을 수 있게 참조
	Parent -> Left = New ;
}
else {
	Parent-> right = New;
}

이진 탐색 트리

탐색 작업을 효율적으로 하기 위한 자료구조 모든 원소는 서로 다른 유일한 키를 갖고 있다.

루트보다 작으면 왼쪽 서브트리, 루트보다 크면 오른쪽 서브트리. 즉 key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)

이런 특징을 알 수 있다. 따라서 중위 순회를 하게 되면 오름차순으로 정렬된 값을 얻을 수 있다.

이제 이진 탐색 트리의 삽입, 삭제 과정을 알아보자.

먼저 이진 탐색 트리의 탐색 연산 연습문제부터 살펴보자.

연습문제. 이진 탐색 트리 탐색

탐색 연산의 과정

루트에서 시작한다
탐색할 키값 x를 루트 노드의 키값과 비교한다
(키값 x = 루트노드의 키값)인 경우 : => 원하는 원소를 찾았으므로 탐색연산 성공
(키값 x < 루트노드의 키값)인 경우:
=> 루트노드의 왼쪽 서브트리에 대해서 탐색 연산 수행
(키값 x> 루트노드의 키값)인 경우: => 루트노드의 오른쪽 서브트리에 대해서 탐색 연산 수행
서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

// 이진 탐색 트리 탐색
int search(int value){
	// 노드의 순회
    Node *Temp = Root;
    while(Temp){
    	//찾으려는 노드의 값이 더 큰 경우, 오른쪽으로
        if(Temp->value < value){
	        Temp=Temp->right;
        }
        //찾으려는 노드의 값이 더 작은 경우, 왼쪽으로
        else if(Temp->value > value){
        	Temp = Temp->left;
        }
        else if(Temp->value == value){
	        return 1;
        }
    }
    return 0;
}

연습문제. 이진 탐색 트리 삽입

노드 구조체 만들기
노드 초기화 및 데이터 삽입 함수 만들기
노드 삽입 함수 만들기

이 문제는 중복되는 숫자가 들어오면, 왼쪽 노드로 이동하게 했다. (중복된 숫자가 들어오지는 않으니 안심하자.) 만약 들어오게 된다면 새로운 조건문을 만들어서 중복된 값이 들어왔다고 알려야 한다.

코드가 c로 되어 있어서 이해만 하고 넘어감.

연습문제 이진 탐색 트리 삭제

노드를 삭제하는 것은 이진 탐색 트리에서 가장 복잡한 연산이다. 먼저 노드를 삭제하기 위해서는 우리가 삭제하려고 하는 키 값이 트리 안에 어디에 있는지 알아야 지울 수 있다. 그래서 먼저 노드를 탐색해야 한다. 노드를 탐색하였으면, 다음의 3가지 경우를 고려해야 한다.

삭제하려는 노드가 단말 노드일 경우
삭제하려는 노드가 하나의 서브 트리만 가지고 있는 경우
삭제하려는 노드가 두 개의 서브 트리를 모두 가지고 있는 경우

삭제하려는 노드가 두 개의 서브트리를 모두 가지고 있는 경우, 여기서는 삭제하려는 노드의 자리에 가장 알맞은 비슷한 노드로 바꿔 넣어주는 방식을 취했다. 이렇게 하기 위해서는 두 가지 방법이 있다.

자기 자신의 노드를 반환하고 자기 자신이 가지고 있는 서브 트리의 링크 필드를 부모 노드에게 붙여주면 된다. 그렇게 하기 위해서 Parent 노드를 만들어서 항상 이전의 노드를 저장할 수 있게 한다.

삭제하려는 노드의 왼쪽 서브 트리의 가장 키 값이 큰 노드
삭제하려는 노드의 오른쪽 서브 트리의 가장 키 값이 작은 노드

코드에서는 1의 방법을 이용하였다. 즉 새로운 child_P, child 노드를 생성해서 알맞은 후보를 찾아서 현재 삭제하는 노드에 복사해서 넣어줬다.

힙

힙이란 ? 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조다 힙은 최대 힙과 최소 힙이 있다. 힙의 키를 우선순위로 활용하여 우선순위 큐를 구현할 수 있는데, 이것은 뒤에서 알아 보기로 한다.

최대힙

키값이 가장 큰 노드를 찾기 위한 이진 트리
부모노드의 키값> 자손노드의 키값
루트노드는 키값이 가장 큰 노드

최소 힙

키값이 가장 작은 노드를 찾기 위한 완전 이진트리
부모노드의 키값 < 자손노드의 키값
루트노드는 키값이 가장 작은 노드

힙의 삽입 연산

조건에 따라 삽입만 해도 되는 경우가 이고, 삽입할 노드가 부모노드 보다 큰 경우 새로운 연산을 해서 바꿔줘야 한다. 최대 힙의 조건을 지키기 위해서 부모노드와 삽입 노드를 바꿔주는 작업을 삽입 노드가 루트 노드가 될 대까지 또는 부모노드가 삽입 노드보다 클떄까지 한다.

힙의 삭제 연산

힙의 삭제 연산은 다음과 같은 조건이 있다.

힙에서는 루트 노드의 원소만을 삭제 할 수 있다.
루트 노드의 원소를 삭제하여 반환한다.
힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.

힙의 삭제는 항상 루트의 원소를 삭제해야한다. 루트의 원소를 삭제하고, 트리의 마지막 노드의 원소와 바꿔주고, 마지막 노드를 삭제시킨다. 최대 힙의 조건을 만족시키기 위해서 바꾼 노드에서 자식 노드와 비교하여 자식 노드가 더 크다면, 두 자식 중 큰쪽 자식과 바꿔주는 연산을 바꾼 노드가 단말 노드가 되거나 두 자식노드보다 클때까지 반복한다.

6.1 대표 문제 중위순회 해결하기.

제한 조건

총 10개의 테스트 케이스가 주어진다.

총 노드의 개수는 100개를 넘어가지 않는다.

트리는 완전 2진 트리 형식으로 주어지며, 노드당 하나의 알파벳만 저장할 수 있다.

노드가 주어지는 순서는 아래 입력 예시와 같이 숫자 번호대로 주어진다.

입력

입력 파일의 첫 줄에는 각 케이스의 트리가 갖는 정점의 총 수 N(1 <= N <= 100 )이 주어진다. 그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다. 해당 정점에 대한 정보는 해당 정점의 알파벳, 해당 정점의 왼쪽 자손, 오른쪽 자손의 정점번호가 차례대로 주어진다. . 정점번호는 1부터 N까지의 정수로 구분된다. 입력에서 정점번호를 매기는 규칙은 위와 같으며, 루트 정점의 번호는 반드시 1이다.

입력에서 이웃한 알파벳이나 자손 정점의 번호는 모두 공백으로 구분된다.

위의 예시에서 알파벳 s가 정점에 해당하면 “7 S”으로 주어지고, 알파벳 F가 2번 정점에 해당하면 두 자손이 각각 알파벳 O인 4번 정점과 알파벳 T인 5번 정점이므로 “2 F 4 5”로 주어진다.

총 10개의 테스트 케이스가 주어진다.

입력 예시

8 // 정점의 총 수 N 1 W 2 3 // 해당 정점의 번호, 정점의 알파벳, 왼쪽, 오른쪽 자손 2 F 4 5 3 R 6 7 4 O 8 5 T 6 A 7 E 8 S

출력 예시

#1 SOFTWARE // 테스트 케이스 1번 답

트리를 중위순회 하는 방법을 참고하자.

이 문제는, 입력 값 처리 방법이 트리 입력 방법의 유일한 것이 아니다. 이 입력 방법은 많이 까다롭다. 자손이 있는 경우, 없는 경우가 있다. 이와 같은 입력을 받는 방법은, 줄 단위로 받는 방법이 있다. 다른 방법은 완전 이진 트리인 것을 알아야 한다. 그래서 트리의 정점의 개수를 비교하며 뒤에 자손 노드가 존재하는 지를 찾는 코드를 생각해 볼 수 있다.

이진 트리의 정보를 담기 위한 과정이 필요하다. 사전에 배열과 연결리스트를 통해 이진 트리를 구현해 보았다. 가장 적합한 방법을 찾아야 한다.

부모 노드가 1이면 부모 노드에 곱하기 2의 숫자가 왼쪽 자 손, 거기에 더하기 1을 한 숫자가 오른쪽 자손임을 드러내고 있다.

부모 노드 * 2 = 왼쪽 자손 노드
부모 노드 * 2 + 1 = 오른쪽 자손 노드

이러한 구조는, 자손 노드를 동적으로 생성하는 방법으로 하게 되면, 매번 자손 노드를 삽입할 때 이진 트리 탐색을 통해 자손 노드를 봐야하므로 매우 비효율적이다. 위의 문제는 배열의 크기가 100이라고 정해져 있으므로 배열을 이용하여 트리를 구성하는 방법이 알맞은 방법 중 하나이다. 그래서 위의 문제는 구조를 만들되, 구조체 배열로 이진 트리를 구현할 수 있다.

c 코드라서 이해만 하고 넘어감.

참고자료

소프트웨어 아카데미 S/W Problem Solving

배열 정렬 참고자료

https://defacto-standard.tistory.com/18