자료구조
자료구조(Data Structure)란 컴퓨터에 데이터를 어떻게 메모리에 저장하고 관리할 것인지 지정하는 구조를 말한다.
데이터를 특정 기준점을 두고 그 위에 아래부터 쌓아올리고 위에서부터 빼는 식. 아래부터 순차적으로 보관할 데이터를 입력/삽입하는 작업을 Push, 위에서부터 순차적으로 보관했던 데이터를 출력/삭제하는 작업을 Pop이라고 한다.
탐색은 Pop 후 원하는 원소를 확인하고 다시 Push해야 하므로 O(n)의 시간 복잡도를 가지며 삽입/삭제의 시간 복잡도는 O(1)이다.
CPU의 프로시저 호출/함수 호출시 필요한 데이터를 적재하는 방법(기존 코드로 돌아가야 하는 위치, 함수 파라미터 및 함수 스코프 내에 정의된 변수 등)이 스택을 사용한다. 왜냐하면 이 작업들은 반드시 적재할 데이터의 순서를 유지해야 정상 동작하기에 탐색보다는 삽입/삭제에 특화된 스택이 유리하기 때문이다.
리스트의 한쪽 끝에서 데이터를 넣기만 하고, 반대쪽 끝에서는 빼기만 하는 자료구조다. 데이터를 넣는 작업을 Enqueue, 빼는 작업을 Dequeue라고 한다.
데이터의 탐색과 삽입/삭제 작업의 시간 복잡도가 스택과 같으나 넣고 빼는 자리가 같지 않기 때문에 데이터 통신에 매우 유리한 자료구조다. 따라서 메세지 통신 방식으로 동기화 수행하는 CPU 내 병렬화된 작업은 큐를 사용한다. 그 외에 프로세스 스케줄링에도 Round Robin 정책처럼 큐를 사용하는 알고리즘이 있다.
보통 그냥 큐를 쓸 수도 있지만 데이터 정렬의 문제로 Enqueue/Dequeue할 위치를 가리키는 포인터가 리스트 끝에 도달하면 삽입/삭제 시 처음 원소가 있는 위치로 돌아가게 하는 원형 큐로 응용하는 경우가 많다. 이때는 삽입 포인터/삭제 포인터의 위치가 같을 때 큐가 비었는지, 혹은 꽉 찼는지 확인시켜줄 별도의 변수를 필요로 한다.
선형으로 리스트를 구성하되 인덱싱을 하지 않고 한 원소가 자기 자신에게 담긴 값(Value)와 다른 원소를 가리키는 포인터(Pointer)를 전부 내장한 자료구조이다. 보통 다음 원소를 가리키는 포인터만 있는 단방향 연결 리스트(Singly Linked List)와 다음 원소 및 이전 원소를 모두 가리키는 포인터들이 있는 양방향 연결 리스트(Doubly Linked List)가 있으며 마지막 원소의 다음 원소 포인터를 처음에 연결하고 양방향 연결 리스트에 한해 첫 원소의 이전 원소 포인터도 마지막 원소에 연결한 환형 연결 리스트(Circular Linked List)이란 응용법이 있다.
탐색이나 삽입/삭제가 모두 O(n)이 걸리기에 보관할 데이터 크기가 커질 수록 연결 리스트를 다루는 성능이 다른 자료구조 대비 상당히 낮아지나, 메모리 영역의 위치 선정 및 크기 조절이 매우 자유롭다는 특성 때문에 종종 쓰인다. 스택과 큐의 근본적 단점인 데이터를 넣는 곳과 빼는 곳이 '정해져 있다'를 극복하여 데이터를 넣고 빼는 곳이 정해져 있지 않는 데크(Deque 또는 DEQ - Double Ended Queue)도 사실 양방향 연결 리스트이다.
나뭇가지처럼 상위에 하나의 뿌리(루트, Root)를 두고 그 아래에 가지를 내어 원소의 데이터 배치를 위에서 아래로 가는 방사형으로 전개할 수 있는 모든 자료구조를 트리라고 한다. 이때 배치하는 원소들은 노드라 하여 자기 자신이 담은 데이터와 자식 노드로 가는 포인터들을 담고 있다. 그래서 트리는 버텍스와 엣지를 가지는 그래프(Graph)의 일종이기도 하다.
트리의 깊이(Depth)는 루트 노드로부터 현재 노드까지의 최단 길이(Length)이고, 루트 노드로부터 가장 멀리 떨어진 단말 노드(리프 노드라고도 한다)까지의 최대 깊이는 Height라고 하며 루트 노드로부터 개별 노드 사이의 경로(Path) 수의 총합이 같은 노드들은 같은 레벨(Level)이라고 한다.
한 노드가 가질 수 있는 자식의 갯수를 차수(Degree)라고 하며, 트리의 최대 차수를 트리의 차수(Degree of Tree)라고 따로 부른다. 트리의 너비(Width)은 가장 많은 노드가 속하는 레벨의 노드 개수로 한다. 최대 Degree가 n으로 정해진 경우 n진 트리라고 따로 명칭을 붙인다.
지수적인 스케일(Exponential Scale)을 가진 데이터를 트리의 리프 노드에만 넣거나 트리 내 노드 전체에 넣는 방식으로 탐색/삽입/삭제 시간을 획기적으로 단축할 수 있기 때문에 큰 스케일의 데이터를 다룰 때 보통 트리 구조로 정렬하여 다루는 방법을 가장 먼저 생각하게 된다. 가령 2의 n승 단위로 크기가 변하는 데이터가 있다면 이진 트리에 집어넣는 순간 탐색의 시간 복잡도가 로그 값을 취하게 된다(시간 복잡도 O(log n)). 즉 선형적으로 탐색하면 수준의 시간이 걸린다 가정할 때 거기에 로그값을 취한 N 수준으로 시간 단축이 된다.[1]
트리 구조의 일반화라고도 볼 수 있는 그래프 (이산수학) 구조는 해당 문서를 참조하자.
이진 트리가 매우 신박한 특성을 가지고 있기 때문에 따로 서술하자면, 이진 트리 구조를 응용하여 두 자식 중 한쪽 방향 자식은 부모 노드보다 작은 값을, 다른 쪽 방향 자식은 부모 노드보다 큰 값을 담도록 일정하게 만들면 데이터가 사전에 정렬되었다는 것을 보장할 수 있다. 이것을 Binary Search Tree(이진 탐색 트리)라고 하며, 로그값을 취한 수준으로 탐색 시간이 단축되는 트리의 특성을 제대로 보여준다.
다만 원소를 삽입하거나 삭제할 경우 최악의 상황에서는 트리가 아니라 연결 리스트가 되는 수준으로 원소가 한쪽 방향으로만 삽입/삭제되는 경우가 있다. 이건 편향된(Skewed) 상태라고 하며 후술할 Red-Black Tree로 극복하는 것이 일반적이다.
2진 트리는 2의 제곱수로 같은 레벨의 노드를 구분할 수 있기 때문에 배열로 구현하는 것이 쉽고 빠르다.
이진 트리 안에 있는 원소를 순회하는 방법은 부모의 탐색 우선 순위에 따라 전위 순회(pre-order traverse), 중위 순회(in-order traverse), 후위 순회(post-order traverse) 3가지에 level 별 순회(level-order)가 추가로 있다. 이 중 전위 순회는 부모 -> 왼쪽 자식 -> 오른쪽 자식 순으로, 중위 순회는 왼쪽 자식 -> 부모 -> 오른쪽 자식 순으로, 후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 부모 순으로 탐색한다.
이진 트리 구조 같지만 내부에 값을 여러 개 담는 경우 B-Tree라고 부른다. 노드에서 다음 노드로 넘어갈 때 필요한 연산들이 너무 많은 경우 적절히 값들을 모아 한 노드 안에서 탐색할 수 있게 하는 최적화다. 느린 저장 매체(하드디스크 등)에 파일 시스템으로 데이터를 담은 경우 I/O 대기 시간이 긴데 이때 B-Tree를 활용한 파일 시스템(예시: btrfs)으로 파티션을 만들면 I/O 성능 개선에 효과가 있다.
트리 노드에 두 종류의 색이라는 개념을 추가하여 트리가 한쪽 방향으로 편향되는 것을 어느 정도 억제하는 응용형 트리다. 리눅스의 프로세스 스케줄링 알고리즘이 프로세스들을 담을 때 이 자료구조를 활용한다.
부모가 항상 자식보다 크거나 반대로 부모가 항상 자식보다 작게 정렬된 이진 트리는 '힙 트리(Heap Tree)'라고 한다. 큰 규모의 데이터 내의 최대 최소 비교 목적에 최적화되어있다. 역시 이진 트리이기 때문에 메모리 상의 배열로 구현하는 것이 쉽고 빠르다.
삽입과 삭제는 O(log N)의 시간 복잡도로 부모와 자식을 맞바꾸는 정렬을 수행하며 진행된다.
리스트의 합을 자주 연산해야 하는 경우 리스트를 이진 트리의 리프 노드에 배치하고 그 부모들에 합을 미리 저장하는 기법을 세그먼트 트리라고 한다. 보통 세그먼트 트리의 원소 수는 합을 써야 한다는 특징을 감안해 특별히 노드 번호를 1부터 붙인다. 초기화 및 탐색은 분할 정복을 이용한다.
- C언어 등지에서 메모리 관리용으로 삼는 배열(Array) 또는 벡터 자료형, 일반적인 리스트 역시 자료구조이다(선형 자료구조라 한다). 접근 시간 복잡도 O(1), 삽입의 시간 복잡도가 O(1), 삭제의 시간 복잡도가 O(n)이다.
- 아니면 값이 될 데이터를 해싱한 결과인 해시값으로 인덱싱을 하는 해시 테이블도 있다. 해싱 알고리즘은 가장 간단하게는 나머지 연산부터 MD-5 같은 복잡한 알고리즘 사용까지 다양하다. 이쪽은 값 그 자체가 인덱싱에 영향을 주므로 탐색과 삽입, 삭제가 해싱 알고리즘 부분을 제외하면 O(1)이라는 기가 막힌 속도를 자랑하나, 삽입/삭제의 경우 비둘기집 원리에 의해 해시값이 중복될 가능성(해시 충돌)이 있어 해당 상황에서 데이터를 옮겨 저장할 방법을 같이 구현해야 한다.
- 우선순위 큐 같이 새로운 개념을 위해 기존 자료구조를 활용하는 경우가 있다. 우선순위 큐의 경우 배열, 연결 리스트, 힙 트리로 구현하는 방법들이 있으며, 보통 힙 트리가 최악의 상황에서도 O(log n)이 나오기에 힙 트리 구현 후 우선순위에 따라 삽입 후 필요한 만큼 heapify 연산을 사용해 루트 방향으로 밀어올리면 된다.
- ↑ 그렇다고 트리 구조가 항상 만능인 건 아니고, 기본적으로 메모리 사용량이 큰 편이라 적은 양의 데이터들을 보관할 때에는 다른 자료구조 대비 불리한 편이다.