그래프이론, 트리, 이진탐색트리

gunnoo·2024년 7월 9일

data structure

목록 보기

3/5

그래프 이론

그래프 이론에는 오일러경로, 단절점 등 어려운 개념들이 많지만 그중 기초만 다뤄보도록 하겠다. 먼저 정점과 간선이다.
정점은 분할할 수 없는 객체이자, 점으로 표현되는 위치, 사람 물건 등이 될수있는데 어떠한 위치나 어떠한 사람 등으로 나타낼 수 있다. Vertax라고 부른다.
다음 간선은 정점을 잇는 선을 의미한다. 관계, 경로 등이 될 수 있다. 이때 간선은 단방향 간선, 양방향 간선이 존재한다. 간선은 edge라고 부른다.
indegree와 outdegree
정점으로 나가는 간선을 해당 정점의 outdegree라고 부르고 들어오는 간선을 indegree라고 부른다. 쉽게 말해서 자신에게 오는 간선은 indegree, 자신으로부터 나가는 간선은 outdegree라고 생각하면 된다. 이때, outdegree와 indegree는 여러개가 존재할 수 있다.
가중치
가중치는 그래프 이론에서 나오는 개념으로 정점과 정점사이에 드는 비용을 말한다. 비용은 시간, 칸수 등을 말하는데 예를 들어 설명하자면 1번 노드와 2번 노드까지 가는 비용이 한칸이라면 1번 노드에서 2번 노드까지의 가중치는 한칸이다.

지금까지 설명한 정점과 간선들로 이루어진 집합을 그래프라고 부른다.

이 그래프를 컴퓨터에게 알려줄 표현 방법으로는 인접행렬과 인접리스트가 존재한다.

인접행렬이란?

그래프에서 정점과 간선의 관계를 나타내는 bool타입의 정사각형 행렬을 의미한다. 이떄 정사각형 행렬 의 각 요소는 0또는 1이라는 값을 가지는데 0은 두 정점 사이의 경로가 없음을 의미하고 1은 두 정점 사이의 경로가 있음을 의미한다.

위의 그림을 보면 0과 1, 1과 2, 0과 2, 0과 3이 연결되어있는 것을 볼 수 있는데 행렬로 표현하면
이렇게 나타나는데 이때, 1-1, 2-2는 0을로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 점점의 사이클이 없을 떄는 0이라고 표기한다.
코드로 표기하면 다음과 같다.

bool a[4][4] = {
 	{0, 1, 1, 1},
 	{1, 0, 1, 0},
 	{1, 1, 0, 0},
 	{1, 0, 0, 0},
 };

인접 리스트란?

인접리스트는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미한다. 인접행렬에서 나타낸 그래프가 있을 때엔 아래와 같이 나타낼 수 있다. 이때, 인접리스트를 코드로 나타낼 때에 벡터로도 구현가능한데, 이때 연결리스트와 벡터의 시간복잡도를 보면 이해할 수 있다. 인접리스트를 구현할때 많이 사용하는 연산은 마지막 요소에 삽입과해당 배열을 탐색하는 연산이다, 연결리스트의 경우 마지막 요소에 삽입, 삭제가 O(1)이고, 특정요소 탐색이 O(n)인데, vector 역시 해당 연산에 연결리스트와 시간복잡도가 동일하다. 그렇기 때문에 vector로 구현해도 무방하다.

인접행렬과 인접리스트의 차이는?

공간 복잡도

인접 행렬: O(V^2)
모든 정점 쌍에 대해 간선 존재 여부를 저장하므로 V^2에 비례하는 공간이 필요하다.
인접 리스트: O(V+E)
각 정점에 대해 연결된 간선만 저장하므로, 정점의 수 V와 간선의 수 E에 비례하는 공간이 필요하다.

시간 복잡도

간선 하나를 찾을 때
인접 행렬: O(1)
인접 행렬은 간선 존재 여부를 상수 시간 내에 바로 확인할 수 있다.
인접 리스트: O(V)
최악의 경우, 모든 정점을 확인해야 하므로 V에 비례하는 시간이 걸린다.

모든 간선을 찾을 때
인접 행렬: O(V^2)
모든 정점 쌍을 확인해야 하므로 V^2에 비례하는 시간이 걸린다.
인접 리스트: O(V+E)
모든 정점과 각 정점의 연결된 간선을 확인하므로 V와 E에 비례하는 시간이 걸린다.
결론
그래프가 희소할 때: 인접행렬이 인접리스트보다 메모리를 더 많이 써야하고 인접행렬의 경우, 간선이 없어서 대부분이 0임에도 불구하고 2차원 배열을 다 만들어야하기 떄문에 인접리스트가 더 유리하다.
그래프가 조밀할 때: 어차피 다 연결되어있기 때문에, 메모리 효율성은 동일한데 정점에서 정점까지의 확인하는 속도가 더 빠르기 때문에 인접 행렬을 사용하는 것이 더 유리하다.

트리

트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미한다.
트리의 용어로는
• 노드(node):트리의 구성요소
• 루트(root):부모가 없는 노드
• 서브트리(subtree):하나의 노드와 자손들로 이루어짐
• 단말(terminal)노드:자식이 없는 노드 리프(leaf)노드,잎 노드라고도 부름.
• 비단말(non-terminal)노드:자식을 가지는 노드

