들어가기 전

이번 블로깅에선 비선형 자료구조 에 대해 넓고 얕게 배워보자.
우선 비선형 자료구조는 배열이나 백터처럼 일렬로 나열한 것이 아닌 자료 순서나 관계가 복잡한 구조를 말한다. 그 예시로는 트리나 그래프가 있다.
이제부터 이에 각각에 대해 배워보자.

그래프

그래프는 현재 우리 자동차 도로를 생각하면 좋다. 지역과 지역이 있고 이를 연결하는 도로가 있다. 이러한 자료 형태를 그래프라 부른다.

간선과 정점

이때 이 도로는 간선(edge) 이라고 부르며, 지역을 정점(vertex) 이라고 부른다.

단방향 간선 과 양방향 간선

도로의 종류도 여러개가 있는데 어떠한 도로 같은 경우에는 한 쪽 방향으로만 가는 일반통행 이 있을 것이고, 양쪽 방향으로 모두 갈 수 있는 도로가 있다.
이러한 일반통행을 부르는 말이 단방향 간선 이라고 부르며, 양쪽 모두를 갈 수 있다면 양방향 간선 이라고 부른다.

outdegree와 indegree

한 정점 기준에서 나가는 간선을 outdegree 라 부르며 들어오는 간선을 indegree 라고 부른다. 이는 상대적인 단어로 정점 마다 다르다.

가중치

가중치는 간선과 정점 사이에 드는 비용을 말한다. 이는 아까 말한 도로를 기억해보자.
A->B라는 지역을 갈때 도로마다 드는 비용이 다를 것이다. 어떤 도로는 돌아서 가서 거리가 멀수도 있고 톨게이트 비용 같은 것이 들 수도 있다.
이렇듯 정점에서 다른 정점으로 이동할때 간선의 비용을 가중치라고 부른다.
이렇듯 간선에 가중치를 부여할 수도 있다.

지금까지 말한 정점 + 간선의 집합 을 그래프 라고 부른다.

트리

트리(Tree)란 무엇일까?
트리는 앞에서 배운 그래프 중의 하나로 정점과 간선으로 이루어져 있다.
가장 큰 특징으로는 계층적 데이터의 집합입니다. 각각이 부모 자식 관계를 가진다는 말이다. 아래 그림처럼 위에 정점이 부모에 해당하고 그 아래 연결 되어진 정점들이 자식들이 되는 구조이다.

참고로 이 트리들이 모여진 집합을 숲 이라고 한다.

특징

1. 부모 자식 계층 구조를 가진다. 위에 그림 5번을 기준으로 말하면 5번이 부모 노드, 6번과 7번이 노드가 자식 노드가 된다.
2. 간선 수 = 노드 수 - 1 ( V - 1 = E )
3. 트리에 있는 노드를 연결해주는 경로는 항상 존재한다. 어떠한 노드에서든 다른 노드에 갈 수 있다. 다른 부모나 자식을 타고타고 갈 수 있다.

트리의 구성

1. 루트 노드
   -> 가장 최상위 노드를 뜻하며 가장 위에 있는 노드를 말한다.

2. 내부 노드
   -> 루트 노드와 외부 노드 사이에 있는 노드를 뜻한다.

3. 리프 노드 ( 외부 노드 )
   -> 자식 노드가 없는 노드를 뜻하며 가장 밖에 있는 노드를 뜻한다.

트리의 다른 용어 설명

1. 깊이
   -> 깊이는 루트 노드부터 그 대상 노드까지 최단 거리를 말한다.
   참고로 루트노드의 깊이는 0 이다.
2. 높이
   -> 높이는 트리에서 가장 긴 거리를 뜻한다. 위에 사진 그림 기준에서 높이는 3이다. 이또한 루트노드를 0이라고 생각하고 카운트 해주면 쉽게 구할 수 있다.
3. 서브트리
   -> 트리 내의 하위 집합을 서브트리 라고 한다. 이는 트리 안에 부분 집합을 말한다. 위 자료 기준에선 5,6,7번 노드의 집합, 8,9,10번 노드이 집합 등이 서브트리가 될 수 있다.

이진 트리

트리도 여러가지로 나뉘는데 그 중 대표적인 것이 이진 트리이다.
이진 트리 는 자식의 노드 수가 두개 이하인 트리를 의미한다.
이진 트리도 형태에 따라 여러가지로 나뉘는데 아래가 그 예시이다.

