자료구조_비선형 구조

비선형 구조

트리의 개요

트리의 정의 - 트리는 계층적인 구조를 나타내는 비선형 자료구조로, 노드와 간선으로 이루어져 있다.

// 트리의 대표적인 특징

트리에는 루트 노드가 단 하나뿐이고, 루트 노드는 트리의 최상위에 위치한다. 다른 노드는 모두 루트 노드에서 파생되며 계층 구조를 이룬다.
트리를 구성하는 각 노드는 모두 부모 노드(Parent Node)와 자식 노드(Child Node)의 관계가 되고 간선(Edge)으로 연결된다. 이때 부모 노드는 자식 노드를 여러 개 가질 수 있지만, 자식 노드는 부모 노드를 하나만 가질 수 있다.
각 노드 사이에는 사이클이 허용되지 않는다. 따라서 임의의 노드에 시작해 간선을 따라가면 다시 이전 노드로 돌아갈 수 없다. 그러므로 트리는 비순환 구조라고 할 수 있다.
트리는 비순환 그래프이고 방향성이 없다. 따라서 간선으로 연결된 노드들은 한쪽 방향으로만 이동할 수 있고, 간선은 부모 노드에서 자식 노드로만 이동할 수 있다.

* 트리는 자료구조의 생김새가 나무와 비슷하다고 해서 붙여진 이름이다.

트리에서 사용하는 용어

노드(node) - 트리 구성의 기본 요소이자, 데이터를 저장하고 있는 개체
루트 노드(root rnode) - 트리의 최상위에 위치하는 노드로서, 모든 노드는 루트 노드와 계층 관계이다.
부모 노드(parent node) - 각 노드의 바로 위에 있는 노드를 의미한다. 부모 노드는 자식 노드와 간선으로 연결되어 있다.
자식 노드(child node) - 각 노드의 바로 아래 노드를 의미한다. 부모 노드와는 간선으로 연결된다.
형제 노드(sibling node) - 부모 노드가 같은 노드들을 의미한다.
차수(degree) - 자식 노드의 수를 의미한다.
트리의 차수(degree of tree) - 트리에서 가장 큰 차수를 의미한다.
단말 노드(leaf node) - 자식이 없는 노드로서, 차수가 0인 노드를 의미한다.
레벨(level) - 루트 노드로부터 특정 노드까지의 거리를 의미한다.
트리의 높이(height of tree) - 트리의 최대 레벨을 의미한다. 즉 루프 노드로부터 가장 멀리 떨어져 있는 단말 노드까지의 거리이다.
깊이(depth) - 특정 노드에서 루트 노드까지 경로의 길이를 의미한다. 즉, 각 노드의 위치를 상대적으로 표현하는 데 사용된다.
서브 트리(sub tree) - 특정 노드를 제거했을 때 생기는 하위 트리이다.

* 트리는 자료구조의 생김새가 나무와 비슷하다고 해서 붙여진 이름이다.

트리의 종류

자유트리(Free Tree)
- 각 노드가 상호 연결된 초기 상태의 트리로, 사이클이 없으나 부모-자식 관계가 형성되지 않고, 루트 노드도 없다.
순서 트리(Ordered Tree)
- 일반적인 트리와 달리 자식 노드의 순서가 중요한 정보를 나타내는 경우에 사용된다.
- 자식 노드들 사이의 순서가 명확하게 정의되어 있어서 노드의 순서가 바뀌면 서로 다른 트리가 된다.
비순서 트리(Unordered Tree)
- 순서 트리와 달리 자식 노드 간의 순서가 중요하지 않은 트리 구조이다.
- 자식 노드들 사이에 순서가 없으며, 각 자식 노드의 위치가 동등해 노드의 순서가 바뀌어도 같은 트리이다.
이진 트리(Binary Tree)
- 모든 노드의 자식노드가 최대 두 개 이하인 트리이다.
- 알고리즘과 자료구조에서 널리 사용되는 가장 기본적인 트리이다.
닮은 트리(Similar Tree)
- 구조는 같고 데이터만 다른 트리이다.
- 두 개 이상의 트리에 포함된 데이터나 내용은 서로 다르더라도 구조나 형태는 유사한 경우를 말한다.
대등 트리(Equivalent Tree)
- 구조와 데이터가 모두 같은 트리이다.
- 서로 다른 트리가 구조적으로 동일하며 요소가 동등한 경우를 말한다.

