비선형 자료구조

비선형 자료구조 (NonLinear)

• 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것

• 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계

• 트리와 그래프가 대표적이며 계층적 구조를 나타내기에 적절

• <-> 선형 자료구조 (Linear)

  • 하나의 자료 뒤에 하나의 자료가 존재하는 것
  • 자료들 간의 앞뒤 관계가 1:1의 선형관계
  • 배열과 리스트가 대표적이고 더 나아가서 스택, 큐도 이에 해당
    => 이 부분은 나중에 또 정리해보도록 하자!!!

그래프 (Graph)

• 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어진 자료구조

• G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 뜻

• V(G)는 그래프 G의 정점 집합이고, E(G)는 그래프 G의 간선 집합

• 간선은 (정점 v, 정점 w)형식

• 아래에서 설명할 트리도 그래프의 한 종류이다.

• 예시
  

• 용어

  • 정점(Vertex): 노드(node), 데이터 저장
  • 간선(Edge): 정점을 연결하는 선
  • 분지수(차수, degree): 무방향 그래프에서 하나의 정점에 붙어있는 간선 개수
    • 내향 분지수(진출 차수, in-degree): 방향 그래프에서 들어오는 간선의 수
    • 외향 분지수(진입 차수, out-degree): 방향 그래프에서 나가는 간선의 수
  • 인접
    • 인접(adjacent): 정점 사이 간선이 있음
    • 부속(incident): 정점과 간선 사이 관계
  • 경로(path): 출발지에서 목적지로 가는 순서
    • 단순 경로(simple path): 경로 중 반복되는 정점이 없음, 한붓그리기처럼 같은 간선 지나지 않음
    • 사이클(cycle): 단순 경로의 출발지와 목적지가 같은 경우

• 종류
  

  • 무방향 그래프(Undirected Graph)
    • 간선에 방향이 없는 그래프
    • 정점 v와 정점 w를 연결하는 간선을 (v, w)라고 하면, (v, w)와 (w, v)는 같은 간선
    • 정점 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개
  • 방향 그래프(Directed Graph)
    • 간선에 방향이 있는 그래프
    • 정점 v에서 w로 가는 간선을 (v, w)라고 하고, 이때는 간선 (w, v)와 다름
    • 정점 n개일 때 방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)개
  • 완전 그래프(Complete graph)
    • 모든 정점에 간선이 있고, 한 정점에서 다른 정점과 모두 연결
      
  • 가중치 그래프(Weighted graph)
    • 간선에 가중치(=비용)가 존재
      

• 자세한 구현 방법이나 순회 (BFS/DFS) 는 아직 이해도 잘 안가고 구현하기 힘듬
  -> 일단은 "출처"를 참고하자!!
  -> 코딩 테스트를 할 때 BFS/DFS가 많이 나오는 거 같은데, 아직 구현할 줄 모르니까 연습하자~

트리 (Tree)

• 노드들이 나무 가지처럼 연결된 비선형, 계층적 자료구조로 위 그림처럼 나무를 거꾸로 뒤집어 놓은 것과 같은 모양이어서 트리(tree)라는 이름을 가지게 된 자료구조

• 데이터 구조의 상하 개념 계층의 구조적 속성을 표현

• 컴퓨터의 파일, 폴더의 계층 구조 등

• 용어
  

  • Node: 트리 구조에서 각 구성요소를 의미하는 단위
    -> 위 그림에서는 A~J까지를 모두 Node
  • Root Node: 트리의 시작 노드로, 부모가 없는 최상위 노드
    -> 위 그림에서 A노드를 의미
    -> 트리는 최대 1개의 Root Node를 가짐
  • Edge: 노드와 노드 간의 연결을 하는 선
  • Path: 특정 노드에서 노드까지의 경로 (순서)
    -> 한 번 지나쳤던 경로를 다시 지나는 것은 허락 X
  • Terminal Node(Leaf Node): 자식 노드가 존재하지 않는, 즉 다시 말해 밑으로 또 다른 노드가 연결 되어있지 않는 노드
    -> 위 그림에서 H, I, J, F, G와 같은 노드
  • Sub-Tree: 전체 큰 트리 구조 안의 작은 트리 구조
    -> 트리의 재귀적인 특성
  • Depth: 루트 노드로부터 얼마나 떨어져 있는 지를 뜻하는 단위
    -> 루트 노드의 바로 아래 노드는 depth 1
    -> 루트 노드가 기준이기 때문에 루트 노드는 depth 0
  • Level: 트리 구조에서 같은 위치, 즉 같은 depth를 가지는 노드들을 한 레벨로 나타내는 단위
    -> Root Node가 기준이고 이 위치를 level 0
    -> 루트 노드에서 어떤 노드까지의 간선 수
  • Height: 트리에서 가장 최고 레벨, 가장 깊은(deep) 층
    -> 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수
  • Order: 부모 노드가 가질 수 있는 최대 자식의 수
    -> 예를 들어 order 4라고 하면 부모 노드는 최대 3명의 자식 노드를 가질 수 있는 것

