1. Array vs Linked List
Array
Array 자료구조는 인덱스(index)로 해당 원소(element)에 접근할 수 있습니다. 찾고자 하는 element의 index 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있습니다.(논리적 저장 순서와 물리적 저장 순서가 일치)
하지만, 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 소요됩니다.
만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨집니다. 즉 빈 공간이 생기는 것입니다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 앞쪽으로 이동, shift 해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 됩니다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 최악 시간복잡도 O(n)이 됩니다.
삽입의 경우도 마찬가지입니다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 늘려줘야 하므로, 이 경우도 O(n)의 시간복잡도를 갖게 됩니다.
Linked List
Array의 삽입, 삭제에 대한 문제점을 해결하기 위한 자료구조가 linked list 입니다.
Linked List는 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있습니다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결할 수 있는 것입니다.
하지만 Linked List 역시 문제점이 있습니다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 탐색하는 과정에서 순차적으로 확인해봐야 한다는 것입니다. (Array 와 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문입니다.)
이것은 일단 삽입하고 정렬하는 것과 마찬가지입니다. 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 됩니다.
정리하자면 linked list 자료구조는 탐색할 때 O(n)의 시간복잡도를 갖고, 삽입, 삭제에 대해서도 O(n)의 시간복잡도를 갖습니다.
이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다고 합니다.
2. Stack vs Queue
Stack과 Queue의 공통점은 선형 자료구조입니다.
Stack
Last In First Out (LIFO) 먼저 들어간 원소가 나중에 나온다는 것이 Stack 자료 구조의 특징입니다. stack를 활용해 짝이 있는 것에 대한 유효성을 확인할 수 있을 것입니다. ex. ()
Queue
Fist In First Out (FIFO) 먼저 들어간 원소가 먼저 나오는 것이 Queue 자료 구조의 특징입니다.
3. Tree
Tree는 비선형 자료구조입니다. 계층적인 관계를 표현할 수 있습니다.
Tree를 구성하는 요소는 Node, Edge, Root Node, Terminal Node, Internal Node가 있습니다.
- Node(노드) : 트리를 구성하는 각각의 엘레멘트
- Edge(간선) : 노드와 노드를 연결하는 선
- Root Node(루트 노드) : 트리 구조 최상위에 있는 노드
- Terminal Node OR leaf Node(단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 단 하나의 노드
- Internal Node : 단말 노드를 제외한 모든 노드이다 (루트 노드도 포함)
Binary Tree (이진 트리)
루트 노드를 중심으로 두 개의 서브 트리로 나누어집니다. 나뉘어진 두 서브 트리도 모두 이진 트리여야합니다. 공집합도 이진 트리로 포함시켜야 합니다.
트리에서는 각 층별로 숫자를 붙이는데 이를 level(레벨)이라고 합니다. 레벨의 값은 0부터 시작하며 루트 노드의 레벨은 0이 되겠습니다. 트리의 최고 레벨은 height(높이) 라고 합니다
- 포화 이진 트리 : 모든 레벨이 꽉 찬 이진 트리
- 완전 이진 트리 : 위에서 아래로, 왼쪽에서 오른쪽으로 채워진 이진 트리
- 정 이진 트리 : 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리
이진 트리는 노드의 개수가 n개이고, root가 0이 아닌 1에서 시작할 때, i번째 노드에 대하여 parent(i) = i/2, left_child(i) = 2i, right_child(i) = 2i+1 index를 갖습니다
Binary Search Tree
효율적인 탐색을 위해서는, 효율적인 저장방법을 고민해야합니다. 이진 탐색 트리 또한 이진 트리 중 하나입니다. 이진 탐색 트리는 데이터 저장하는 규칙이 있고, 이 규칙으로 특정 데이터의 위치를 찾을 수 있습니다.
- 이진 탐색 트리 노드에 저장된 키는 유일하다.
- 부모의 키가 왼쪽 자식 노드보다 크다.
- 부모의 키가 오른쪽 자식 노드보다 작다.
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
탐색 연산은 O(log n)의 시간복잡도를 갖습니다. 트리의 높이를 하나씩 더해갈 수록, 추가 가능한 노드의 수가 2배씩 증가하기 때문에 O(h) 라고 표현하는 사람들도 있습니다.
위 같은 규칙을 가지고 있는 이진 탐색 트리는 편향 트리가 될 수도 있습니다. 한쪽에만 노드가 추가되는 경우가 있기 때문입니다. 이럴땐 최악의 시간 복잡도 O(n)을 갖습니다.
4. Binary Heap
Tree 형식을 가지고 있으며, 완전 이진 트리입니다. 배열에 트리 값들을 넣어줄 때, 1번째 index부터 루트노드가 시작됩니다. 이는 노드의 고유 번호 값과 배열의 index 혼동을 줄이기 위한 규칙입니다.
힙에서는 max heap(최대힙)과 min heap(최소힙)의 개념이 있습니다.
Max Heap이란, 각 노드의 값이 해당 children 의 값보다 크거나 같은 완전 이진 트리를 말합니다. (Min Heap 은 그 반대입니다.)
Max Heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간복잡도는 O(1)입니다. 그리고 완전 이진 트리이기 때문에 배열을 사용하여 효율적으로 관리할 수 있습니다. (반대로, Min heap 에서는 최소값을 찾는데 소요되는 연산의 시간복잡도는 O(1)입니다.)
하지만 heap 의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요합니다. 여기서 heap 은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지합니다. 이런 경우에는 결국 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 됩니다.