(data-structure) 자료구조 요약 정리

Array

가장 기본적인 자료구조인 배열은 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서, 인덱스(index)로 해당 원소에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 BIG-O(1)에 해당 원소로 접근할 수 있다. random access가 가능하다는 장점이 있다.

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근해 작업을 완료한 뒤, 작업을 추가적으로 해줘야 하기 때문에 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했을때 배열의 연속적인 특징이 깨지게 된다.(빈자리가 발생). 따라서 삭제한 원소보다는 큰 인덱스를 갖는 원소들을 shift해줘야 하는데, 이 경우 시간 복잡도가 O(n)이 된다. 그렇기 대문에 Array 자료구조에서 삭제 기능에 대한 시간 복잡도의 worst case는 O(n)이 된다.

Linked List

위 배열의 단점을 해결하기 위한 자료구조가 Linked List이다. 각각의 원소들은 자지 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있는 것이다.

하지만, 원하는 위치에 삽입을 하고자 하면 탐색 과정에 있어서 첫번째 원소부터 모두 확인해봐야 한다는 것이다. Array와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

결국 Linked List 자료구조는 탐색에 O(n)의 시간 복잡도를 갖고 삽입, 삭제에도 같은 시간 복잡도를 갖는다. 그렇다하더라도 연결 리스트는 tree구조의 근간이 되기 때문에 매우 중요한 개념이다.

Stack

선형 자료구조의 일종으로 Last In First Out(LIFO). 즉, 나중에 들어간 원소가 먼저 나온다. 이것은 stack의 가장 큰 특징이다. 차곡차곡 쌓이는 구조로 먼저 stack에 들어가게 된 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 자료들이 쌓이게 되고 호출 시 가장 위에 있는 자료(나 함수 등등)가 호출되는 구조이다.

Queue

선형 자료구조의 일종으로 First in First Out(FIFO)즉, 먼저 들어간 데이턱라 먼저 호출된다. stack과는 반대로 먼저 들어간 데이터가 맨 앞에서 대기하고 있다가 먼저 나오는 구조이다.

Tree

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다.

트리 구성요소(용어)

• Node(노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
• Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
• Root node(루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
• Terminal Node( = leaf Node, 단말노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
• Internal Node(내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

Binary Tree (이진트리)

루트 노드를 중심으로 두 개의 서브 트리 (큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진트리어야 한다. 한 가지 덧붙이자면 공집합도 이진 트리로 포함시켜야 한다. 그래야 재귀적으로 조건을 확인해갔을때, leaf node에 다다랐을때, 정의가 만족되기 떄문이다. 자연스럽게 노드가 하나뿐인 것도 이진 트리 정의에 만족하게 된다.

트리에서는 각 층별로 숫자를 매기는데 이를 레벨이라고 한다. 레벨의 값은 0부터 시작하고 따라서 루투 노드의 레벨은 0이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.

Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리), Full Binary Tree (정 이진 트리)

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진트리라고 한다. 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다. 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 한다.

Binary Tree는 노드의 개수가 n개이고 root가 0이 아닌 1에서 시작할 때, i번째 노드에 대해서 parent(i) = i/2, left_child(i) = 2i, right_child(i) = 2i + 1의 index 값을 갖는다. 

BST (Binary Search Tree)

효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장방법을 고민하게 된다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

1) 이진 탐색 트리의 노드에 저장된 키는 유일하다.
2) 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3) 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4) 왼쪽과 오른족 서브트리도 이진 탐색 트리이다.

이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 정확히 말하면 O(h)라고 표현하는 것이 좋다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 이러한 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다. 저장 순서에 따라 계속 한쪽으로만 노드가 추가되는 경우가 발생하기 때문이다. 이 경우 성능에 영향을 미치게 되며, 탐색의 worst case가 되고 시간 복잡도는 O(n)이 된다.

배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해 rebalancing기법이 등장하였다. 균형을 잡기 위한 트리 구조의 재조정을 rebalancing이라 한다.

Hash Table

hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 검색하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대하여 시간 복잡도가 O(1)이 되는 것이다. 하지만 문제는 이 인덱스로 저장되는 key값이 불규칙하다는 것이다.

그래서 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에서 추가되는 비용이 없도록 만들어진 구조이다.

특별한 알고리즘이란 것을 통해 고유한 인덱스 값을 설정하는 것이 중요해보인다. 위에서 언급한 '특별한 알고리즘'을 hash method 또는 해시 함수(hash function)을 통해서 작은 범위의 값들로 바꿔준다.
하지만 어설픈 hash function을 통해서 key값들을 결정한다면 동일한 값이 도출될 수 가 있다. 이렇게 되면 동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것인데 이를 collision이라고 한다.

collision : 서로 다른 두 개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미)되면 같은 곳에 저장할 수 없게 된다.

좋은 해쉬 함수란?

해쉬 함수를 무조건 1: 1로 만드는 것보단 collision을 최소화하는 방향으로 설계하고 발생하는 collision에 대비해 어떻게 대응할 것인가가 더 중요하다. collision이 많아 질수록 search에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워진다.
따라서 hashing된 인덱스에 이미 다른 값이 들어 있다면, 세 데이터를 저장할 다른 위치를 찾은 뒤에야 저장할 수 있는 것이다. 따라서 충돌 해결은 필수이다.

해쉬충돌 해결법 알아보기