비선형 자료구조
선형 구조와 달리, 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태
- 자료들 간의 앞뒤 관계가 1:n 또는 n:n의 관계를 이루는 자료구조
- 계층적 구조를 나타내기에 적절하다
그래프 (Graph)
정점(Vertex), 간선(Edge)의 집합으로 이루어진 자료 구조
- 추상적인 개념의 연결 관계를 표현하기 위해 사용된다
- 네트워크 모델
- 2개 이상의 경로가 가능
- 부모 - 자식 관계의 개념이 없다
그래프의 종류
무방향 그래프: (간선의) 방향이 없는 그래프
방향 그래프: 방향성이 있는 그래프
가중치 그래프: 간선의 가중치값이 존재하는 그래프
루트없는 트리: 간선을 통해 노드 간 잇는 방법이 한가지인 그래프 = 트리
이분 그래프 : 그래프의 노드를 겹치지 않게 두 그룹으로 나눈 후 다른 그룹끼리만 간선이 존재하게 분할할 수 있는 그래프
사이클이 없는 방향 그래프 : 노드에서 출발해 자기 자신으로 돌아오는 경로(사이클)가 없는 그래프
그래프의 간선 수
- 방향 그래프의 최대 간선 수 : n(n-1)
- 무방향 그래프의 최대 간선 수 : n(n-1)/2
트리 (Tree)
정점(node), 선분(branch)를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
- 방향성이 있다
- 각 노드는 어떤 자료형으로도 표현이 가능하다
- 하나의 연결 그래프로, 사이클이 존재할 수 없다
트리의 종류
이진 트리 : 트리의 하위 노드가 최대 2개인 경우
트리 관련 용어
- 숲 : 여러 개의 트리가 모여 있는 것
- 트리의 디그리 : 노드들의 디그리 중 가장 많은 수
트리 운행법
이때 서브 트리를 하나의 노드로 생각하도록 묶어서 생각하면 편리하다.
Preorder (전위 수행)
Root >왼쪽 > 오른쪽 순으로 운행
Inorder (중위 수행)
왼쪽 > Root > 오른쪽 순으로 운행
PostOrder (후위 수행)
왼쪽 > 오른쪽 > Root 순으로 운행
그래프, 트리의 차이
힙 (Heap)
- 완전 이진 트리의 일종, 우선순위 큐를 위하여 만들어진 자료구조
- 여러 개의 값 중에서 최댓값 / 최솟값을 빠르게 찾아내도록 만들어짐
반정렬 상태 (느슨한 정렬 상태)를 유지
- 큰 값이 상위 레벨, 작은 값이 하위 레벨
- 즉, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작음- 중복된 값을 허용
힙의 종류
- 최대 힙 (max heap) : 부모 노드의 키 값 >= 자식 노드의 키 값
- 최소 힙 (min heap) : 부모 노드의 키 값 <= 자식 노드의 키 값
맵 (Map)
- key와 value로 이루어진 자료 구조
- key를 통해 value에 접근할 수 있다.
- key는 중복될 수 없다
- key - value의 매칭을
mapping이라고 한다.
종류
HashMap
키와 값이 구성되는 위치를 결정하거나 알 수 없다
키와 값으로 null이 허용된다
TreeMap :
key의 값을 기준으로 데이터가 순서대로 정렬되어 저장한다
저장 시간이 오래 걸린다
LinkedHashMap :
데이터를 입력한 순서대로 쌓이며 데이터를 저장한다
인덱스를 이용한 접근에 용이하다
셋 (Set)
-
순서가 없는 데이터의 집합 (삽입 순서대로 저장되지 않는다)
-
중복을 허용하지 않는다
순서가 필요 없고, 고유 값을 원할 경우 최선의 자료 구조
-
수정 가능
-
Fast Lookup에 용이
종류
HashSet
null 값을 허용한다
내부적으로 HashMap을 사용하여 값을 저장한다
해시 테이블 (HashTable)
- ket - value로 데이터를 저장하는 자료 구조
- 내부적으로 배열을 사용하여 데이터를 저장하기 때문에, 데이터 검색 속도가 빠르다
- 각각의 key 값에 해시 함수를 적용해 배열에 고유한 index를 생성한다
해시맵과의 차이
해시 테이블은 동기화 synchronized를 지원하고, 해시맵은 지원하지 않는다는 차이가 있다
참고 : 그래프, 트리 간결한 정리 Miro, 그래프, 트리 차이 pat coding, 그래프 상세 : 괭이쟁이, 트리 상세 : 괭이쟁이, 힙 상세 : Heee's Development Blog, 맵 상세 : G91 개발일지, 셋 상세 1 : 헬창코딩, 셋 상세 2 : inyong_pang.log, 해시테이블 상세 : 망나니개발자
