데이터 구조

혼자 공부하면서 노션에 적어둔 내용을 기록할겸 붙여넣기 했습니다 (정리 안 됨)

 

우선순위 큐와 힙의 개념

• Priority queue (우선순위 큐)
  • 큐와 유사하지만 우선 순위가 높은 아이템이 먼저 처리됨
  • insert
  • delete
  • peek
• heap
  • 힙은 주로 이진 트리 기반으로 구현
  • 힙은 max heap 과 min heap 이 있음
  • max heap
    • 부모 노드의 키가 자식노드들의 키보다 크거나 같은 트리
  • min heap
    • 부모 노드의 키가 자식노드들의 키보다 작거나 같은 트리
  • 힙 주요동작
    • inser
    • delete
    • peek
• 우선순위 큐와 힙의 관계
  • 힙의 키를 우선순위로 사용한다면 힙은 우선순위 큐 구현체가 된다
• 우선순위 큐와 힙의 사용 사례
  • 프로세스 스케줄링
  • 힙 정렬
• 힙 메모리와는 관련 없음

배열(array), 동적배열(dynamic array)과 연관배열(associative array)

• Array
  • 같은 타입의 데이터들을 저장하는 자료구조
  • 연속된 메모리 공간에 데이터들을 저장
  • 데이터들 각각은 이름이 없지만 인덱스로 접근가능
  • 연속된 메모리 공간에 데이터들을 저장하기 때문에 CPU 캐시를 통해 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축할 수 있다.
• 동적 배열 (dynamic array)
  • 크기가 변할 수 있는 Array
  • 데이터를 더하거나 빼는 것이 가능한 자료구조
  • resizable array, array list 등등으로 불림
• 연관 배열 (associative array)
  • key-value pair 들을 저장하는 ADT
  • 같은 키를 가지는 페어는 최대 한개만 존재
  • map, dictionaray 라고 불리기도 함

리스트(list), array list 와 linked list 의 개념과 차이

• 리스트
  • 값들을 저장하는 추상자료형 (ADT)
  • 순서가 있음
  • 중복을 허용
• 리스트 구현체
  • Array list
  • Linked list
• Array List
  • 배열을 사용하여 리스트를 구현
• Linked list
  • 노드를 연결 시키는 형태로 구현
  • 확장팩(?)
    • circular linked list - 순환 ( 꼬리와 헤드가 연결)
    • doubly linked list - 양방향 : 더 빨리 접근 할 수 잇다
    • circular doubly linke list - 순환 양방향

맵(Map) 과 해시테이블 (hash table)

• Map
  • key-value pair 들을 저장하는 ADT
  • 같은 키를 가지는 페어는 최대 한개만 존재
  • associative array, dictionary 라고 불리기도 함
