비선형 자료 구조

기술노트

비선형 자료 구조

---

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조

  • 트리
  • 그래프

1. 그래프(graph)

---

정점(vertext)과 간선(edge)으로 이루어진 집합

  • 단방향 간선, 양방향 간선
  • 정점의 outdegree : 정점으로 나가는 간선
  • 정점의 indegree : 들어오는 간선
  • 정점은 V 또는 U라고 한다.
  • U에서부터 V로 간다 : 어떤 정점으로부터 시작해서 어떤 정점까지 간다.

가중치

간선과 정점 사이에 드는 비용
  • 1번 노드와 2번 노드까지 가는 비용이 한 칸이라면, 1번 노드에서 2번 노드까지의 가중치는 한 칸이다.

2. 트리

---

정점과 간선으로 이루어져 있으며, 트리 구조로 배열된 일종의 계층적 데이터의 집합

  • 구성 : 루트 노드, 내부 노드, 리프 노드 등
  • 숲 : 트리로 이루어진 집합

특징

1. 부모, 자식 계층 구조를 가진다. 같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 된다. 2. V - 1 = E (간선 수 = 노드 수 - 1) 3. 임의의 두 노드 사이의 경로는 `유일무이` 하게 `존재` 한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.

구성

  • 루트 노드 :가장 위에 있는 노드
   - 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다.
  • 내부 노드 : 루트 노드와 내부 노드 사이에 있는 노드
  • 리프 노드 : 자식 노드가 없는 노드

트리의 높이와 레벨

  • 깊이 : 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
  • 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
  • 레벨 : 깊이와 같은 의미
  • 서브트리 : 트리 내의 하위 집합으로, 트리 내에 있는 부분집합이라고도 한다.

이진 트리

자식의 노드 수가 두 개 이하인 트리

분류

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

이진 탐색 트리(BST)

노드의 오른쪽 하위 트리에는 ‘노드 값보다 큰 값’이 있는 노드만 포함되고, 왼쪽 하위 트리에는 ‘노드 값보다 작은 값’이 들어 있는 트리를 말한다.

  • 왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있어서 검색에 용이하다.
  • 요소를 찾을 때 시간 복잡도 : O(log n)
  • 최악의 경우 : O(n) - 삽입 순서에 따라 선형적일 수 있기 때문이다.

AVL 트리(Adelson-Velsky and Landis tree)

최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리

  • 두 자식 서브트리의 높이는 항상 최대 1만큼 차이가 난다.
  • 선형적인 트리 형태를 가질 때 시간 복잡도 : 최악의 경우 O(n)
  • 탐색, 삽입, 삭제 시간 복잡도 : O(log n)
   - 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.
  • 최악의 경우를 배제하고 항상 균형 잡힌 트리로 만들자.

레드 블랙 트리

균형 이진 탐색 트리

  • 탐색, 삽입, 삭제 시간 복잡도 : O(log n)
  • 각 노드는 빨간색 또는 검은색 색상을 나타내는 추가 비트를 저장한다.
  • 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용된다.
  • 모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

3. 힙

---

완전 이진 트리 기반의 자료 구조로, 최소힙과 최대힙이 있다. 해당 힙에 따라 특정한 특징을 지킨 트리이다.

  • 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
  • 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
  • 힙에는 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다.

최대힙의 삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킨다.

예를 들어, 8이라는 값을 가진 노드 밑에 15라는 값을 가진 노드를 삽입한다고 하면 이 노드가 점차 올라가면서 해당 노드 위에 있는 노드와 스왑하는 과정을 거쳐 최대힙 조건을 만족하게 된다.

최대힙의 삭제

최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하며 또다시 스왑 등의 과정을 거쳐 재구성된다.

4. 우선순위 큐

---

우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조

  • 힙을 기반으로 구현

5. 맵

---

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조

  • 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다.
  • map.put()
  • get : key에 해당하는 value값을 얻는다.
   - getOrDefault : null 대신 디폴트 값을 얻고 싶은 경우에 사용
  • size : Map 갯수 리턴
  • remove : 맵의 항목 삭제하는 메서드
   - key값에 해당되는 아이템(key, value)을 삭제한 후 그 value 값을 리턴한다.
  • keySet : 맵(Map)의 모든 Key를 모아서 리턴한다.

`keySet()` 메서드는 Map의 모든 Key를 모아서 Set 자료형으로 리턴한다. Set 자료형은 잠시후에 알아본다. Set 자료형은 다음과 같이 List 자료형으로 바꾸어 사용할수도 있다. 

List<String> keyList =newArrayList<>(map.keySet());

6. 셋(set)

---

특정 순서에 따라 고유한 요소를 저장하는 컨테이너

중복되는 요소는 없고 오로지 희소한(unique) 값만 저장하는 자료 구조

7. 해시 테이블

---

무한에 가까운 데이터(키)들을 유한한 개수의 해시 값으로 매핑한 테이블

이를 통해 작은 크기의 캐시 메모리도로 프로세스를 관리하도록 할 수 있다.

  • 삽입, 삭제, 탐색 시간 복잡도 : O(1)
원본 주소 "https://technote.wiki/index.php?title=비선형_자료_구조&oldid=259"