• 종류
  • 편향 트리(skew tree)
    • 모든 노드들이 자식 노드를 하나씩만 가진 트리
    • 경사 트리라고도 함
      -> 또한 아래 그림은 왼쪽 자식만 존재하기 때문에 left skew tree
      
  • 이진 트리(Binary Tree)
    • 각 노드의 차수(자식 노드)가 2이하인 트리 구조
  • 이진 탐색 트리(Binary Search Tree, BST)
    • BST라고도 하며 순서화된 이진 트리
    • 노드의 왼쪽 자식은 부모의 값보다 항상 작은 값을 가져야 하고 노드의 오른쪽 자식은 부모의 값보다 항상 큰 값을 가져야 한다
  • m원 탐색 트리(m-way Search Tree)
    • 최대 m 개의 서브 트리를 갖는 탐색 트리
    • 이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용
  • 균형 트리(Balanced Tree, B-Tree)
    • m원 탐색 트리에서 높이 균형을 유지하는 트리
    • height-balanced m-way tree
• 마찬가지로 조금 더 자세한 내용은 "출처"를 참고하자
  -> 이진 트리에 대한 내용과 구현 방법 등이 자세하게 설명되어 있는 듯
  -> 아무래도 자료구조에 대한 지식이나 구현 방법에 대한 것이 아직 준비 안되어있는 거 같다 ㅠㅠ

힙 (Heap)

• 이진트리의 일종이며 정렬된 상태가 아니며, 완전이진트리와는 다르게 중복값이 허용

• 삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠름

• 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적

• 종류

  • 최대힙 : 부모노드가 자식노드보다 큼
  • 최소힙 : 부모노드가 자식노드보다 작음

• 보통 배열을 사용하며, 0번째 인덱스는 계산을 편하게 하기위해 사용하지 않음
  -> 부모노드의 인덱스가 1

• 모든 부모와 자식 간의 인덱스 관계는 부모:N, 왼쪽자식:2N, 오른쪽자식: 2N+1

• 마찬가지로 "출처"에 자세한 구현 방법과 예시 문제들이 있으니 참고하고 풀어보자~

맵 (Map)

• 사전과 비슷, Key와 Value라는 것을 한 쌍으로 갖는 자료형

• 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 Key를 통해 Value를 얻음
  -> 순서보다는 정의된 이름(Key)과 상응하는 데이터들을 묶기 위한 자료 구조로서 효과적

• 리스트와 같이 인터페이스임

• Key의 중복을 허용하지 않아야 됨

• 종류

  • HashMap
    • key와 value의 쌍으로만 구성이 될뿐 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없음
      -> 사용자는 키와 값이 구성되는 위치를 결정 하거나 알 수 없음
  • TreeMap
    • key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조
    • key값을 통한 탐색 뿐 아니라 key값의 정렬을 통한 탐색 등을 하기에 용의
  • LinkedHashMap
    • 데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조
    • 배열, 리스트처럼 인덱싱 접근을 하기에 용의

해시 테이블 (Hash Table)

• 값을 저장하고 조회하는데 있어 가장 빠른 알고리즘

• 저장하고자 하는 값을 어떤 값과도 중복되지 않는 숫자 코드로 변환(이를 해시 코드라 지칭)하여 해당 코드의 메모리 위치에 값을 저장하는 방법
  -> 저장하려는 값을 일련의 공식을 통해 해시코드로 변환된 값이, 저장되는 위치