* 트리는 데이터 구조의 요구사항과 응용 분야에 따라 최적화된 구조를 제공하기 위해 다양한 형태로 표현된다. 이를 통해 데이터의 표현과 조작, 연산의 효율성, 응용 분야의 다양성을 충족시킬 수 있다.

트리의 표현

재귀적 표현(Recursive Representiation) - 노드와 그 노드의 자식 노드들의 집합으로 나타낸다.

// (루트 노드(서브 트리 1(자식노드 1, 자식 노드 2), 서브트리 2....)....)

ex. (A(B(E, F), C(G), D))

* 트리의 재귀적 표현 방법은 트리의 구조를 간결하고 직관적으로 표현할 수 있다. 또한 트리의 깊이 수선 탐색(DFS) 같은 알고리즘을 구현하는데 유용하게 활용된다.

배열로 표현

- 트리의 노드는 배열의 원소로 표현하고, 각 노드의 인덱스를 이용해 부모-자식 관계를 나타낸다.
- 트리의 레벨 순서로 노드를 저장하고 접근할 수 있다.

* 트리를 배열로 표현하면 특정 노드의 부모 노드나 자식 노드에 쉽게 접근할 수 있다. 또한 배열을 이용한 표현 방법은 트리의 순회 알고리즘 등 다양한 트리 연산에 유용하게 사용되고 있다.

// 부모 노드의 index = 자식 노드의 index / 2

// 왼쪽 자식 노드의 index = 부모 노드의 index * 2

// 오른쪽 자식 노드의 index = (부모 노드의 index * 2) +

* index 1이 루트가 되며, index 0은 사용하지 않는다.

연결리스트로 표현

- 각 노드를 객체로 표현하고, 노드 간에 포인터를 이용해 부모-자식 관계를 나타낸다.

- 각 노드 객체는 데이터와 왼쪽 / 오른쪽 자식 노드를 가리키는 포인터를 포함한다.

- 메모리를 효율적으로 사용할 수 있다.

* 트리를 연결리스트로 표현하면 트리의 구조를 동적으로 조작할 수 있고, 노드의 삽입, 삭제, 탐색 등 다양한 연산이 간편해진다.

이진 트리(Binary Tree)

이진 트리의 개념 - 이진 트리는 계층적인 구조로 되어 있으며, 각 노드에 최대 두 개의 자식 노드가 있다. 자식 노드의 개수 및 노드 배치 방법에 따라 이진 트리, 정 이진 트리, 완전 이진 트리, 사향 이진 트리 등이 있다.

// 이진 트리의 특징

레벨 e에서 가질 수 있는 최대 노드의 수는 2의 e-1 제곱이다.
트리의 높이가 h일 때, 최대 노드의 수는 2의 h제곱 -1이다.
노드의 수가 n일 때, null pointer 수는 n+1이다.
노드의 수가 n일 때, 가지(Edge)의 수는 n-1이다.
자식 노드가 없는 단말 노드의 수를 n0, 자식 노드의 수가 2인 단말 노드의 수를 n2라고 할 때 n0 = n2+1이다.
노드 번호가 i일 때, 부모 노드의 위칫값은 i/2, 왼쪽 자식 노드의 위칫값은 i*2, 오른쪽 자식 노드의 위칫값은 i*2+1이다. ( 자식 노드가 없는 노드도 위칫값은 있다. )

* 이진트리는 데이터를 정렬된 상태로 유지하고, 탐색, 삽입, 삭제 연산을 효율적으로 수행하는 데 사용된다. 또한 힙(Heap)이나 트라이(Trie)와 같은 특수한 종류의 이진트리도 데이터 구조로 많이 활용된다.

