비선형 자료구조
데이터 항목 사이의 관계가 1:n인 경우
그래프
그래프는 정점과 간선으로 이루어진 자료구조입니다
- outdegree - 정점으로 나가는 간선
- indegree - 정점으로 들어오는 간선
가중치
가중치는 간선과 정점 사이에 드는 비용을 뜻합니다
트리
하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조이다
- 깊이 - 루트 노드 부터 특정 노드까지의 최단 거리
- 높이 - 루트 노드 부터 리프 노트까지 가장 긴 거리
- 레벨 - 깊이와 같은 의미
- 리프노드 - 자식 노드가 없는 노드
- 서브트리 - 트리 내의 하위 집합
이진 트리
이진 트리는 자식의 노드 수가 두개 이하인 트리를 의미합니다
- 정 이진 트리 (Full) - 자식 노드가 0 또는 2개인 이진 트리
- 완전 이진 트리 (Complete) - 왼쪽 부터 채워져있는 이진 트리
- 변질 이진 트리 (Degenerate) - 자식 노드가 1개 밖에 없는 이진 트리
- 포화 이진 트리 (Perfect) - 모든 노드과 꽉차 있는 이진 트리
- 균형 이진 트리 (Balanced) - 왼쪽과 오른쪽 노드의 높이차가 1이하인 이진 트리
이진 탐색 트리
AVL 트리 (Adelson-Velsky and Landis tree)
최악의 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 트리
두 자식 서브트리의 높이 차는 최대 1만틈 차이 난다는 특징이 있습니다
레드 블랙 트리
균형 이진 트리중에 하나로 탐색, 삽입, 삭제 모두가 O(log n)의 시간복잡도를 가집니다
C++ STL의 set, map, multiset, multimap 등에 쓰입니다
규칙
- 모든 리프노드와 루트노드는 블랙
- 레드 노드의 자식은 반드시 블랙
- 리프 노드에서 루트 노드까지 올라갈때 존재하는 블랙 노드의 수는 동일
힙
힙은 완전 이진 트리 기반 자료 구조이며, 최소 힙과 최대힙 두가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말합니다
- 최대힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야합니다
- 최소힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 합니다
우선순위 큐
우선순위 큐는 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조입니다
https://velog.io/@cada/자바스크립트로-우선순위-큐-구현하기
Map
Map은 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조입니다
레드 블랙 트리 자료 구조를 기반으로 형성되고 삽입하면 자동으로 정렬됩니다
Map은 해시태이블을 구현할때 쓰입니다
map<string, int>
- clear() - 모든 요소 삭제
- size() - map의 크기
- erase() - 키와 매핑된 값 삭제
Set
Set은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 희소한(Unique) 값만 저장하는 자료 구조입니다
자바스크립트의 Set 객체
var mySet = new Set();
mySet.add(1); // Set { 1 }
mySet.add(5); // Set { 1, 5 }
// 중복 되는 값은 추가로 저장되지 않는다
mySet.add(5); // Set { 1 }해시 테이블
해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 코드 값으로 매핑한 테이블 입니다
해시 코드는 배열의 인덱스와 같기 때문에, 해시 코드로 배열에 접근이 가능합니다
유튜브 동영상, 블록체인등에 쓰입니다
- 삽입 - O(1)
- 삭제 - O(1)
- 탐색 - O(1)
해시 충돌
하지만, 최악의 경우 모든 key 값 k가 하나의 slot으로 해싱되는 경우 길이가 n인 이중 연결리스트가 생성되어 O(n) 의 시간복잡도를 가진다
해시 충돌 해결 방법
체이닝
- 해당 인덱스 값이 있으면 체인으로 연결
- 버킷내에 연결리스틀 할당하여, 삽입시 해시 추옫ㄹ이 발생하면 연결리스트로 데이터들을 연결하는 방식
- 버킷이 꽉차게 되더라도 연결리스트를 늘려가는 방식이기에 주소 값 변경 안됨
- 중복되는 key가 있을 경우 해당 slot을 연결리스트로 저장
- 해시 테이블이 채워질수록, Lookup 성능저하가 선형적으로 발생
이 경우도 수행시간이 길어져, 최악의 경우 O(n)의 시간복잡도를 갖는다
개방 주소법
체이닝 처럼 포인터가 필요 없고, 지정한 메모리 외 추가적인 저장공간이 필요 없습니다
- 선형 탐색 : 해시 충돌시 다음 버킷 혹은 몇개 건너뛴 데이터 삽입
- 제곱 탐색 : 해시 충돌시 제곱 만큼 건너뛴 버킷에 데이터 삽입
- 이중 해시 : 해시 충돌시 다른 해시함수를 한번 더 적용
리사이징
- 테이블애 할당된 공간을 다 사용해서 더이상 사용할 공간이 없을 때
- 테이블 크기를 늘려준 다음 기존의 데이터를 해시함수로 보내 재정렬