• 값을 고유한 코드(해시코드)로 변환하여 해당 코드 위치에 값을 저장하고 조회하는 방법을 해시 테이블(=해시)이라 함

셋 (Set)

• 중복을 허용하지 않으며, 순서를 유지하지 않는 데이터의 집합

• 종류

  • HashSet
    • 순서 및 정렬을 하지 않는 가장 단순한 Set이다. 덕분에 가장 빠른 임의 접근 속도
  • LinkedHashSet
    • HashSet과 흡사
    • 연결 리스트를 사용해서 데이터를 저장하기 때문에 Key의 순서를 보장
  • TreeSet
    • 이진 탐색 트리(레드-블랙 트리)의 형태
    • 데이터를 정렬된 순서로 저장, 정렬된 상태를 유지하기 위해 시간이 다소 오래 걸림
    • 정렬 방법을 지정 가능

면접 대비

Q: 비선형 자료구조는 어떤 특징을 가지고 있나요?
A: 비선형 자료구조는 선형 자료구조와 달리 각 요소가 일렬로 연결되어 있지 않고, 계층적인 구조나 네트워크 형태를 가지고 있습니다. 주요 특징은 다음과 같습니다.
첫째로, 계층적 구조를 가집니다. 트리(Tree)나 그래프(Graph)와 같은 비선형 자료구조는 부모와 자식 노드 간의 계층적인 구조를 갖고 있어서 데이터를 효과적으로 구조화할 수 있습니다.
둘째로, 순서가 정해져 있지 않습니다. 선형 자료구조와는 달리 요소들 간에 명시적인 순서가 정해져 있지 않아서 자유롭게 관계를 형성할 수 있습니다.
셋째로, 루프(loop)가 발생할 수 있습니다. 그래프와 같은 비선형 자료구조는 순환 구조를 가질 수 있어서 자기 참조적인 관계를 형성할 수 있습니다.
넷째로, 메모리 관리가 중요합니다. 비선형 자료구조는 동적인 크기를 가질 수 있고, 메모리의 효율적인 관리가 필요합니다.
이러한 특징들을 고려하여, 데이터 간의 복잡한 관계를 표현하고 다양한 상황에 유연하게 대응할 수 있는 자료구조를 선택하는 데 사용됩니다.

Q: 트리와 그래프의 차이가 무엇인지 설명해 주세요.
A: 트리와 그래프는 둘 다 비선형 자료구조로서 계층적인 구조를 가지고 있지만, 몇 가지 중요한 차이점이 있습니다.
첫째로, 계층 구조의 정의입니다. 트리는 각 노드가 하나의 부모 노드를 가지며, 최상위 노드를 제외한 모든 노드는 하나의 부모 노드와 연결돼 있습니다. 반면에 그래프는 각 노드가 임의의 다른 노드와 연결될 수 있습니다.
둘째로, 순환 구조의 허용 여부입니다. 트리는 순환 구조를 허용하지 않습니다. 각 노드 간의 연결이 사이클을 형성하지 않아야 합니다. 그러나 그래프는 순환을 가질 수 있습니다.
셋째로, 루트 노드와 부모-자식 관계의 유무입니다. 트리는 항상 하나의 루트 노드를 가지며, 각 노드는 부모와 자식 노드 간의 관계를 가집니다. 반면에 그래프는 루트 노드를 갖지 않을 수도 있으며, 부모-자식 관계가 없을 수도 있습니다.
넷째로, 방향성의 존재 여부입니다. 트리는 일방향적인 구조로서 각 간선이 한 방향으로만 이동합니다. 반면에 그래프는 간선에 방향이 없는 무방향 그래프와 간선에 방향이 있는 방향 그래프로 나뉩니다.
이러한 차이점을 고려하면, 트리는 주로 계층적인 데이터를 표현하고 구조화하는 데 사용되며, 그래프는 다양한 관계를 모델링하고 복잡한 네트워크를 표현하는 데 사용됩니다.

출처

선형/비선형
자료구조 - 그래프
트리, 이진 트리
힙 개념과 JAVA로 구현
MAP의 자료구조
자료구조(MAP)
자료구조 - set 개념 및 활용
맵 & 셋