[Careerthon] 비선형자료구조

개요

• 비선형자료구조란?
• 트리와 힙
• 그래프
• 맵
• 셋
• 해시테이블

---

비선형자료구조

하나의 자료뒤에 여러개의 자료가 존재할 수 있는 형태 (앞, 뒤 관계가 1:N , N:N 관계)

트리와 그래프가 대표적 예시이며 계층구조를 나타내기에 적합함

노드: 연결구조 또는 계층구조에서 데이터의 기본단위를 뜻하는 단어

LinkedList도 노드와 링크로 이루어져있 듯이 비선형자료구조에만 쓰이는 것이 아님

트리(Tree)

이진트리 : 자식노드가 2개 이상인 트리 (힙, 이진검색트리)

 

힙(Heap)

트리가 채워질 때 무조건 왼쪽노드부터 채워진다.(index순서가 왼쪽부터)

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안 된  완전이진트리(트리가 완전히 채워진 구조)

O(log n)만큼의 시간복잡도를 가진다

동작)

•  데이터삽입
  • 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다
  • 삽입한 노드(자식노드)의 크기가 root(부모노드)보다 클 경우 와 값을 비교해서 위치를 바꾸며 이를 반복한다.

 

• 데이터 삭제
  • 최소값과 최댓값을 알아내는 자료구조이기에 삭제된다면 Root에 위치한 부모노드의 값이 삭제된다.
  • 부모노드가 비었다면 가장 최하단부 노드를 루트로 옮기고 자신보다 큰 자식노드가 있는지 값을 비교한다.
  • 왼쪽과 오른쪽 노드 모두 클 경우에는 비교 후 큰 값과 swap한다.

---

그래프(Graph)

연결되어있는 원소간의 관계를 표현한 자료구조로써 노드와 그노드를 연결하는 간선을 하나로 모아놓은 자료구조

부모자식개념 및 루트노드의 개념이 없는 네트워크 모델

지도나 지하철노선의 최단경로 등에 사용 됨

---

맵(Map)

특정 순서에 따라 키(key)와 값(value)의 조합으로 형성된 자료구조 해시테이블을 구현할 때 사용 됨키(key)를 사용해서 데이터 검색, 추가, 삭제, 수정이 가능하며 키는 고유해야한다.데이터의 효율적인 저장과 검색을 위해 해시함수를 사용한다.

일반적으로 Map이라 사용되는 자료구조는 해시 맵 또는 해시 테이블로써 해시함수를 통해서 배열의 인덱스로 값을 저장하거나 검색할 수 있다

삽입, 삭제, 검색의 평균 시간복잡도가 O(n)에 가깝다

---

셋(Set)

중복요소가 없이 유일한 값을 저장하는 자료구조

순서를 보장하지 않아 추가된 순서대로 나열되지 않는다

원시데이터와 객체를 모두 저장할 수 있는 자료구조이며 추가된 데이터는 내부적으로 객체로 저장된다

---

해시 테이블(Hash table)

키와 값으로 데이터를 저장하는 자료구조 빠르게 데이터를 검색할 수 있다 (평균 O(1)의 시간복잡도)해시함수를 통해서 변환한 값을 배열의 index로 저장하고 값을 저장한다. (우리가 흔히 사용하는 Map)