알고리즘과 자료 구조 - 2

저번 시간에 이어서 자료구조에 대해서 좀 더 알아보도록 하자.

자료 구조에 대해서 다시 정리해 보면 분류에 따라 나눌 수 있고, 형태에 따라 나눌 수도 있다. 저번 시간에 설명한 배열과 원형 연결 리스트, 이중 연결 리스트 등이 구현에 따라 나누어진 자료 구조 형태이며 이번에는 형태에 따라 나뉘는 자료 구조에 대해 알아보자.

가장 첫 번째로는 '스택'이라는 자료 구조이다. 이 자료 구조 형태는 어떠한 컵이나 과학 실험을 할 때 쓰이는 비커를 떠올리면 이해하는 데 도움이 된다. 컵이나 비커의 모양은 어떻게 되어있는가? 위로는 액체를 비롯하여 어떠한 물체를 위에서부터 부어서 담을 수 있는 형태이며 아래는 막혀있어서 예를 들어 밀도가 다른 흙을 넣는다고 가정하면 그 흙은 넣는 순서대로 밑에서부터 쌓일 것이다. 스택이 이러한 컵이나 비커의 구조와 거의 유사하다. 스택도 자료를 담으면 그 순서대로 아래서부터 쌓이는 구조이다. 컵이나 비커에 흙을 넣었는데 맨 아래의 흙을 다시 꺼내야 할 때는 어떻게 하는가? 우리는 곧장 맨 아래에 깔린 흙을 꺼낼 수는 없다. 위에 쌓여있는 흙부터 꺼낸 뒤에야 우리가 꺼내려고 했던 맨 아래층에 깔린 흙을 꺼낼 수 있다. 스택 구조도 먼저 저장된 자료를 꺼내어 쓰고 싶을 때는 제일 나중에 꺼내서 사용할 수 있고 반대로 제일 나중에 넣은 자료는 제일 첫 번째로 자료를 꺼내서 사용할 수 있는 구조이다. 이 구조를 선형 구조라고 한다. 또한 스택 구조는 Last In Last Out의 구조로 자료를 한쪽 면에서만 관리할 수 있는 구조이다. 자료를 스택 구조에 넣는 것을 push라고 하며 자료를 스택 구조에서 꺼내는 것을 pop이라고 한다. 예를 들어, 스택 구조에 알파벳을 순서대로 저장하기 위해 A 세 개의 알파벳을 A 순서로 push 했다고 가정하면 아래부터 a 순서로 쌓여있다고 상상하면서 구조를 떠올려보면 이해하기 쉽다. 이러한 스택 자료구조의 장점으로는 단순한 구조로 구현이 용이하며 데이터를 저장하고 읽는 속도가 빠른 장점이 있다. 단점으로는 데이터 최대 개수를 미리 정해야 하는 제한적인 부분이 있으며 저장 공간의 낭비가 발생할 여지가 있다.

두 번째 자료구조로는 큐가 있다. 큐는 양쪽이 뚫린 원통 모양을 떠올리면 구조를 이해하는 데 도움이 될 것이다. 빨대 모양이 바로 그 모양의 예로 들 수 있다. 만약에 원통 모양의 소시지를 만드는 기계 소시지 재료를 넣는다고 치면 어떻게 되는가? 넣은 입구 반대쪽, 즉 출구로 가장 먼저 넣은 소시지 재료 부분이 나오기 위해 시작할 것이다. 이 큐 자료구조는 스택과는 다르게 (First In First Out) 구조인데 들어간 순서대로 나오는 순서도 그대로 나오게 된다. 즉, 가장 먼저 넣은 자료는 꺼낼 때도 가장 먼저 꺼낼 수 있고 가장 나중에 넣은 자료는 제일 나중에 꺼낼 수 있는 구조이다. 따로 장단점은 언급되는 부분은 없으나 사용에 따라 단점이 될 수도 있는 점은 자료가 쌓여있는 상태에서 새로운 자료를 넣었을 때 그 자료를 출력하려고 하면 순서를 기다렸다가 출력해야 하는 단점이 있을 수도 있겠다.



앞에서 말한 두 가지 자료 구조는 선형 구조에 해당하는 자료구조들이다. 이것과 다르게 비선형구조로 된 자료구조도 있는데 지금부터 알아보자. 



비선형 구조에는 첫 번째로 우리가 흔히 볼 수 있는 그래프가 있다. 그래프는 꼭짓점과 꼭짓점을 있는 변으로 구성된 것이다. 두 번째로는 트리가 있다. 트리는 말 그대로 구조의 모양이 트리 모양인데, 한 꼭짓점을 제일 상단의 노드로 기준을 잡고 그 아래로 뿌리를 뻗어나가는 형태로 구조가 이어지는 형태를 말한다. 이 사이의 자료들은 부모와 자식 관계의 노드로 볼 수 있다. 최상위 노드를 루트 노드라고 하며 그 아래로 순차적으로 뻗어나가는데, 예를 들어 A 노드가 B 노드를 가리키면 A는 B의 부모노드라 할 수 있고 B는 A의 자식노드라고 할 수 있다. 그리고 이렇게 계속해서 구조를 만들어 나가다가 자식 노드 없는 노드에 이르면 그 노드는 잎 노드(leaf node)라고 한다. 그리고 부모 노드나 자식 노드가 있는 중간에 있는 노드들은 내부 노드라고 한다. 트리구조 중에서 유명한 자료구조는 이진 탐색 트리, 빨간색-블랙 트리가 있다.

이진 탐색 트리는 한 노드의 자식 노드가 최대 2개인 자료구조이다. 이진 트리의 종류로는 여러 가지가 있는데 포화 이진 트리, 완전 이진 트리, 높이 균형 트리 등이 있다.

완전 이진 트리는 단말 노드들이 트리 왼쪽부터 순차적으로 채워진 형태의 이진 트리이다. 포화 이진 트리는 모든 레벨의 노드가 꽉 차 있는 형태이며 잎 노드를 제외한 모든 노드의 차수가 2인 이진 트리를 말한다. 그리고 높이 균형 트리는 모든 단말 노드의 깊이 차이가 1인 이진 트리를 말한다.



빨간색-블랙 트리는 각 노드의 자료에 숫자 등과 같은 자료 외에 색상 속성을 가지는 이진 탐색 트리를 말한다. 여기서 색상은 빨간색과 검은색 두 가지를 가진다. 먼저 최상위 노드(루트 노드)의 색상은 블랙이며 그 아래로 뻗어나가는 자식 노드들의 색상은 빨간색 혹은 블랙 둘 중 하나이다. 그리고 잎 노드들의 색상은 모두 블랙이며 이 색상은 번갈아 가면서 색상을 가지게 된다. 부모 노드의 색상이 빨간색이었다면 자식 노드는 블랙이며 이 자식 노드의 자식 노드는 빨간색이 된다. 이러한 빨간색-블랙 트리가 가지는 가장 큰 특성은 루트 노드로부터 가장 먼 잎 노드 경로까지 거리가 가장 가까운 잎 노드 경로까지의 거리의 두 배보다 항상 작다는 것이다. 빨간색-블랙 트리는 개략적으로 균형이 잡혀 있는 자료 구조이며 삽입, 삭제, 검색 시 시간복잡도가 트리의 높이(깊이)에 따라 결정되므로 이진 탐색 트리에 비해 효율적이라고 할 수 있다.