정 이진 트리(Full Binary Tree / 포화 이진 트리)

- 최대 레벨의 모든 단말 노드가 꽉 찬 노드이다.

- 단말 노드를 제외한 모든 노드에 자식 노드가 두 개이고, 모든 단말 노드는 레벨이 동일하다.

마지막 레벨을 제외한 모든 노드의 차수가 2이다.
높이가 h일 때, 전체 노드의 수는 2의 h제곱-1이다.
각 레벨 i의 노드 수는 2의 i-1 제곱이다.

* 정 이진 트리는 각 노드의 자식 노드가 두 개이므로 구조가 일관되고 균형적이다. 이러한 특성으로 인해 구현이 간단하고 탐색 알고리즘의 작성에 용이하다.

완전 이진 트리(Complete Binary Tree)

- 최대 레벨을 제외한 나머지 레벨에 모두 노드가 채워져 있고 최대 레벨의 노드는 왼쪽부터 채워진 트리를 말한다.

- 마지막 레벨을 제외하면 정 이진 트리를 형성하고, 마지막 레벨은 왼쪽부터 순차적으로 채워지는 구조이다.

전체 노드의 수가 n이면, 트리의 높이는 ┕ log₂n ┙+1이다.

* 완전 이진 트리는 노드를 왼쪽부터 차례로 채우는 특성이 있으므로 배열처럼 메모리를 연속적으로 할당해 사용할 수 있다. 이러한 특징으로 인해 배열 등의 데이터 구조로 표현하거나 힙(Heap)과 같은 자료구조에 활용할 때 유용하다.

사향 이진 트리(Skewed Binary Tree)

- 모든 노드에 왼쪽 자식 노드 또는 오른쪽 자식 노드만 있는 이진 트리를 말한다.

- 트리의 형태가 한쪽 방향으로 치우쳐 있다.

노드의 수가 전체 트리의 높이와 같다. ( 높이가 h일 때, 전체 노드의 수는 h이다. )

트리 운행(Tree Traversal)

트리 운행 개념 - 트리의 모든 노드를 방문하는 방법 또는 순서를 말한다. 트리 운행을 통해 각 노드를 방문하면서 원하는 작업을 수행하거나 트리의 데이터를 탐색해 필요한 정보를 얻을 수 있다.

* 트리 구조는 계층적이고 조직화된 데이터를 표현하기 때문에, 운행을 통해 데이터에 효과적으로 접근할 수 있다. 또한 운행을 통해 트리 내 특정 노드의 위치를 찾고, 노드를 추가 또는 삭제할 수 있다.

트리 운행 방법 - 노드를 방문하는 순서에 따라 전위 운행(Pre-order Traversal / DLR), 중위 운행(In-order Traversal / LDR), 후위 운행(Post-order Traversal / LRD)으로 구분한다. 이러한 운행 방법의 차이는 트리의 구조를 탐색하거나, 트리를 재구성하는 다양한 알고리즘에서 널리 활용된다.

전위 운행(Pre-order Traversal)
- 현재의 노드를 먼저 처리한 후 자식 노드를 방문하는 방식이다. ( DLR )
1. 노드의 데이터를 출력한다. // D
2. 왼쪽 자식 노드가 있으면 전진한다. // L
3. 오른쪽 자식 노드가 있으면 전진한다. // R
중위 운행(In-order Traversal)
- 왼쪽 서브 트리를 먼저 방문한 후, 현재 노드를 처리하고 이어서 오른쪽 서비트리를 방문하는 방식이다. ( LDR )
1. 왼쪽 자식 노드가 있으면 전진한다. // L
2. 노드의 데이터를 출력한다. // D
3. 오른쪽 자식 노드가 있으면 전진한다. // R
후위 훈행(Post-order Traversal)
- 왼쪽 서브 트리와 오른쪽 서브 트리를 순서대로 방문한 후, 현재 노드를 처리하는 방식이다. ( LRD )
1. 왼쪽 자식 노드가 있으면 전진한다. // L
2. 오른쪽 자식 노드가 있으면 전진한다. // R
3. 노드의 데이터를 출력한다. // D