1. 정 이진 트리(Full Binary Tree): 자식 노드가 0 또는 2개인 이진 트리를 의미한다. 아예 없거나 꽉 차 있는 형태를 말한다.
2. 완전 이진 트리(Complete Binary Tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
3. 변질 이진 트리(Degenerate Binary Tree): 자식 노드가 하나밖에 없는 이진 트리를 의미한다.
4. 포화 이진 트리(Perfect Binary Tree): 모든 노드가 꽉 차있는 이진 트리를 의미힌다.
5. 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미힌다. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나다.

이진 탐색 트리

이진 탐색 트리 (BST) 는 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값 이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값 이 들어가 있는 트리를 말한다.

이렇게 해두는 이유가 무엇일까? 검색이 매우 쉬워진다. 만약 10을 찾아야 된다면 루트 노드부터 작으면 왼쪽, 크면 오른쪽으로 이동해서 찾으면 비교적 빠르게 찾을 수 있다. 이때 O(logn) 시간으로 처리가 가능하다.

하지만 트리가 저렇게 예쁘게 균형있게 나눠져 있을까?
최악의 경우에는 아래와 같이 선형적으로 되어 있을 수 있다. 이때는 O(n)이 걸린다.

이 때문에 나온 것이 뒤에 설명할 AVL트리 이다.

AVL 트리

AVL 트리 (Adelson - Velsky and Landis tree)는 앞서 말한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다.

두 자식 서브트리의 높이를 최대 1만큼을 둔다는 특징을 가지고 균형을 잡아간다. 삽입, 삭제, 탐색 등 모두 시간 복잡도가 O(logn)을 유지할 수 있다. 만약 균형이 안맞는다면, 트리 일부를 왼쪽 혹은 오른쪽으로 회전하여 이를 균형을 맞춰 위의 시간복잡도를 가능하게 한다.

레드 블랙 트리

이는 균형 이진 탐색 트리로 O(logn)의 시간복잡도를 가지고 있다.
각 노드는 빨간색 또는 검은색 색상을 나태는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용된다. 이래서 이름이 위와 같이 지어졌다.

참고로 모든 리프 노드와 루트노드는 블랙이고 어떤 노드가 레드이면 그 자식은 반드시 블랙이라는 규칙을 가지고 있으며 이를 가지고 균형을 잡는다.

힙

힙은 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있다.

1. 최대힙
   -> 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한, 각 노드의 자식 노드와의 관계에도 이와 같으 특징이 재귀적으로 이루어져야 한다.

2. 최소힙
   -> 최소 힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

이러한 힙에는 설정된 규칙을 기반으로 만들어져 있다. 이는 대입, 삭제 등 연산에서도 마찬가지이다.

최대힙의 삽입

예시로 최대힙의 삽입을 들어보겠다.

만약 8이라는 노드에 15를 삽입한다고 가정해보자. 그러면 15와 8을 비교해서 크니깐 자리를 바꾼다. 또 14와 15를 비교해서 15를 올린다. 이런식으로 최대힙의 규칙을 지키게 삽입이 진행된다

삭제도 마찬가지로 삭제 후에 정렬이 이루어진다.

우선순위 큐

우선순위 큐는 말 그대로 데이터에 우선순위가 존재하고 이 순서대로 제공되는 자료구조이다. 우선 순위가 높으면 이를 먼저 제공하는 형태이다. 이는 힙을 기반으로 구현된다.

참고로 우선순위를 큰 값이 높은 우선순위를 가질지, 작은 값이 가질지는 정할 수 있다.

맵

맵(map) 은 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조이다.
ex) "홍길동" : 1, "김철수" : 2
위 예시처럼 key값에 어떤 값을 매칭 시킨다던지 할때 맵을 사용한다.
이는 앞서 설명한 레드 블랙 트리 방식으로 형성된다.
-> JS 도 Map() 함수가 존재하여 이를 이용할 수 있다.

key : value 형식으로 값을 저장

셋

셋(Set)은 배열처럼 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이다. 하지만 가장 큰 차별점은 중복되는 요소가 없다 는 것이다.
같은 요소를 Set에 넣으면 하나만 저장한다.
-> JS 도 Set() 함수가 존재하여 이를 이용할 수 있다.
Map과 유사하지만 중복 요소가 없다는게 차이점이다.

해시 테이블

해시 테이블은 Map에서 순서가 없는 방식으로 구현되며 해시 값을 통해 매핑을 진행하는 자료구조이다.
삽입 시 Map과 똑같이 key, value로 값을 삽입하며 삭제, 탐색 시에 설정해준 key값을 통해 탐색하고 삭제한다.
이 덕분에 시간복잡도가 상수시간 O(1)을 가진다.

마무리

이번 블로깅에선 비선형 자료구조 에 대해 알아보았다. 이 블로깅의 목적은 깊게 배우는 것이 아니라 개발자 대회에 낄 정도의 넒고 얕은 지식을 목표로 하고 있다. 이 블로깅을 통해서 전체적인 비선형 자료구조 에 대해 잡았으면 좋겠다. 그리고 감을 잡았고 좀 더 깊게 배우고 싶다면 이 블로깅의 키워드를 길로 잡아서 하나씩 공부해 나간다면 매우 도움이 될 것이라고 생각한다.