TIL17 | 자료 구조

hyseoseo·2021년 9월 18일
0

CS

목록 보기
1/4

자료구조: 데이터를 원하는 목적에 맞게 저장하기 위한 구조
알고리즘: 자료구조에 쌓인 데이터를 활용해 문제를 해결하기 위한 동작들의 모임

스택, 큐

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 반환

이진 트리 삽입

새 키는 항상 리프 노드에 삽입된다. 삽입 값을 루트와 비교하여 루트보다 작으면 왼쪽으로, 크다면 오른쪽으로 재귀. 리프 노드에 도달 후 노드보다 크다면 오른쪽, 작다면 왼쪽에 삽입

이진 트리 삭제

  1. 삭제할 노드가 리프 노드일 경우: 삭제만 하면 완료
  2. 삭제할 노드에 자식이 하나만 있는 경우: 노드를 삭제하고 자식 노드를 삭제된 노드의 부모에 직접 연결
  3. 삭제할 노드에 자식이 둘 있는 경우: 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/

0개의 댓글