#include <stdio.h>
#include <stdlib.h>
struct node{
	struct node*llink;
    char data;
    struct node* rlink;
};

struct node* createNode(char data){
	struct node* p = (struct node*)malloc(sizeof(struct node));
    p->llink = NULL;
    p->data = data;
    p->rlink = NULL;
    return 0;
}

void deleteAll(struct node* p){
	if(p != NULL){
    	deleteALl(p->llink);
        deleteAll(p->rlink);
        free(p);
    }
}
void preOrder(struct node* p){
	if(p != NULL){
    	printf("%c ", p->data);
        preOrder(p->llink);
        preOrder(p->rlink);
    }
}

void inOrder(sruct node* p){
	if(p != NULL){
    	inOrder(p->llink);
        printf("%c ", p->data);
        inOrder(p->rlink);
    }
}

void postOrder(struct node* p){
	if(p != NULL){
    	postOrder(p->llink);
        postOrder(p->rlink);
        printf("%c ", p->data);
    }
}

int main(void){
	struct node* root = createNode('A');
    root->llink = createNode('B');
    root->rlink = createNode('C');
    root->llink->llink = createNode('D');
    root->llink->rlink = createNode('E');
    root->rlink->llink = createNode('F');
    root->rlink->rlink = createNode('G');
    root->llink->rlink->llink = createNode('H');
    
    printf("전위 운행(preOrder) : ");
    preOrder(root); printf("\n");	// A, B, D, E, H, C, F, G
    
    printf("중위 운행(inOrder) : ");	// D, B, H, E, A, F, C, G
    inOrder(root); printf("\n");
    
    printf("후위 운행(postOrder) : ");	// D, H, E, B, F, G, C, A
    postOrder(root); printf("\n");
    
    deleteAll(root);
    return 0;
}

* 중위 운행은 이진 탐색 트리의 노드를 정렬된 순서로 방문할 수 있어서, 효율적인 검색과 정렬을 수행할 수 있다.

* 전위 운행과 후위 운행은 수식이나 계산식을 표현하고 계산하는 데 사용된다.

그래프(Graph)의 개요

그래프의 정의
- 그래프는 정점과 간선의 집합으로 구성된 자료이다.

- 전기회로 분석, 최단 거리 탐색, 컴퓨터 네트워크, 인공지능 등에 널리 활용된다.

// 그래프에 사용되는 용어

정점(Vertex) : 그래프의 구성 요소 중 하나로, 데이터를 나타내는 개체이며, 일반적으로 숫자, 알파벳, 기호 등으로 표현된다.
간선(Edge) : 정점과 정점 사이를 연결하는 선으로, 간선은 정점 간의 관계를 나타낸다. 간선은 방향성이 있는 경우도 있고, 없는 경우도 있다.
인접 정점(Adjacent Vertex) : 한 정점과 간선으로 연결된 다른 정점으로서, 정점과 정점 사이에 연결선이 있고 직접 접근이 가능하다.
경로(Path) : 정점들을 간선으로 연결해 이동하는 경로를 말하며, 출발에서 목표 지점까지 정점들의 순서를 의미한다. 정점 사이는 무뱡향 간선(-) 또는 방향 간선(->)으로 표현할 수 있다. ( 출발 정점 / 도착 정점 )
차수(Degree) : 한 정점에 연결된 간선의 수를 의미한다. 무방향 그래프의 경우 차수는 해당 정점과 인접한 정점의 수를 의미하고, 방향 그래프의 경우 차수는 해당 정점으로 들어오거나 나가는 간선 수를 합한 값이다.
사이클(Cycle) : 최소 세 개 이상의 정점(2개도 가능)으로 이루어진 경로이며, 시작 정점과 끝 정점이 동일한 경우를 의미한다. 사이클은 그래프 내에서 반복된 경로를 형성한다. (사이클 이룸 = 트리 x / 그래프 o )
가중치(Weight) : 간선에 할당된 값으로, 간선의 비용이나 거리를 나타낸다. 가중 그래프에서는 각 간선에 가중치가 할당될 수 있다.
연결 그래프(Connected Graph) : 그래프 내의 모든 정점이 최소한 하나의 경로로 연결된 그래프를 말한다.

