자료구조: 데이터를 원하는 목적에 맞게 저장하기 위한 구조
알고리즘: 자료구조에 쌓인 데이터를 활용해 문제를 해결하기 위한 동작들의 모임
스택, 큐
abstract data type (ADT) 구현 방법은 명시하지 않고 자료에 대한 연산을 명기한 것
- 스택: first in last out 구조. 재귀함수에서 사용
- 큐: first in first out 구조
Array, Linked List
Array는 데이터들이 순서대로 늘여선 배열이며, 링크드 리스트는 자료의 주소값으로 서로 연결된 형식이다.
Array
- 원하는 데이터에 무작위로 접근할 수 있어서 검색이 빠르다. access 시간 복잡도 O(1)
- 크기가 제한되어 있으며, 크기를 재조정하는 것은 많은 연산이 필요하다.
- 추가와 삭제를 위해 임시 배열을 생성하고 복제하여 시간이 오래 걸린다.
Linked List
- 리스트의 크기에 영향 없이 데이터를 추가할 수 있다. 새로운 노드를 생성하여 연결하면 되므로 추가, 삭제 연산이 빠르다. 추가, 삭제 시간 복잡도 O(1)
- 무작위 접근이 불가능하고 순차 접근만 가능하다.
Single Linked List
단방향 연결 리스트. 다음 노드의 탐색만 가능
Double Linked List
양방향 연결 리스트
- 앞뒤 노드의 탐색이 가능. 상황에 따라 탐색의 방향이 바뀌어야 하는 경우는 이중 연결 리스트 사용
- 이전 노드 지정하기 위한 변수 추가 사용으로 메모리 더 사용
Skip List
밸런싱 과정 필요 없는 랜덤 자료 구조. 평균 시간 복잡도 O(logN), 최악은 O(N). next가 여러 개인 linked list라 할 수 있다.
Hash Table
key, value로 데이터를 저장하는 자료 구조. hash map이라고도 한다.
- key 값에 해시 함수를 적용해 고유한 index를 생성하고 검색시 index에 저장된 값에 접근한다.
- 고유한 index로 값을 조회하므로 검색, 추가, 삭제의 평균 시간 복잡도는 O(1)이다. 그러나 해시 index 값이 충돌(두 개 이상의 키가 동일한 슬롯에 hash됨)할 경우는 index 값에 연결된 데이터 배열을 조회해야 하기 때문에 시간 복잡도가 O(N)으로 증가할 수 있다.
해시 충돌 해결법
- 분리 연결법: 추가 메모리 사용. 동일한 버킷에 chaining되는 데이터 많아지면 캐시 효율성 감소
- 개방 주소법: 비어있는 해시 테이블 공간 활용하기 때문에 해시 테이블 재정리해주는 작업 필요
Trees
비선형 계층적 자료 구조. 그래프 자료구조의 일종 (ex. computer directory 구조)
- 노드 Node : 트리 구성 기본 요소. 데이터 값과 하위 노드에 대한 포인터 갖고 있음
- 간선 Edge: 노드 간의 연결선
- 루트 노드 Root Node: 부모가 없는 최상위 노드
- 부모 노드 Parent Node: 자식 노드를 가진 노드
- 자식 노드 Child Node: 부모 노드의 하위 노드
- 형제 노드 Sibling Node: 같은 부모를 가지는 노드
- 리프 노드 Leaf Node: 자식 노드가 없는 노드
- 가지 노드 Branch Node: 자식 노드 하나 이상 가진 노드
- 깊이 Depth: 루트에서 특정 노드까지의 간선 수. (D의 깊이는 2)
- 높이 Height: 특정 노드에서 리프 노드까지 가장 긴 경로의 간선 수 (A노드의 높이는 3)
- Level: 루트에서 어떤 노드까지의 간선 수
- 경로 Path: 한 노드에서 다른 노드에 이르는 길 사이에 놓여 있는 노드들의 순서 (A & H 경로: ABDH). 경로의 길이는 경로에 속한 간선의 수
- Width: 레벨에 있는 노드 수 (Level 2의 width는 4)
- Breadth: 리프 노드의 수 (5)
- Distance: 두 노드 사이의 최단 경로에 있는 간선 수 (D와 J distance는 3)
- Order: 부모 노드가 가질 수 있는 최대 자식 수
속성
- 노드가 n개인 트리는 항상 n-1개의 간선을 갖는다.
- 트리 내에 또 다른 트리가 있는 재귀적 자료 구조이다.
- 모든 자식 노드는 하나의 부모 노드만 갖는다.
- 하나의 루트 노드만 갖는다.
- 임의의 노드에서 다른 노드로 가는 경로는 유일하다.
- 회로가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다
- 간선을 하나 자르면 트리가 두 개로 분리된다
트리 종류
- 편향 트리 skew tree: 모든 노드들이 자식을 하나만 가진 트리
- 이진 트리 binary tree: 각 노드의 자식 노드 수가 2이하인 트리
- 이진 탐색 트리 binary search tree: 순서화된(정렬된) 이진 트리
- 다원 탐색 트리 m-way search tree: 최대 m개의 서브 트리를 갖는 탐색 트리. 이진 탐색 트리의 확장 형태로 height 줄이기 위해 사용함
- 균형 트리 B-Tree: height balanced m-way tree
트리 순회 Tree Traversal
트리의 모든 노드를 방문하는 과정
전위 순회 Preorder Traversal
깊이 우선(Depth first) 순회. 트리를 복사할 때 주로 사용된다. (부모 노드부터 생성)
루트 노드 방문 -> 왼쪽 서브트리 전위 순회 -> 오른쪽 서브 트리 전위 순회
중위 순회 Inorder Traveral
왼쪽 오른쪽 대칭 순서로 순회. 이진 탐색 트리에서 오름차순, 내림차순으로 값 가져올 때 사용
왼쪽 서브 트리 중위 순회 -> 루트 노드 방문 -> 오른쪽 서브 트리 중위 순회
후위 순회 Postorder Traversal
트리 삭제에 주로 사용. (자식 노드 먼저 삭제하고 부모 노드 삭제)
왼쪽 서브 트리 후위 순회 -> 오른쪽 서브 트리 후위 순회 -> 루트 노드 방문
이진 트리 Binary Tree
각 노드의 자식 노드 수가 2 이하인 트리
유형
- 전 이진 트리 full binary tree
모든 노드가 0 또는 2개의 자식 노드를 갖는 트리
- 완전 이진 트리 complete binary tree
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함
- 포화 이진 트리 perfect binary tree
모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이, 레벨을 갖는다
- 균형 이진 트리 balanced binary tree
왼쪽과 오른쪽 높이 차이가 모두 1만큼 나는 트리 (AVL, 레드 블랙 트리)
표현
이진 트리는 배열 또는 연결 리스트로 표현이 가능
- 배열: 루트 노드 인덱스 i가 1이라면 노드 i 왼쪽 자식은 2i번째 노드, 오른쪽 자식은 2i + 1번째 노드로 표현할 수 있다. 노드 i의 부모는 i/2번째 노드이다.
이진 탐색 트리 Binary Search Tree
- 정렬된, 순서화된 이진 트리
- 노드의 왼쪽 하위 트리에는 노드 키보다 작은 키가 있는 노드만, 오른쪽 하위 트리에는 노드 키보다 큰 키가 있는 노드만 포함된다.
- 모든 하위 트리도 각각 이진 검색 트리여야 한다.
- 중복 키를 허용하지 않는다.
- 균형 상태일 경우 검색 시간 복잡도 O(logN), 불균형 상태라면 최대 O(N)
이진 트리 검색
루트에서 시작 -> 검색 값을 루트와 비교 -> 루트보다 작으면 왼쪽에 대해 재귀, 크다면 오른쪽에 대해 재귀. 검색값 없으면 null 반환
이진 트리 삽입
새 키는 항상 리프 노드에 삽입된다. 삽입 값을 루트와 비교하여 루트보다 작으면 왼쪽으로, 크다면 오른쪽으로 재귀. 리프 노드에 도달 후 노드보다 크다면 오른쪽, 작다면 왼쪽에 삽입
이진 트리 삭제
- 삭제할 노드가 리프 노드일 경우: 삭제만 하면 완료
- 삭제할 노드에 자식이 하나만 있는 경우: 노드를 삭제하고 자식 노드를 삭제된 노드의 부모에 직접 연결
- 삭제할 노드에 자식이 둘 있는 경우: successor노드 (right subtree의 최소값)를 찾아서 삭제할 노드와 값을 바꾸고 successor 노드를 삭제한다
AVL tree
스스로 균형을 잡는 이진 탐색 트리. 트리의 높이가 h일 때 시간 복잡도는 O(h)인데, 한쪽으로 치우친 편향 이진 트리가 되면 트리의 높이가 높아져 시간 복잡도도 높아지므로 높이 균형을 유지하는 AVL트리를 사용함
- 이진 탐색 트리의 속성을 가짐
- 왼쪽, 오른쪽 서브 트리 높이 차이가 최대 1
- 높이 차이가 1보다 커질 때 회전을 통해 균형을 잡는다
- 높이가 logN으로 유지되기 때문에 삽입, 검색, 삭제 시간 복잡도가 O(logN)
- balance factor: 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
Red Black tree
이진 탐색 트리의 일종. AVL트리와 마찬가지로 이진 탐색 트리를 기본으로 한다. 삽입, 삭제, 검색의 시간 복잡도는 O(logN)이다. 다음의 속성을 만족한다.
- 모든 노드는 빨간색, 검은색 둘 중 하나
- 루트 노드는 검은색이다.
- 모든 리프 노드는 검은색이다.
- 어떤 노드가 빨간색이라면 두 개 자식 노드는 모두 검은색이다. (빨간색 노드가 같은 경로 상에 연이어 등장하지 않는다)
- 각 노드에서 자손 잎새 노드 사이의 모든 경로에 대해 검은색 노드 수가 같다.
Heap
최대값, 최소값 연산을 빠르게 하기 위해 고안된 자료 구조
- 완전 이진 트리 complete binary tree이다.
- 부모 노드의 키 값고 자식 노드의 키값 사이에 대소 관계가 성립한다.
- 일반적으로 배열 인덱스 1부터 사용하는 배열로 표현한다.
- 우선순위 큐, 다익스트라 알고리즘, 힙 정렬에 사용
최대 힙
부모 키값이 자식 키값보다 큰 힙. 가장 큰 값이 루트 노드에 있다.
최소 힙
부모 키값이 자식 키값보다 작은 힙. 가장 작은 값이 루트 노드에 있다.
연산
- heapify: 이진 트리에서 힙 속성 유지하는 작업. (max heap 기준) 루트 기준 자식 트리로 내려가면서 현재 요소와 자식 노드들 비교하여 자식 노드가 크면 부모 노드와 값을 바꿔준다.
- extract: (max 기준) 최대 요소 추출. 먼저 루트 노드 값을 추출하고, 마지막 요소를 루트 노드에 배치한 후 heapify 수행
- increase value: 특정 노드 값 증가시킨 후 부모 노드와 비교하여 heap 속성 위배되면 부모와 자식 값을 바꿔준다. heapify는 따로 필요 없음. (max heap에서는 노드 값 증가시켰을 때 항상 자식 노드보다 크므로)
- insert: 힙의 끝에 최소값을 삽입. 추가할 값을 increase value 연산으로 삽입
- delete: increase value로 삭제할 요소를 max값으로 증가시키고 루트 노드에 위치시킨 후 extract 수행
Splay Tree
self balancing 수행하는 이진 탐색 트리 중 하나. splay라는 rotate 연산 과정을 통해 접근한 특정 노드를 root로 끌어올리고 self balancing한다. 시간 복잡도 O(logN)
K-D Tree
특수 이진 트리. 공간 내 점들 구성하기 위한 공간 분할 자료 구조. 평균 시간 복잡도 O(logN)
B-tree
모든 리프 노드들이 같은 레벨을 가질 수 있도록 밸런스를 맞추는 트리. 다원 탐색 트리는 노드에 저장할 수 있는 요소의 수를 늘려서 트리의 높이를 줄일 수 있다. 그러나 불균형이 발생하면 검색 성능이 떨어지게 되므로 이를 보완한 b-tree를 사용한다
Trie
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태 자료 구조 (ex 사전 찾기, 검색어 자동 완성, 문자열 검사 등에 쓰임)
- 저장된 단어는 끝을 표시하는 변수 통해서 단어의 끝 구분할 수 있다.
- 제일 긴 문자열의 길이를 L, 총 문자열 수를 M이라 할 때 검색 시간 복잡도는 O(L). 생성시 시간 복잡도는 O(M*L)
Reference
https://www.bigocheatsheet.com/
생활 코딩
https://yoongrammer.tistory.com/68?category=956616
https://yoongrammer.tistory.com/71
https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/