비선형 자료구조

그래프

노드와, 노드를 연결하는 간선인 edge로 이뤄진 비선형 자료구조이다.

• 트리는 그래프의 일종으로 cycle이 불가능하며 노드간 방향성이 존재하지만 그래프는 cycle이 가능하고 노드간 방향성이 존재하지 않아도 상관없다.

• 엣지에서 방향성이 존재하는 그래프를 방향 그래프(Directed Graph), 방향성이 없어 양방향으로 갈 수 있는 그래프를 무방향 그래프(Undirected Graph)라고 한다.

• Undirected Graph 에서 각 노드에 연결된 Edge 의 개수를 Degree 라 한다. Directed Graph 에서는 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.

• 자기 자신을 향하는 간선은 없다.

• 중복된 간선을 허용하지 않는다.

• 인접 행렬과 인접 리스트 방식으로 구현할 수 있다.

인접행렬

인접 행렬은 노드의 수가 N인 경우 N*N의 형태로 2차원 행렬을 만들고 각 노드간 edge를 표현한 방식이다. 두 노드간 연결된 정보를 확인할 떄 O(1)의 시간 복잡도로 접근이 가능하지만 edge의 수와는 무관하게 항상 N^2의 메모리 공간이 필요하고 인접행렬을 만드는 과정에서도 N^2의 시간복잡도가 소요된다.

인접 리스트

인접 리스트는 각각의 노드에 대해 인접한 노드가 edge로 연결된 상태를 리스트로 만들어 표현하는 방식이다. 인접 리스트는 상대적으로 edge수가 많을 경우 메모리 공간에서 비효율적이며, 두 노드간 연결 여부를 확인하는 과정이 인접행렬보다는 시간이 더 걸린다. 시간 복잡도는 O(V+E)이다. (노드 + 엣지)

그래프 탐색

그래프의 모든 정점을 탐색하기 위한 방법은 다음의 두 가지 알고리즘을 기반으로 한다.

깊이 우선 탐색 (Depth First Search: DFS)

갈 수 있는 만큼 최대한 깊이 방문하고, 더 이상 갈 곳이 없다면 이전 노드로 돌아가며 방문할 수 있는 노드를 탐색하는 기법이다. 주로 Stack을 사용한다.

너비 우선 탐색 (Breadth First Search: BFS)

임의의 한 노드로부터 연결되어 있는 모든 인접 노드를 순차적으로 방문해 나가는 탐색 알고리즘이다. 노드를 방문할 순서를 기록하기 위해 BFS 에서는 자료구조로 Queue 를 사용한다. 최단경로를 얻을 수 있는 알고리즘이다. DFS와 달리 큐를 이용하여 다음에 탐색할 정점들을 저장하므로 더 큰 저장공간이 필요하다.

트리

트리는 Node와 edge를 이용하여 사이클이 이루어지지 않게 구성된 비선형 자료구조이다.

• 루트에서 한 노드로 가는 경로는 유일하다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
• 주로 계층적 구조를 표현할 때 사용된다.
• 배열이나 연결리스트로 구현할 수 있다
  • 배열을 사용하면 노드 접근이 빠르고 구현이 용이하다는 장점이 있지만, 편향 이진트리 같은 경우 많은 공간이 낭비될 수 있고 배열 크기 이상 노드를 추가할 수 없다.

트리 순회 방식

1. 전위 순회(pre-order)
   (Root → 왼쪽 자식 → 오른쪽 자식)

2. 중위 순회(in-order)
   (왼쪽 자식 → Root → 오른쪽 자식)

3. 후위 순회(post-order)
   (왼쪽 자식 → 오른쪽 자식 → Root)

4. 레벨 순회(level-order)
   루트(Root)부터 계층 별로 방문하는 방식이다.

트리 종류

1. Binary Tree (이진 트리)

자식 노드가 공백이거나 최대 2개인 트리 구조이다. 배열로 구성된 Binary Tree는 노드의 개수가 n 개이고 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.

• 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

• 포화 이진 트리 (Perfect Binary Tree) : 포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다.

• 정 이진트리 (Full Binary Tree or Strict Binary Tree) :
  전 이진 트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다

• 균형 이진 트리 (Balanced Binary Tree) :
  균형 이진 트리는 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리이다.

2. 이진탐색트리 (Binary Search Tree)

이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종이며, 이진탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제를 가능하도록 고안되었다.

• 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 하지만 삽입,삭제가 불가능
• 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), 하지만 탐색하는 시간복잡도가 O(N)