레벨(level):트리의 각층에 붙인 번호
높이(height):트리의 최대 레벨
차수(degree):노드의 자식 노드 개수
트리의 특징으로는 V-1 =E라는 특징이 있는데 간선 수는 노드 수 -1이라는 뜻이다. 또, 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없다.

이진트리

이진트리는 공집합이거나 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합을 말한다. 이진트리의 서브트리 또한 이진트리이다. 이진트리의 경우 각 노드는 최대 2개의 자식노드가 존재하며 다시 말해, 모든 노드의 차수가 2 이하가 된다. 또한 서브트리간의 순서가 존대하며 높이가 h일때, 최소 h개~2h-1개의 노드를 갖는다.
이진트리의 특징으로는 n개의 노드를 가지는 이진트리의 최대 높이는 h이고, 최소 높이는 log_{2}(n+1)을 가진다.

이진트리의 종류로는

정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리
완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터
채워져 있음.
변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리
포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리
균형 이진 트리(balanced binary tree): 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리. map, set을 구성하는 레드블랙트리는 균형이진트리 중
하나임.

이렇게 존재한다.

이진트리의 ADT

• create():이진트리를 생성한다.

• isEmpty():이진트리가 공백 상태인지 확인한다.

• getRoot():이진트리의 루트 노드를 반환한다.

• getCount():이진트리의 노드의 수를 반환한다.

• getHeight():이진트리의 높이를 반환한다.

• insertNode(n):이진트리에 노드 n을 삽입한다.

• deleteNode(n):이진트리에서 노드 n을 삭제한다.

• display():이진트리의 내용을 화면에 출력한다.

트리의 구현방법

배열로 구현하기
각 노드에 번호를 붙여, 그 번호를 배열의 인덱스로 삼아 각 노드의 데이터를 배열에 저장!
연결리스트로 구현하기
부모노드가 자식노드를 가리키게 하는 방법을 활용하여 구현

트리의 순회

전위 순회(preorder traversal):VLR
• 루트->왼쪽 자식->오른쪽 자식

중위 순회(inorder traversal):LVR
• 왼쪽 자식->루트 ->오른쪽 자식

후위 순회(postorder traversal):LRV
• 왼쪽 자식->오른쪽 자식->루트

이진탐색트리

탐색작업을 효율적으로 하기 위한 자료구조이다. 이진탐색 트리는 key(왼쪽서브트리)≤key(루트노드)≤key(오른쪽서브트리) 라는 특징이 있다. 또한, 이진탐색트리를 중위순회라면 오름차순으로 정렬된 값을 얻을 수 있다.

이진탐색트리의 ADT로는 탐색, 삽입, 삭제 등이 있는 탐색연산의 경우,
• 키 값이 루트와 같으면 -> 탐색이 성공적으로 끝난다.
• 키 값이 루트보다 작으면 -> 왼쪽 자식을 기준으로 다시 탐색
• 키 값이 루트보다 크면 -> 오른쪽 자식을 기준으로 다시 탐색
이러한 순서를 가지고 있고 탐색 연산의 경우 재귀(recursive)방식과 반복(iterative)방식을 사용할 수 있다.
탐색연산의 시간복잡도는 O(logN)이고 연결리스트에서 O(N)인반면, O(logN)으로 BST가 더 효율적인것을 알 수 있다.
다만, 이진트리가 균형적으로 생성되어있을 경우(최선의 경우)에는 O(logN)이지만, 변질 이진트리의 경우(최악의 경우) 시간복잡도가 O(n)이다.
BST의 삽입연산의 경우, 이진탐색 트리에 원소를 삽입하기 위해 먼저 탐색을 수행하고, 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치이다. 과정을 자세히 보면
• 우선 탐색을 반복해서 수행!
• 현재 Node의 값이 추가하려는 값과 동일 ->pass!
• 현재 Node의 값이 추가하려는 값보다 크다 ->왼쪽 노드로 이동!
• 현재 Node의 값이 추가하려는 값보다 작다 ->오른쪽 노드로 이동!
이와 같은 순서를 가진다.
삽입 연산의 시간복잡도로는
삽입은 탐색을 한 후 삽입하는 과정을 거치게 되는데
• 탐색: O(log(N))
• 새로운 노드 추가: O(1)
• 즉, 총 합은 O(log(N))!을 가진다.

다음은 BST의 삭제연산이다. 삭제연산은 다른 연산과 다르게 여러 경우의 수가 존재한다.

리프노드를 삭제하는 경우->그냥 삭제하면 됨!
삭제하려는 노드가 하나의 서브트리(자식)를 갖고 있을 경우->해당 노드를 삭제하고 그 자리에 자식 노드를 그대로 갖다 붙임!
삭제하려는 노드가 하나의 두 개의 자식(서브트리)을 갖고 있을 경우 -> 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져옴 => 후계 노드의 선택
BST에서 삭제연산의 시간복잡도는 삽입연산과 마찬가지로 탐색을 한 후 제거하는 과정을 거침!
• 탐색:O(log(N))
• 찾은 노드 제거:O(1)
즉, 총 합은 O(log(N))!