CS 부수기 - 비선형 자료 구조 편

0. 들어가며, Nonlinear Data Structure

---

이번 포스팅에서는 비선형 자료 구조에 대해서 알아본다.

선형 자료 구조에 대해서는 포스팅을 확인하면 된다.

비선형 자료 구조(Nonlinear Data Structure)의 의미는 다음과 같다.

비선형 자료 구조 : 하나의 원소 뒤에 여러개의 원소가 따라오는 것을 말하며 1:다 혹은 다:다의 형태를 띄는 자료구조

대표적인 비선형 자료 구조에는 그래프(Graph), 트리(Tree), 힙(Heap)이 있다.

1. Graph

---

그래프(Graph)란, 정점(Node or Vertex)과 간선(Edge)로 이루어진 자료 구조이다.

다음은 그래프의 기본적인 형태이며 이해를 돕기 위한 사진이다.

그래프의 이해를 돕기 위한 사진

• Graph
  • 용어
    • 정점 (Node or Vertex) : 데이터의 저장 위치
      • 위의 사진에서 (1), (2), (3), (4)에 해당
    • 간선 (Edge) : 정점끼리 연결하는 선
    • 인접 정점 : 간선에 의해 직접 연결한 정점
      • 위의 사진에서 (1) 기준으로 (2), (3), (4)에 해당
    • 차수(Degree) : “무방향 그래프”에서 하나의 정점에 대한 인접 정점의 개수
      • 위의 사진에서 (1) 기준으로 차수 3
    • 진출 차수(Out - Degree) : “방향 그래프”에서 하나의 정점에서 외부로 향하는 간선 개수
    • 진입 차수(In - Degree) : “방향 그래프”에서 하나의 정점으로 들어오는 간선 개수
  • 종류
    • 무방향 그래프 : 간선에 방향이 없는 그래프
      • 사진
    • 방향 그래프 : 간선에 방향이 있는 그래프
      • 사진
    • 가중치 그래프 : 정점 간 이동 시 비용이 드는 그래프
      • 사진
    • 완전 그래프 : 모든 정점이 간선으로 연결된 개수
      • 완전 그래프의 간선 개수 : n(n-1) / 2
      • 사진

2. Tree

---

트리(Tree)란, 그래프의 특징처럼 정점과 간선으로 이루어지며 트리 즉, 나무의 구조로 배열된 계층적 데이터 집합이다.

다음의 트리에 대한 사진이다.

트리의 이해를 돕기 위한 사진

• Tree
  • 용어
    • 루트 노드 (Root Node) : 최상위 노드
      • 위의 사진에서 (1)에 해당하는 노드
    • 리프 노드 (Leaf Node) : 자식이 없는 노드
      • 위의 사진에서 (4), (5), (6) 노드에 해당
    • 깊이 (Depth) : 루트 노드부터 특정 노드까지의 최단 거리
      • 위의 사진에서 (1)번 노드부터 (5)번 노드까지의 깊이는 2
    • 높이 (Height) : 루트 노드부터 리프 노드까지의 가장 긴 거리
      • 위의 사진에서 높이는 2
    • 레벨 (Level) : 루트 노드를 0레벨로 하며 각 깊이마다 1씩 증가
      • 위의 사진에서 (2), (3) 노드는 레벨 1, (4), (5), (6) 노드는 레벨 2
    • 부모 노드 (Parent Node) : 자식 노드를 가진 노드
      • 위의 사진에서 (2), (3) 노드의 부모 노드는 (1) 노드
    • 자식 노드 (Child Node) : 부모 노드의 하위 노드
      • 위의 사진에서 (1) 노드의 자식 노드는 (2), (3) 노드
    • 형제 노드 (Sibling Node) : 같은 부모를 가지는 노드
      • (2), (3) 노드는 서로 형제 노드
  • 종류
    • 이진 트리 (Binary Tree) : 자식의 노드 수가 두 개 이하인 트리 (위의 사진과 같은 형태의 트리)
      • 정이진 트리 : 자식 노드 수 없거나 두 개인 이진 트리
        • 사진
      • 완전 이진 트리 : 왼쪽에서부터 채워진 이진 트리, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 형태
        • 사진
      • 변질 이진 트리 : 자식 노드가 하나밖에 없는 이진 트리
        • 사진
      • 포화 이진 트리 : 모든 노드가 꽉 찬 이진 트리
        • 사진
      • 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리
        • 사진
    • 이진 탐색 트리 (Binary Search Tree, BST) : 오른쪽 하위 트리는 부모 노드보다 큰 값, 왼쪽 하위 트리에는 부모 노드보다 작은 값이 들어가는 형태의 트리
      • 사진
    • AVL 트리 (Adelson-Velsky and Landis Tree, AVL Tree) : 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
      • 사진

3. Heap

---

힙(Heap)이란 힙 트리(Heap Tree)라고도 하며, 완전 이진 트리 기반의 자료 구조로 최소힙(Min Heap)과 최대힙(Max Heap)이 있다.

최솟값과 최댓값을 빠르게 탐색하기 위한 자료구조이다.

최대힙(Max Heap)이란, 루트 노드가 모든 자식 중 데이터 값이 가장 큰 힙을 의미한다.
최소힙(Min Heap)이란, 최대힙과는 반대로 루트 노드가 모든 자식 중 테이터 값이 가장 작은 힙을 의미한다.

그리고 최대힙과 최소힙은 이러한 모든 특성이 재귀적으로 이루어진다.

사진으로 보면 다음과 같다.

최대힙의 이해를 돕기 위한 사진

최소힙의 이해를 돕기 위한 사진

4. 정리하며

---

비선형 자료 구조는 이 정도로 마무리 된다.

다음 포스팅부터는 알고리즘에 대해서 공부하고 리뷰할 예정이다.

Adios.