자료구조(data structure)

<aside> 💡 자료구조란 데이터를 구성하고 저장하는 방법을 설명하며, 데이터를 식별하는 방법을 제공하고 데이터의 관계를 보여주는 개념이다.

</aside>

Untitled

자료구조 기본 개념

배열(Array)
- 순차적 또는 연속적
- 요소를 임의의 순서로 읽을 수 있다
- 데이터 추가 및 삭제 시 다른 데이터들의 순서를 다시 매겨야 하므로 시간이 걸린다.
- 특히 기존에 선언한 배열 크기 이상의 데이터를 추가하려 하면 그만한 크기의 데이터를 메모리상에 만들고 기존 배열을 복사한 후 추가 데이터를 입력하는 방식이라 비효율적이다.
리스트(List)
- 요소들이 흩어진 상태로 메모리에 저장된다.
- 데이터와 포인터(=참조)의 쌍으로 구성된다. 이 쌍을 노드라고 부른다.
- 진입 지점이 있도록 구성되는데, 이 진입점을 헤드라고 한다.
- 단방향, 양방향, 순환 구조가 있다.
큐(Queue)
- FIFO방식
- 우선순위 큐(Priority Queue)
  - 우선순위가 높은 순서대로 추출
  - 같은 우선순위일 경우 먼저 추가된 요소
스택(Stack)
- LIFO방식
트리(Tree)
- 최상단을 루트 노드라 한다.
- 최하단 노드를 리프 노드(말단 노드)라 한다.
- 한 노드를 부모 노드(상위 노드)로 한다면, 거기에 연결된 밑의 노드들은 자식 노드(하위 노드)라 한다.
- 노드끼리 연결하는 선을 엣지라고 한다.
- 이진 탐색 트리
  - 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다.
  - 최하단 최좌측노드는 최솟값, 최하단 최우측노드는 최댓값을 갖는다.
  - B 트리
    - 이진 탐색 트리와 달리 자식 노드를 3개 이상 갖고 있다.
- AVL(Adelsom-Velsky and Landis) 트리
  - 시간복잡도는 $O(logn)$ 이다.
  - 최악의 경우로 일자로 쭉 연결된 트리가 있는데, 이걸 이진 탐색트리처럼 재정렬한 트리를 AVL 이진 트리라고 한다.
  - 높이 차이를 감지하면 트리 회전 과정을 통해 균형을 조정하는 메커니즘을 가진 트리다.
  - RB(Red-Black) 이진 탐색 트리
    - AVL트리보다 균형 조정 과정에서 트리 회전수가 적어 효율적이다
    - 일반적으로 루트 노드는 검정을 갖고, 빨강 노드는 검정 노드를 자식으로 갖는 트리다.
트리

트리 구조란 모든 노드가 연결되어 있으면서 순환할 수 없는 다이어그램을 말한다.

왼쪽은 모든 노드가 연결되어 있지 않으며, 오른쪽은 순환이 가능하기 때문에 트리가 아니다.
- 정렬 순서
  
  https://m.blog.naver.com/rlakk11/60159303809
  - 코드로 파악해보면 좀 더 이해하기 쉽다.
```
fun preorder(n) {
	visit(n)
	preorder(n.left)
	preorder(n.left)
}

fun inorder(n) {
	inorder(n.left)
	visit(n)
	inorder(n.left)
}

fun postorder(n) {
	postorder(n.left)
	postorder(n.left)
	visit(n)
}
```
- 이진 탐색 트리의 삭제 방법
  - 만약 삭제 대상 노드의 왼쪽 트리가 비어있다면, 단순히 오른쪽 자식 서브트리를 올리면 된다.
  - 만약 삭제 대상 노드의 오른쪽 트리가 비어있다면, 단순히 왼쪽 자식 서브트리를 올리면 된다.
  - 만약 삭제 대상 노드의 양쪽 트리가 전부 비어있지 않다면, 이어받을 트리는 현재 노드보다 큰 수들 중 가장 작은 수를 가진 노드다.
    - 즉 삭제 대상 노드의 오른쪽 서브트리의 각 왼쪽 노드를 끝까지 타고 가면 된다.
    - 그러면 자연스럽게 가장 작은 노드는 오른쪽 트리가 있거나 없는 2가지 형태의 노드가 된다.
    - 대상 노드와 후계자 노드를 변경하고 비어있는 노드는 삭제 원칙에 따라 삭제를 진행한다.
    - 만약 대상 노드 오른쪽 노드의 왼쪽 노드가 없는 경우 ⇒ 오른쪽 노드의 오른쪽 노드가 있거나 없는 경우이므로,(이보다 더 큰 수만 있으므로)
      - 가장 작은 노드는 대상 노드의 바로 오른쪽 노드다.
    - 이러면 단순히 대상 노드를 삭제하고 오른쪽 서브트리를 올리기만 하면 된다.
  - 수도 코드