* 그래프가 '특정 조건'을 충족하는 경우 트리라고 부른다. 여기서 특정 조건은, 노드는 부모와 자식으로 계층적 구조이어야 하고, 그래프에 사이클이 없어야 한다는 것이다.

// 그래프 기초

단순 경로 : 경로 상에서 같은 노드를 중복해서 지나지 않는 경로이다.
사이클(Cycle) : 출발과 도착 정점이 같은 단순 경로를 말한다. ( = 단순경로의 특수한 경우 )
차수(Degree) : 한 정점에 연결된 간선의 수를 말한다.

* 경로를 탐색하고 분석함으로써 그래프의 구조와 연결성을 이해하고, 최단 경로를 찾거나 네트워크 흐름을 최적화할 수 있다.

그래프의 종류 - 그래프는 간선의 방향성, 가중치, 사이클 형성 여부에 따라 다양한 형태로 표현할 수 있다.

무방향 그래프(Undirected Graph)
- 간선에 방향성이 없는 그래프를 말하며, 인접 간에 상호 접근이 가능하다.

- 간선이 양방향으로 이동할 수 있으며, 연결된 두 정점의 관계는 상호적이다.
- G = ( V, E )의 수식으로 표현가능하며, V는 정점들의 집합을, E는 간선들의 집합을 의미한다.

// 무방향 그래프 G1을 수식으로 표현

// V(G1) = {A, B, C, D, E}

// E(G1) = {(A, B), (A, C), (B, D), (B, E)}

* 무방향 그래프에서는 간선의 순서가 없으며, 간선은 단순히 두 노드 사이의 연결을 나타낸다.

방향그래프(Directed Graph)

- 간선에 방향이 있는 그래프로서, 방향을 따라 인접으로 접근이 가능한 그래프를 의미한다.

- 한 정점에서 다른 정점으로의 연결이 일방적이므로, 해당 정점으로 들어오는 간선의 수를 징비 차수(In-Degree)라고 하고, 해당 정점에서 나가는 간선의 수를 진출 차수(Out-Degree)라고 한다.

// 방향 그래프 G2

// V(G2) = {A, B, C}

// E(G2) = {<A, B>, <A, C>}

* 방향 그래프에서 간선은 한 노드에서 다른 노드로 방향성을 가지며, 출발 노드와 도착 노드 간에 방향성이 명확하게 정의된다.

혼합 그래프(Mixed Graph)

- 방향 그래프와 무방향 그래프의 특징을 동시에 가지고 있어서, 간선의 방향성이 중요한 경우와 그렇지 않은 경우 모두를 다룰 수 있다.

// 혼합 그래프 G3

// V(G3) = {A, B, C, D, E, F}

// E(G3) = {<A, B>, (A, C), <A, D>, <B, C>, (B, F), (C, E), <D, E>, <E, F>}

* 교통 네트워크를 모델링하는 경우에 효율적으로 사용될 수 있다.

* 도로 사이의 연결은 방향그래프의 간선으로 표현하고, 교차로 사이의 연결은 방향성이 없는 간선으로 표현할 수 있다.

가중치 그래프(weighted Graph)

- 간선에 가중치(weight)라는 숫자 값을 할당한 그래프를 의미하며, 가중치에는 간선을 통과하는 데 필요한 비용, 거리, 우선순위 등의 가치를 부여할 수 있다.

- 가중치 그래프는 최단 경로 문제, 최소 비용 신장 트리와 같은 다양한 그래프 알고리즘에서 중요한 개념으로, 간선의 가중치를 고려해 그래프 내에서 최적의 경로나 구조를 찾는 등 다양한 분야에서 유용하게 활용된다.

// G = ( V, E, W)

// V는 정점의 집합, E는 간선의 집합, W는 각 간선에 대한 가중치의 집합을 의미한다.