이진 탐색 트리는 다음의 조건을 만족해야 한다.

• 왼쪽 서브 트리는 해당 노드의 값보다 작다. 오른쪽 서브 트리는 해당 노드의 값보다 크다.
• 중복되는 값이 없다.
• 서브트리는 이진 탐색 트리를 만족한다.

이진 탐색 트리의 조회방식

• 조회하고자하는 값과 루트 노드를 비교하며 시작한다.
• 조회하고자하는 값이 노드의 값 보다 크다면 오른쪽, 작다면 왼쪽 서브트리로 이동한다.
• 이 과정을 반복하며 탐색을 진행한다.

이진 탐색 트리의 삭제방식

• 삭제하려는 노드가 단말 노드인 경우 메모리를 반납하면 쉽게 삭제할 수 있다.
• 삭제하려는 노드가 하나의 자식 노드를 가지고 있는 경우 해당 노드의 부모 노드와 자식노드를 연결 시켜주면 된다.
• 삭제하려는 노드가 두 개의 자식 노드를 가지고 있는 경우 왼쪽 서브트리의 최대 값 혹은 오른쪽 서브트리의 최소 값을 위치시킨다.

이진 탐색 트리의 시간 복잡도는 트리가 고르게 분포한 경우 시간복잡도는 logn으로 계산되지만 트리가 한쪽으로 치우친 경우 트리의 높이는 결국 선형 탐색과 다를바 없어지고 이때 시간 복잡도는 O(N)으로 계산 된다.

따라서 균형 잡힌 이진 검색트리로 대표적인 것은 레드블랙트리와 AVL트리다.

AVL 트리

한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지고 탐색에 있어 비효율적이기 때문에 이를 방지하고자 avl 트리가 고안되었다.

AVL 트리는 이진 탐색 트리의 속성을 가지고 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1인 자료구조이다.

• AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 이다.
• 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄인다.

Red Black Tree

이진 탐색 트리를 기반으로 하는 균형 이진 탐색 트리로서 각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 맞춘다.

• 모든 노드는 RED이거나 BLACK이다.
• 루트는 BLACK이다.
• 모든 leaf node 는 black이다.
• 노드가 RED이면 그 노드의 자식은 모두 BLACK이다.
• 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 BLACK 노드를 포함한다.

search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요된다. 삽입이나 삭제 후 레드블랙특성을 위반하는 경우가 발생할 수 있따. 이때는 적절한 작업을 통해 레드블랙 특성을 만족하다록 바로잡아 주어야 한다.

AVL Tree와 Red Black Tree 차이

• AVL Tree가 Red Black Tree보다 빠른 Search를 제공
• Red Black Tree은 AVL Tree보다 빠른 삽입과 제거를 제공
  • AVL Tree가 더 엄격한 Balanced를 유지하고 있기 때문
• Red Black Tree는 AVL Tree보다 색깔을 저장하기 위해 더 많은 Space Complexity가 필요
• 자바에서 Collection에서 ArrayList의 내부적인 알고리즘이 RBT로 이루어져 있다.
• 자바의 Map에서 HashMap의 Separate Chaining(LinkedList로 Hash 충돌을 해결하는 방법)에서 사용된다

Heap

힙은 우선 순위 큐를 위한 완전 이진 트리 구조로서 대표적으로 최대 힙과 최소 힙으로 나뉠 수 있다. 힙 구조는 정렬기준에 따라 값이 미리 정렬되면서 저장되므로 O(1)의 시간복잡도로 출력이 가능하다. 데이터를 삽입하고 삭제하는 과정에서도 정렬이 필요하기 때문에 O(logn)의 시간 복잡도가 소요된다.

최대힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

• 중복된 값 허용
• 힙을 저장하는 표준적인 자료구조는 배열 이다.
  • 완전이진트리를 기본으로 하기 때문에 비었는 공간이 없어 배열로 구현하기에 용이

트라이(Trie)

정수형에서 이진탐색트리를 이용하면 시간복잡도 O(logN), 하지만 문자열에서 적용했을 때, 문자열 최대 길이가 M이면 O(M*logN)이 된다. 트라이는 문자열에서 검색을 빠르게 도와주는 자료구조 이다. O(M)으로 문자열 검색이 가능하다.

• 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다.
• 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리
• 필요한 메모리의 크기가 너무 크다. (O(포인터 크기 포인터 배열 개수 트라이에 존재하는 총 노드의 개수))