- 균형잡힌 이진 탐색 트리
  - 이진 탐색 트리의 삽입, 삭제, 검색의 이상적인 시간복잡도는 $O(logN)$ 이지만, 최악의 경우에는 $O(N)$ 이다.
  - 이진 탐색 트리는 레드-블랙 트리나 AVL 트리처럼 위 형태의 트리를 관리하는 기법이 있다.
  - 삭제나 삽입이 수행될 때 루트 노드와 그 주변 노드를 회전시키는 방식 등으로 루트 노드의 왼쪽, 오른쪽 서브트리가 지나치게 커지지 않도록 관리한다.
  - 이렇게 잘 분배된 이진 탐색 트리를 균형잡힌 이진 탐색 트리라고 한다.
- 완전 이진 트리(complete binary tree)
  - 잎 노드들을 제외한 트리 중 가장 오른쪽, 즉 가장 큰 값을 가진 노드를 제외한 모든 노드가 자식을 가지고 있으며, 그것이 왼쪽부터 순서대로 채워진 경우를 완전 이진 트리라고 한다.
  - 모든 노드가 전부 자식을 2개씩 가지고 있으면 완벽 이진 트리(perfect binary tree)라고 한다.
힙
- 트리 기반 데이터 구조이다.
- 우선순위 큐는 힙을 이용해 구현할 수 있다.
- 힙 데이터 구조는 힙 메모리와 전혀 다른 개념이다.
- 힙이란 완전 이진 트리에서, 루트 노드가 가장 큰 값 또는 가장 작은 값을 가지고 있는 경우를 말한다.
- 최초로 생성할 때는 $O(n)$, 추가나 삭제의 경우 $O(logN)$ , 탐색의 경우 $O(1)$ 의 시간복잡도를 갖는다.
  - 최대 힙, 최소 힙 모두 동일
- 하지만 힙은 삭제는 반드시 루트 노드만 가능하다는 점을 명심해야 한다.
- k번째로 큰 노드를 찾는 것도 불가능하며, 루트 노드(최댓값)을 뺀 나머지 요소는 알 수 없는 구조라고 생각하면 좋다.
- 따라서 무작위 값이 추가되면서, 최댓값, 최솟값의 탐색 및 삭제만 필요한 상황에서 유용한 구조이다.
- 힙의 삽입 로직
  - 삽입을 수행해야하는 특별한 위치는 없다.
  - 보통 배열의 제일 마지막에 삽입을 수행하는데(단순히 append 수행), 이러면 위치는 트리의 가장 마지막 노드가 된다.
  - 그리고 부모 노드와 값을 비교하며(n/2) 교환을 수행한다. 더 큰 부모 노드가 있거나 루트 노드가 될 때 까지 수행한다.
```
function insert(arr[], n, x)
  arr.append(x)                          // Add node x at the end.

  set i = n + 1                          // Start from the last node.
  while i > 1 and arr[i / 2] < arr[i]    // If the parent is smaller than the child,
                                         // it violates the max-heap condition.
    swap(arr[i], arr[i / 2])             // Swap the two values
    i = i / 2                            // Move up to the parent position.
```
- 힙의 삭제 로직
  - 힙은 루트 노드에서만 삭제가 수행된다.
  - 루트 노드가 삭제되면 배열의 가장 마지막 노드를(가장 오른쪽 아래) 루트 노드 위치로 변경한다.
  - heapify(1)을 1차례 수행하면 힙 구조가 다시 복구된다.
  - heapify의 시간복잡도는 $O(log N)$ 이므로 삭제 로직의 시간 복잡도 또한 $O(log N)$ 이다.
```
function remove(arr[], n)
  arr[1] = arr[n]                     // Move the last node to the first node.
  delete arr[n]                       // Delete the last node.
  heapify(arr, n - 1, 1)              // Perform heapify starting from the 1st node
                                      // to maintain the max-heap state.
```
해시(Hash)
그래프(Graph)

자바 자료구조의 모든것

API reference for Java Platform, Standard Edition

Java Development Kit Version 17 API Specification

개요

https://medium.com/@dakota.lillie/javas-collections-framework-an-overview-86de12f4f622