[Careerthon] 비선형자료구조
개요
- 비선형자료구조란?
- 트리와 힙
- 그래프
- 맵
- 셋
- 해시테이블
비선형자료구조
하나의 자료뒤에 여러개의 자료가 존재할 수 있는 형태 (앞, 뒤 관계가 1:N , N:N 관계)
트리와 그래프가 대표적 예시이며 계층구조를 나타내기에 적합함
노드: 연결구조 또는 계층구조에서 데이터의 기본단위를 뜻하는 단어
LinkedList도 노드와 링크로 이루어져있 듯이 비선형자료구조에만 쓰이는 것이 아님
트리(Tree)
힙(Heap)
트리가 채워질 때 무조건 왼쪽노드부터 채워진다.(index순서가 왼쪽부터)
데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안 된 완전이진트리(트리가 완전히 채워진 구조)
O(log n)만큼의 시간복잡도를 가진다
동작)
- 데이터삽입
- 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다
- 삽입한 노드(자식노드)의 크기가 root(부모노드)보다 클 경우 와 값을 비교해서 위치를 바꾸며 이를 반복한다.
- 데이터 삭제
- 최소값과 최댓값을 알아내는 자료구조이기에 삭제된다면 Root에 위치한 부모노드의 값이 삭제된다.
- 부모노드가 비었다면 가장 최하단부 노드를 루트로 옮기고 자신보다 큰 자식노드가 있는지 값을 비교한다.
- 왼쪽과 오른쪽 노드 모두 클 경우에는 비교 후 큰 값과 swap한다.
그래프(Graph)
연결되어있는 원소간의 관계를 표현한 자료구조로써 노드와 그노드를 연결하는 간선을 하나로 모아놓은 자료구조
부모자식개념 및 루트노드의 개념이 없는 네트워크 모델
지도나 지하철노선의 최단경로 등에 사용 됨
맵(Map)
특정 순서에 따라 키(key)와 값(value)의 조합으로 형성된 자료구조 해시테이블을 구현할 때 사용 됨키(key)를 사용해서 데이터 검색, 추가, 삭제, 수정이 가능하며 키는 고유해야한다.데이터의 효율적인 저장과 검색을 위해 해시함수를 사용한다.
일반적으로 Map이라 사용되는 자료구조는 해시 맵 또는 해시 테이블로써 해시함수를 통해서 배열의 인덱스로 값을 저장하거나 검색할 수 있다
삽입, 삭제, 검색의 평균 시간복잡도가 O(n)에 가깝다
셋(Set)
중복요소가 없이 유일한 값을 저장하는 자료구조
순서를 보장하지 않아 추가된 순서대로 나열되지 않는다
원시데이터와 객체를 모두 저장할 수 있는 자료구조이며 추가된 데이터는 내부적으로 객체로 저장된다
해시 테이블(Hash table)
키와 값으로 데이터를 저장하는 자료구조 빠르게 데이터를 검색할 수 있다 (평균 O(1)의 시간복잡도)해시함수를 통해서 변환한 값을 배열의 index로 저장하고 값을 저장한다. (우리가 흔히 사용하는 Map)