• Map 구현체 → Hash table
• Hash table (hash map)
  • 배열과 해시함수를 사용하여 map 을 구현한 자료구조
  • (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠름
• hash function
  • 임의의 크기를 가지는 타입의 데이터를 고정된 크기를 가지는 타입의 데이터로 변환하는 함수
  • 해시 테이블에서 임의의 데이터를 정수로 변환하는 함수
• hash collision (해시 충돌)
  • 키는 다른데 해시가 같을 때
  • 키도 해시도 다른데 hash % map_capa 결과가 같을 때
• hash collision 해결 방법
  • open addressing
    • linear probing
      • 비어있는 공간 활용
  • separate chaining
    • 버킷을 linked list로 관리
• hash table resizing
  • 데이터가 많이 차게 되면 테이블의 크기를 늘려주어야한다

Set , Hash Set, List vs Set

• Set
  • 데이터를 저장하는 추상 자료형 (ADT)
  • 순서를 보장하지 않음
  • 데이터 중복을 허용하지 않음
  • 데이터 조회가 리스트보다 빠름
• 언제 쓰면 좋을까?
  • 중복된 데이터를 제거해야 할 때
  • 데이터의 존재 여부를 확인해야 할 때
• set 구현체
  • hash set
  • linked hash set
  • tree set
• Hash set
  • 해시 테이블을 사용하여 구현
  • Hash table
    • 일반적으로 테이블의 크기에 상관없이 키를 통해 상수 시간에 빠르게 데이터에 접근 가능
  • 해시테이블을 사용하여 구현하기 때문에 크기 상관없이 데이터 조회가 빠름
• 리스트와 셋 중 무엇을 쓸까?
  • Set 을 사용하는게 더 적절한 상황이 아니라면, 거의 대부분 리스트를 사용한다고 봐도 무리 없음
• 리스트가 메모리 적게 씀 구현 특성상 리스트가 단순하고 iteration이 더 빠름

트리(tree) 구조의 기본 개념과 용어, 이진트리의 형태에 따른 다양한 종류

• 트리
  • 노드들의 집합
  • 각 노드는 값과 다른 노드들을 가리키는 레퍼런스로 구성
• 트리 관련 주요 용어
  • 간선 (edge)
    • 노드와 노드를 연결하는 선
    • 구현 관점에서는 레퍼런스를 의미
    • a.k.a link, branch
  • 루트 노드
    • 트리의 최상단에 있는 노드
    • 트리의 시작점
  • 자녀 노드
    • 모든 노드는 0 개 이상의 자녀 노드를 가진다
  • 부모 노드
    • 자녀 노드를 가지는 노드
  • 형제 노드
    • 같은 부모를 가지는 노드
  • 조상 노드
    • 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드
  • 자손 노드
    • 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드
  • 내부 노드
    • 자녀 노드를 가지는 노드
  • 외부 노드
    • 자녀 노드가 없는 노드
    • a.k.a leaf node, 단말 노드
• 경로 (path)
  • 한 노드에서 다른 노드 사이의 노드들의 시퀀스
• 경로 길이
  • 경로에 있는 노드들의 수
• 노드의 높이
  • 노드에서 리프 노드까지의 가장 긴 경로 간선 수
• 트리의 높이
  • 루트 노드의 높이
• 노드의 깊이 (depth)
  • 루트 노드에서 해당 노드까지 경로 간선 수
• 트리의 깊이
  • 트리의 있는 노드들의 깊이 중 가장 긴 깊이
  • 트리 높이 == 트리 깊이
• 노드의 차수 (degree of node)
  • 노드의 자녀 노드 수
• 트리의 차수 (degree of tree
  • 트리에 있는 노드들의 차수 중 가장 큰 차수
• 두 노드 사이의 거리
  • 두 노드의 최단 경로의 간선 수
• 노드의 레벨
  • 노드와 루트 노드 사이의 경로에서 간선의 수
• width
  • 임의의 레벨에서 노드의 수
• 노드의 크기
  • 자신을 포함한 자손 노드의 수
• 트리의 크기
  • 트리의 모든 노드의 수
• 서브 트리
  • 각 노드의 자녀 노드들을 재귀적으로 서브 트리를 구성한다
• 트리 구조의 주요 특징
  • 루트 노드는 하나만 존재
  • 사이클이 존재하지 않음
  • 자녀 노드는 하나의 부모 노드만 존재
  • 데이터를 순차적으로 저장하지 않는 비선형 구조
  • 트리에 서브 트리가 있는 재귀적 구조
  • 계층적 구조
• 이진 트리
  • 각 노드의 자녀 노드 수가 최대 두 개인 트리
• 형태에 따른 이진 트리의 종류
  • full binary tree (정 이진 트리)
    • 모든 노드는 자녀 노드가 없거나 두 개인 트리
  • Complete binaray tree (완전 이진 트리)
    • 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 잇음
    • 마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워져 있는 트리
  • perfect binary tree (포화 이진 트리)
    • 모든 레벨에서 노드가 빠짐 없이 채워져 있는 트리
  • degenerated binary tree (변질 이진 트리)
    • 모든 부모 노드는 하나의 자녀 노드만 가지는 트리
    • == pathological binary tree
    • left skewed binary tree
      • 모든 부모 노드는 왼쪽 자녀 노드만 가지는 트리
    • right skewed binary tree
      • 모든 부모 노드는 오른쪽 자녀 노드만 가지는 트리
  • balanced binary tree (균형 이진 트리)
    • 모든 노드에서 왼쪽 서브트리와 오른 쪽 서브트리의 높이 차이가 최대 1인 트리

이진탐색 트리 (binary search tree)

• 이진 탐색 트리
  • 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고
  • 모든 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값들만 가짐
• 최소값
  • 트리의 가장 왼쪽
• 최대값
  • 트리의 가장 오른쪽
• 중위 순회 (inorder traversal)
  • 재귀적으로 왼쪽 서브 트리 순회
  • 현재 노드 방문
  • 재귀적으로 오른쪽 서브 트리 순회
• 전위 순회 (preorder traversal)
  • 현재 노드 방문
  • 재귀적으로 왼쪽 서브 트리 순회
  • 재귀적으로 오른쪽 서브 트리 순회
• 후위 순회 ( postorder traversal)
  • 재귀적으로 왼쪽 서브 트리 순회
  • 재귀적으로 오른쪽 서브 트리 순회
  • 현재 노드 방문
• 노드의 successor (후임자)
  • 해당 노드보다 값이 큰 노드들ㅇ 중에서 가장 값이 작은 노드
• 삽입
• 삭제
  • 삭제하려는 노드가 있는지 검색, 있으면 삭제
  • 자녀가 없는 노드 삭제
    • 삭제 될 노드를 가리키던 레퍼런스를 가리키는 것이 없도록 처리
  • 자녀가 하나인 노드 삭제
    • 삭제될 노드를 가리키던 레퍼런스를 삭제될 노드의 자녀를 가리키게 변경
  • 자녀가 두개인 노드 삭제
    • 삭제될 노드의 오른쪽 서브 트리에서 제일 값이 작은 노드가 삭제될 노드를 대체한다
• 시간 복잡도best avg wort

  insert	Θ(1)	O(logN)	Θ(N)
  delete	Θ(1)	O(logN)	Θ(N)
  search	Θ(1)	O(logN)	Θ(N)

• 장점
  • 삽입 삭제가 유연하다
  • 값의 크기에 따라 좌우 서브트리가 나눠지기 때문에 삽입/삭제/검색이 (보통은) 빠르다
  • 값의 순서대로 순회 가능하다
• 단점
  • 트리가 구조적으로 한쪽으로 편향되면 삽입 삭제 검색 등등 여러 동작들의 수행 시간이 악화된다
  ⇒ 해결하기 위해 스스로 균형을 잡는 이진 탐색 트리가 사용 → AVL 트리 Red-Black 트리