* 가중치 그래프는 일반 그래프의 확장된 형태로, 보다 현실적이고 복잡한 상황을 모델링할 수 있다.

완전 그래프(Complete Graph) - 모든 정점이 간선으로 연결된 그래프로, 모든 정점 사이에 간선이 존재한다.

// n개의 정점이 있는 완전 그래프의 간선은 총 n(n-1)/2개이다.

// 5개 정점인 완전 그래프 간선 = 5(5-1)/2 = 10

신장 트리(Spanning Tree) - 주어진 그래프의 모든 정점을 연결하면서도 사이클을 형성하지 않는 트리를 의미한다. 즉, 그래프의 부분 그래프 중에서 사이클이 없는 트리 구조이다.

* 신장 트리와 신장 그래프는 일반적으로 같은 의미로 사용된다.

최소비용 신장 트리(Minimum Spanning Tree, MST)

- 가중치 그래프에서 모든 정점을 연결하면서 간선들의 가중치 합이 최소인 트리를 의미한다.

- 그래프의 연결성을 유지하면서 최소비용으로 모든 정점을 연결하는 문제 해결에 유용하다.
- 네트워크, 도로 시스템, 전기회로, 통신망 등 다양한 분야에서 중요하게 사용된다.

쿠르스칼(Kruskal) 알고리즘
- 크루스칼 알고리즘은 간선의 가중치를 기준으로 그래프의 최소비용 신장 트리를 구성하는데, 산선을 선택할 때 사이클을 형성하지 않으면서 가중치가 가장 작은 간선을 선택한다.
프림(Prim) 알고리즘
- 프림 알고리즘은 선택한 정점과 연결된 간선 중에서 가중치가 가장 작은 간선을 선택하는 단계를 반복하면서 최소비용 신장 트리를 구성한다.

* 크루스칼 알고리즘과 프림 알고리즘은 최소비용 신장 트리를 구성하는 데 사용하는 알고리즘이라는 공통점이 있다.

* 차이점은 크루스칼 알고리즘은 간선을 기준으로 그래프를 확장하고, 프림 알고리즘은 정점을 기준으로 그래프를 확장한다는 점이다.

* 프림 알고리즘은 시작 정점을 선택하여 시작한다. 따라서 시작 정점의 선택에 따라 최종 결과가 달라질 수 있고, 이는 최소비용 신장 트리의 품질과 구조에 영향을 줄 수 있다.

그래프(Graph)의 표현

인접행렬로 표현 - 그래프를 2차원 배열로 표현하는 방법으로, 정점 간의 연결 여부를 행렬의 값으로 표현한다.

* 인접행렬은 정점 간의 연결 관계를 효율적으로 확인할 수 있고, 간선의 존재 여부를 상수 시잔에 확인할 수 있다는 장점이 있다. 단점은 중복되는 정보가 있기 때문에 공간을 더 많이 사용한다는 것이다.

인접리스트로 표현 - 그래프를 인접리스트로 표현하려면 각 정점의 번호를 인덱스로 사용하고 해당 정점과 인접한 정점들을 리스트로 지정한다.

의 부분 그래프 중에서 사이클이 없는 트리 구조이다.

* 방향 그래프에서 간선은 한 방향으로만 흐르기 때문에 각 정점의 인접리스트에는 해당 정점에서 출발하는 간선에 연결된 정점들만 포함된다.

'전공' 카테고리의 다른 글

Java_예외 처리, 스레드 (0)	2024.10.08
Java_컬렉션 제네릭 (7)	2024.10.08
파이썬_변수, 자료형 / 제어문, 반복문 / 함수 (0)	2024.07.10
자료구조_선형 구조 (0)	2024.07.09
자료구조_자료구조와 알고리즘 (0)	2024.07.09

story-study

자료구조_비선형 구조

비선형 구조

'전공' 카테고리의 다른 글

티스토리툴바

자료구조_비선형 구조

비선형 구조

'전공' 카테고리의 다른 글

'전공' Related Articles

티스토리툴바