Learn/이론 정리 2020. 2. 23. 19:53 1. 자료구조란? 사전적인 의미 - 자료의 집합으로 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것. 목적 - 자료를 저장, 관리를 더 효율적으로 하기 위함으로 실행시간의 단축(시간복잡도)와 메모리 용량의 절약(공간복잡도)을 목적으로 자료구조를 선택한다. 즉, 컴퓨터에서 사용항 자료를 효율적으로 관리하고 구조화 하기 위한 작업이다. 2. 자료구조의 종류 자료구조는 자료의 구성에 따라 순차적으로 나열하는 선형구조, 비 순차적으로 나열하는 비선형구조로 나뉜다. 선형구조 - 선형리스트, 연결리스트, 스택, 큐, 데크 비선형구조 - 트리, 그래프 3. 선형구조
4. 비선형 구조
자료구조에 대해서 찾아보면 다양한 종류의 자료를 효율적으로 처리하기 위해 자연스럽게 알고리즘과 각 자료구조의 특징을 확인 하기 위한 시간 복잡도, 공간 복잡도에 대한 개념을 많이 볼 수 있을 것이다. 다음 포스팅은 자료 처리의 기본 삽입, 탐색 알고리즘과 시간 복잡도, 공간 복잡도 대해서 정리하려고 한다. ※ 참고 블로그 https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html 'Learn/이론 정리' Related Articles*참고사이트 : http://soen.kr 1. 배열 배열은 C언어가 제공하는 가장 기본적인 자료 구조이며 워낙 단순하기 때문에 누구나 쉽게 익숙해질 수 있다. 배열의 장점은 크게 두 가지가 있는데 첫 째로 구조가 단순하기 때문에 정보 자체를 기억하는 메모리 외에 추가로 소모하는 메모리가 전혀 없어 공간 효율이 좋다.정수형 변수 100개를 저장하는 int ar[100] 배열은 정확하게 정수 100개분만큼의 메모리만을 요구한다. 둘 째로 배열 크기가 아무리 커지더라도 검색 속도가 일정하다. 배열의 첨자 연산은 포인터를 통해 시작 번지에 첨자*요소크기를 더하는 간단한 동작이므로 임의의 한 요소를 참조하는 시간이 상수이다. int ar[10]에서 ar[9]를 참조하는 시간과 int ar[1000]에서 ar[999]를 참조하는 시간이 똑같다는 얘기이다. 이처럼 배열은 메모리 요구량이나 속도면에서 모두 만족할만한 성능을 보이는데 요약하자면 작고 빠른 자료구조이다. 게다가 쓰기도 쉬워 다양한 용도에 아주 요긴하게 사용된다. 그러나 이런 편리한 배열에도 한 가지 단점이 있는데 배열 요소가 연속된 메모리 공간에 배치되어 있어야 하므로 중간의 요소를 삭제하거나 새로운 요소를 삽입할 수 없다는 점이다. 배열은 일반적으로 삽입, 삭제가 안되는 것으로 알려져 있는데 이는 일종의 고정 관념이다. 방법을 찾아 보면 조금 불편하기는 하지만 전혀 불가능한 것은 아니다. 다음 예제는 문자형 배열을 대상으로 삽입, 삭제하는 방법을 보여준다.(memmove : c의 메모리 이동 메소드 사용) 2. 연결리스트 2-1. 단순 연결 리스트 동적 배열은 같은 타입의 데이터 여러 개를 저장할 수 있는 가변 크기를 가지는 자료 구조이다. 이런 목적으로 사용할수 있는 자료구조가 연결 리스트이다. 연결 리스트와 동적 배열은 완전히 용도가 같은 자료 구조로서 서로 대체 가능하지만 구성 원리나 관리 방법은 질적으로 다르다. 연결 리스트의 대체 자료 구조는 배열이 아니라 동적 배열임을 주의. 연결 리스트는 요소들이 메모리의 도처에 흩어져서 존재하지만 링크에 의해 논리적으로 연결되어 있어 링크를 따라가면 이전, 이후 요소들을 찾을 수 있다. 삽입, 삭제를 할 때도 물리적인 메모리 이동없이 요소간의 링크만 조작하면 되므로 속도가 빠르다. #배열과 연결 리스트가 메모리에 구현된 모양 비교  배열의 요소 하나는 자신이 기억할 데이터값만을 가지는데 비해 연결 리스트의 요소인 노드는 데이터외에 연결 상태에 대한 정보인 링크를 추가로 가져야 한다. 자기 다음의 요소가 누구인지를 스스로 기억하고 있어야 흩어져 있는 노드들의 순서를 알 수 있는데 이 연결 정보를 저장하는 것이 바로 링크이다. 링크를 하나만 가지는 것을 단순 연결 리스트(Single Linked List)라고 하고 두 개의 링크를 가지는 것을 이중 연결 리스트(Double Linked List)라고 한다. 노드를 구성하는 데이터와 링크는 타입이 다르기 때문에 노드는 이형 타입의 집합인 구조체로 정의된다. struct Node { int value; // 데이터 Node *next; // 링크 }; value멤버는 노드가 기억하는 정보의 실체인 데이터이다. 배열 요소 타입에 제한이 없는 것처럼 연결 리스트가 저장하는 정보의 종류에도 제한이 없으므로 노드의 데이터는 임의 타입, 임의 개수로 정의할 수 있다. 여러 개의 변수들을 한꺼번에 가질 수도 있고 포인터나 배열 또는 다른 구조체를 노드에 포함시키는 것도 물론 가능하다. 예제에서는 편의상 정수값 하나만을 노드에 포함시켰다. next 멤버는 다음 노드에 대한 포인터를 가지는 링크이다. Node 구조체안에 다른 Node 구조체의 번지 정보가 포함되어 있는데 자신에 대한 포인터를 멤버로 가지는 자기 참조 구조체이므로 크기가 무한대가 되지는 않는다(13-2-라 참조). 이 포인터가 가리키는 곳을 찾아가면 다음 노드가 저장된 곳을 알 수 있으며 또 다음 노드의 링크를 따라 가면 그 다음 노드를 연속적으로 찾을 수 있다. 노드들이 링크를 통해 서로의 위치를 기억함으로써 물리적으로 흩어져 있더라도 논리적으로는 한 덩어리의 정보가 될 수 있는 것이다. 단, 어떤 노드가 연결 리스트의 첫 번째 노드인지는 따로 저장해야 하는데 시작점을 기억하는 노드를 머리(head)라고 한다. 일단 머리 노드를 알아야 연속적으로 다음 노드를 찾을 수 있으므로 머리 노드는 언제든지 참조할 수 있는 전역변수로 선언하는 것이 보통이다. 머리는 연결 리스트의 진입점이며 항상 머리부터 검색을 시작하므로 연결 리스트의 대표 노드라고 할 수 있다. 이에 비해 동적 배열은 진입점을 가리키는 포인터로 대표된다. 다음 그림은 1, 2, 3 세 개의 노드를 가지는 연결 리스트가 메모리에 구현된 모양이다. 노드들이 메모리상의 임의 위치에 불규칙적으로 생성된다는 것을 강조하기 위해 노드의 위치도 불규칙적으로 그렸다. 하지만 노드의 물리적인 위치가 어디인가는 전혀 중요하지 않으며 실제 번지에 상관없이 링크에 의해 서로 논리적으로 연결되어 있으므로 일직선으로 그리는 것이 보통이다. 머리는 노드 1을 가리키고 노드1의 링크를 따라가면 노드 2가 있고 노드 2 다음에 노드 3이 있다. 노드 3의 링크는 NULL로 되어 있는데 다음 노드가 없다는 것은 곳 연결 리스트의 끝이라는 뜻이다. 2-2. 이중 연결 리스트 단순 연결 리스트는 자신의 다음 노드에 대한 링크(next)만을 가지기 때문에 뒤쪽으로만 이동할 수 있으며 앞쪽으로는 이동할 수 없다. 링크를 조작할 때도 앞쪽 노드의 링크를 액세스할 수 없기 때문에 항상 지정한 노드의 오른쪽에만 삽입할 수 있으며 특정 노드를 바로 삭제하지 못하고 다음 노드만을 삭제할 수 있다. 이에 비해 이중 연결 리스트는 전후의 노드에 대한 링크를 각각 따로 가진다. struct Node { int value; Node *prev; Node *next; }; 노드에 저장되는 데이터 외에 앞쪽 노드의 번지를 가지는 prev와 뒤쪽 노드의 번지를 가지는 next 링크가 포함되어 있다. 그래서 이중 연결 리스트의 노드는 자신의 뒤쪽 노드 뿐만 아니라 앞쪽 노드도 찾을 수 있으며 링크를 조작할 때도 앞뒤의 노드를 자유롭게 액세스할 수 있다. 즉 순방향뿐만 아니라 역방향 순회도 가능한 것이다. 대신 링크가 하나 더 들어가기 때문에 기억 장소를 그만큼 더 소비하고 링크를 관리하는 코드가 조금 더 복잡해진다는 것이 단점이다. 하지만 요즘의 컴퓨터 환경에서 메모리를 조금 더 쓰는 것은 큰 부담이 아닌데다 노드 관리가 자유롭기 때문에 단순 연결 리스트보다는 이중 연결 리스트가 훨씬 더 활용성이 높다고 할 수 있다. 3. 스택 스택은 LIFO(Last In First Out)의 원리로 동작하는 선형적인 자료 구조이다. 같은 타입의 자료 집합을 관리한다는 면에서는 배열이나 연결 리스트와 동일하지만 자료를 관리하는 방식이 미리 정해져 있다는 점이 다르다. 스택은 데이터가 들어가고 나오는 입구가 하나뿐이므로 입구로 들어간 데이터가 스택에 차곡차곡 쌓여 있다가 들어간 반대 순서로 나온다. 주로 계산중에 잠시 기억해야 하는 임시적인 자료를 관리하는 용도로 사용된다. CPU도 여러 가지 정보를 저장하기 위해 스택을 사용하는데 이를 시스템 스택이라 한다. 시스템 스택에는 함수로 전달되는 인수, 지역변수 등의 임시 변수들이 저장되고 함수 실행 후 돌아갈 복귀 번지도 저장된다. 이 내용은 스택 프레임을 공부할 때 이미 살펴본 적이 있다. 또한 함수 실행중에 필요한 임시 정보들도 스택에 저장되는데 주로 레지스터값을 대피시키는 용도로 사용한다. CPU의 레지스터 개수가 많지 않기 때문에 이미 사용중인 레지스터를 다른 용도로 쓰고 싶을 때는 스택에 잠시 저장해 두고 사용한 후 다시 원래값을 꺼내 복구한다. 시스템 스택은 CPU가 직접 사용하는 장소이므로 응용 프로그램은 여기에 자신의 데이터를 저장할 수 없다. 꼭 시스템 스택을 쓰고자 한다면 불가능한 것은 아니지만 어셈블리 코드로만 스택을 사용할 수 있고 규칙을 반드시 지켜야 하므로 무척 부담스럽다. 별도의 스택이 필요하다면 하드웨어 스택과 똑같이 동작하는 소프트웨어 스택을 만들 수 있다. 다음 예제는 배열로 정수형 스택을 구현한 것이다. #include <Turboc.h> int *Stack; int Size; int Top; void InitStack(int aSize) { Size=aSize; Stack=(int *)malloc(Size*sizeof(int)); Top=-1; } void FreeStack() { free(Stack); } BOOL Push(int data) { if (Top < Size-1) { Top++; Stack[Top]=data; return TRUE; } else { return FALSE; } } int Pop() { if (Top >= 0) { return Stack[Top--]; } else { return -1; } } void main() { InitStack(256); Push(7); Push(0); Push(6); Push(2); Push(9); printf("%d\n",Pop()); printf("%d\n",Pop()); printf("%d\n",Pop()); printf("%d\n",Pop()); printf("%d\n",Pop()); FreeStack(); } 스택을 구현하기 위해서는 세 개의 변수가 필요하다. Stack은 데이터를 저장할 저장소인데 필요한만큼 동적으로 할당하기 위해 포인터로 선언했다. 스택에 저장할 데이터와 같은 타입의 포인터를 선언하면 이 포인터가 곧 스택이 된다. 예제에서는 정수형 포인터를 선언했으므로 이 스택은 정수를 저장하는 스택이 되는데 임의의 모든 타입에 대한 스택을 만들 수 있다. 문자, 실수는 물론이고 구조체같은 큰 타입도 물론 가능하다. Size는 스택의 할당 크기이다. Top은 스택의 현재 위치를 가리키는 값이며 스택의 어디까지 차 있는지를 기억한다. InitStack 함수는 스택을 초기화하는데 인수로 전달된 aSize를 Size에 대입해 놓고 Size 크기만큼 메모리를 할당하여 Stack 포인터에 대입한다. 따라서 Stack은 Size 크기의 정수형 배열이 되며 Size개의 정수를 저장할 수 있다. 정적 배열로도 스택을 구현할 수 있지만 이렇게 하면 크기가 고정되어 버린다. 동적으로 할당하면 스택을 쓰는 쪽에서 필요한 크기를 결정할 수 있는데 필요한 최대 크기로 잡는 것이 좋다. 최초 스택에는 아무런 데이터가 들어 있지 않으므로 Top은 비어 있다는 뜻의 -1로 초기화한다. 배열이 0부터 시작하기 때문에 0은 자료가 없는 상태가 아니라 하나 들어 있는 상태이므로 비어 있는 것과는 다르다. FreeStack 함수는 스택을 파괴하는데 동적으로 할당된 메모리만 해제하면 된다. 스택에 데이터를 저장하는 동작을 푸시라고 한다. Push함수는 데이터가 들어 있는 Top을 1증가시킨 후 이 자리에 인수로 전달된 data를 집어 넣는다. 푸시 동작은 Top 증가, 그리고 Top에 data 대입 두 동작만으로 구현된다. 나머지 코드는 에러 처리 코드인데 스택의 크기가 무한하지 않기 때문에 가득차 있는지를 점검하는 것이다. Push는 할당된 스택 크기와 Top을 비교하여 Top이 스택의 마지막 요소보다 작을 때만 푸시한다. 스택이 가득 차서 더 데이터를 삽입할 수 없는 상태를 스택 오버플로우라고 하는데 이때는 삽입을 중지하고 에러를 리턴한다. realloc 함수로 재할당하면 필요한만큼 스택 크기를 더 늘이는 것도 가능하지만 일반적으로 스택은 고정된 크기를 가지는 것이 보통이므로 재할당하지는 않았다. 그래서 스택은 넉넉한 크기로 충분히 여유있게 잡아야 한다. 스택 오버플로우는 기억 장소의 부족보다는 무한 루프 등의 논리적인 오류로 인해 발생하는 경우가 더 많으므로 에러를 리턴하는 편이 더 안전하다. 스택에 저장한 값을 빼 내는 것을 팝이라고 하는데 이 동작도 아주 간단하다. Top 위치의 값을 읽고 Top은 하나 감소시킨다. 스택이 텅 비어서 더 꺼낼 데이터가 없는 상태를 스택 언더플로우라고 하는데 이때는 -1이라는 에러값을 리턴하도록 했다. 이렇게 되면 스택에서 꺼낸 값이 진짜 -1인 경우와 구분되지 않는 모호함이 있으므로 에러값을 좀 더 특이한 값(예:-101092)으로 선택하거나 아니면 별도의 출력용 인수를 사용할 수도 있다. 스택은 푸시와 팝을 정확하게 맞춰야 하므로 스택 언더플로우는 절대로 발생해서는 안되는 에러이다. 따라서 에러 처리를 하는 것보다는 assert(Top >=0)로 처리하는 것이 더 바람직하다. 푸시와 팝 동작에서 보다시피 Top은 스택의 최상단을 가리키며 최후로 삽입된 데이터를 가리키고 있다. 이 방식 외에 Top이 다음 삽입될 위치를 가리키도록 구현할 수도 있으며 이 경우 Top이 0인 상태가 빈 상태이다. 두 방식 모두 가능하므로 어떤 방식이든지 선택할 수 있되 한 번 정한 의미를 헷갈리지만 않으면 된다. 시스템 스택의 Top이 최후 데이터 위치를 가리키도록 되어 있으므로 보통은 이 방식을 따른다. 다음 그림은 스택에 1, 2, 3을 순서대로 넣었다 빼는 예이다. 최초 Top이 -1일 때는 스택이 비어 있으며 데이터가 삽입되면 Top이 위로 이동하면서 Top 위치에 데이터가 저장된다. 푸시되는 순서대로 스택에 데이터가 차곡차곡 쌓이며 팝할 때는 푸시된 역순으로 꺼내진다. 예제에서는 7, 0, 6, 2, 9를 차례대로 넣었다가 역순으로 빼서 출력해 보았다. 위 그림에서 스택의 아래쪽이 낮은 번지(배열 선두)이고 위쪽이 높은 번지이며 시스템 스택은 이와 반대로 되어 있다. 스택은 같은 타입의 집합이므로 연결 리스트로도 만들 수 있다. 연결 리스트를 쓸 경우 스택 크기가 처음부터 고정되지 않고 필요한만큼 얼마든지 늘릴 수 있다는 장점이 있다. 그러나 푸시, 팝 할 때마다 메모리를 할당하고 해제해야 하므로 속도가 느리고 메모리도 더 많이 소모한다. 임시적인 정보를 저장하는 용도상 스택은 굳이 길이가 가변적일 필요가 없으므로 연결 리스트로 스택을 구현하는 것은 합리적이지 않으며 배열이 더 잘 어울린다. 4. 큐 큐는 스택과 반대로 FIFO(First In First Out)의 원리대로 동작하는 자료 구조이다. 동일한 자료의 집합을 다룬다는 면에 있어서는 스택과 비슷하지만 가장 먼저 들어간 자료가 가장 늦게 나온다는 점이 다르다. 넣은 순서대로 자료를 꺼내가므로 순서대로 처리해야 하는 자료를 임시적으로 저장하는 용도로 흔히 사용한다. 고속도로 톨게이트에 줄 서 있는 차들의 행렬이 큐의 대표적인 예인데 먼저 도착한 차가 먼저 빠져 나가고 늦게 도착한 차는 앞 차가 지나갈 때까지 기다려야 한다. 저장되는 자료의 타입이 동일하므로 배열 또는 연결리스트로 큐를 구현할 수 있다. 상대적으로 간단한 배열로 큐를 먼저 구현해 보자. 일정한 크기를 가지는 배열을 만들고 여기에 자료를 저장한다. 큐는 자료가 삽입되는 곳과 삭제되는 곳의 위치가 다르기 때문에 두 개의 포인터를 관리해야 한다. 여기서 포인터라고 함은 위치를 가리키는 값(offset)이라는 뜻이지 C의 포인터 타입과는 다른 뜻이다. ▶ head : 다음 삭제될 위치를 가리킨다. ▶ tail : 다음 삽입될 위치를 가리킨다. tail 쪽에서는 새로 도착하는 자료가 끊임없이 쌓이기만 하고 head에서는 처리할 자료를 빼내 가기만 한다. 두 포인터의 의미를 잘 정해야 하는데 이미 삽입, 삭제된 위치가 아니라 다음 삽입, 삭제 위치라는 점을 유의하도록 하자. 큐에 4개의 자료가 저장된 경우를 그려 보면 다음과 같다. 왼쪽 그림에서 tail은 다음 삽입할 위치, head는 다음 읽을 위치를 가리킨다. head, tail이 삽입, 삭제된 최후 위치를 가리키도록 한다면 오른쪽 그림처럼 될 것이다. 물론 두 방식 모두 모호하지는 않으므로 어느쪽으로 구현해도 마찬가지이기는 하다. 데이터를 넣을 때 삽입을 먼저 하고 포인터를 증가할 것인지 아니면 포인터를 증가한 후 삽입할 것인지 순서가 달라질 뿐이다. 어떤 방식을 선택하든 상관없지만 한 번 정한 의미를 헷갈려서는 안된다. 여기서는 다음 위치를 가리키도록 의미를 정했으므로 삽입, 삭제 전에 포인터를 먼저 증가시켜야 한다. 큐를 초기화할 때 최초 head, tail은 모두 배열 선두인 0을 가리키는데 두 포인터가 같은 위치를 가리키면 대기중인 데이터가 없고 큐가 비어 있다는 뜻이다. 자료가 추가되면 tail 위치에 삽입되고 tail은 다음 칸으로 이동한다. 자료를 읽어서 삭제하면 head가 다음 칸으로 이동할 것이다. 이런 식으로 head와 tail은 자료가 삽입, 삭제될 때 배열의 뒤쪽으로 점점 이동하는데 다음은 다섯 개의 칸을 가진 큐에서 자료가 삽입, 삭제되는 과정이다. 삽입될 때는 tail이 배열의 오른쪽으로 이동하고 삭제될 때는 head가 배열의 오른쪽으로 이동한다. 이런 식으로 자료를 계속 삽입, 삭제하면 head, tail은 계속 뒤쪽으로만 이동하기 때문에 배열의 뒤쪽 공간이 금방 부족해진다. 위 그림에서 5가 삽입된 후 T는 배열 경계를 넘어서며 이 상태에서는 다음 삽입 동작을 할 수 없다. 그런데 앞쪽에는 먼저 들어왔던 자료들이 삭제되었기 때문에 공간이 비어 있다. 배열의 크기만큼 자료가 들어 있지도 않은데 기억 공간이 부족해진 것이다. 큐의 자료는 빈번하게 삽입, 삭제되므로 배열 크기를 늘리는 것으로는 이 문제를 근본적으로 해결할 수 없다. 이 문제를 해결하려면 tail이 배열 끝에 닿았을 때 head의 데이터를 배열 처음으로 보내고 tail 직전까지의 모든 데이터를 앞쪽으로 복사해서 이동시킨다. 데이터가 이동하면 포인터도 따라서 이동해야 한다. 이렇게 하면 앞쪽의 남은 공간이 뒤쪽으로 이동하므로 새로운 데이터를 삽입할 수 있다. 그러나 큐가 찰 때마다 이런 식으로 매번 복사를 한다면 느리고 비효율적이다. 그래서 이 방법 대신 포인터가 배열의 끝에 닿았을 때 앞쪽으로 보내어 배열을 원형(Circular)으로 연결하는 방법을 많이 사용하는데 이는 % 연산자로 간단하게 구현할 수 있다. head와 tail은 원형의 큐를 빙글 빙글 돌아가면서 자료를 삽입하고 삭제한다. 만약 삽입하는 속도가 삭제하는 속도보다 빨라 tail이 head를 따라 잡으면 큐가 가득찬 상태이다. head가 tail과 같은 상태는 큐가 빈 상태와 같으므로 두 포인터의 값만 비교해서는 큐의 정확한 상태를 알 수 없다. 그래서 head 바로 앞의 한 칸은 미사용으로 남겨 두어 tail이 head의 바로 앞쪽에 있을 때, 즉 tail이 head-1일 때를 큐가 가득찬 것으로 정의한다. 이렇게 하면 기억 장소 하나를 쓰지 못하는 약간의 낭비가 발생하기는 하지만 상태를 정확하게 판별할 수 있다. 5. 트리 여기까지 알아본 배열이나 연결 리스트, 스택, 큐 등은 모두 1차원의 선형적인 구조를 가지는데 비해 트리는 2차원적인 구조를 가진다. 구조가 입체적이고 다소 복잡하기 때문에 배열이나 연결 리스트보다는 다루기 어렵고 까다롭다. 또한 스택이나 연결 리스트처럼 구현 방법이 정형화되어 있지 않고 적용하는 알고리즘에 따라 천차 만별로 모양이 달라져 응용력을 필요로 하기도 한다. 그러나 입체적인 구조로 인해 자료의 삽입, 삭제 속도가 빠르면서도 검색 속도까지 만족할만하며 용량이 커지더라도 속도의 감소가 적어 대용량의 자료를 다룰 때 훨씬 더 효율적이다. 어느 정도 규모가 있고 복잡한 데이터를 다룰 때는 주로 트리가 사용되는데 상용 DB 엔진들도 트리 구조로 데이터를 관리한다. 디렉토리 구조나 기구도, 토너먼저 대진표 등과 같이 계층적인 자료들을 다룰 때도 트리가 가장 어울린다. 트리를 프로그래밍하는 방법을 배우기 전에 우선 트리에서 사용하는 용어부터 정리해 보자. 트리는 말뜻 그대로 나무를 뜻하므로 트리 구조에서 사용하는 용어들은 나무의 각 부분들인 경우가 많고 노드끼리 계층적인 관계를 이루므로 족보의 용어가 사용되기도 한다. 용어 자체는 상식적이므로 쉽게 이해되지만 같은 대상을 칭하는 동의어가 많아 조금 헷갈린다. 다음은 트리의 한 예인데 이 예를 통해 트리의 용어를 정리해 보자. 진짜 나무들은 뿌리가 밑에 있고 가지와 잎이 위로 자라지만 트리를 그릴 때는 위 그림처럼 루트를 위쪽에 그리는 것이 보통이다. 트리는 실제 데이터를 가지는 노드(Node)와 노드를 연결하는 링크(Link)로 구성된다. 위 그림에서 원으로 표현된 것이 노드이며 원을 잇는 선분들이 링크인데 노드, 링크라는 용어 대신 버텍스(Vertex), 에지(Edge)라는 용어를 사용하기도 한다. 트리의 노드들은 항상 루트로 향하는 링크를 하나씩 가지되 루트는 링크를 가지지 않으므로 링크의 개수는 항상 노드보다 하나 더 작다. 위의 트리는 노드가 14개이고 링크는 13개이다. 노드 중에 가장 기본이 되는 최상위 노드를 루트(Root)라고 부른다. 모든 트리는 단 하나의 유일한 루트를 가지며 루트 아래로 무수히 많은 노드들이 있다. 트리를 구성하는 노드끼리의 관계는 흔히 가족 관계에 비유하는데 아래쪽의 노드를 자식이라고 하며 위쪽의 노드를 부모라고 한다. 위 그림에서 B와 C는 A의 자식이며 E와 F의 부모는 B이다. 같은 부모를 가진 노드들을 형제라고 하는데 G, H는 공동의 부모 C에 소속되어 있으므로 형제 관계이다. 직속 관계가 아니더라도 아래쪽에 있으면 후손이며 위쪽에 있으면 선조라고 한다. 레벨(Level)은 루트에서의 거리를 의미하는데 루트의 레벨은 1이다. C 언어는 모든 숫자를 0부터 시작하지만 트리의 레벨은 1부터 시작(One Base)한다. 위의 트리에서 B의 레벨은 2이고 E의 레벨은 3이고 M의 레벨은 4이다. 높이(Height, 또는 깊이라고도 한다.)는 트리의 최대 레벨인데 가장 아래쪽에 있는 N의 레벨이 5이므로 이 트리의 높이는 5가 된다. 경로(Path)란 특정 노드에서 다른 노드로 가는 길이다. 어떤 노드에서 다른 노드로 가려면 공동의 조상까지 올라간 후 다시 아래로 내려 가야 하므로 두 노드 사이의 경로는 단 하나만 존재하는 특성이 있다. K에서 G로 가는 경로는 K-E-B-A-C-G 단 하나밖에 없다. 이에 비해 경로가 여럿 존재하는 자료 구조가 있는데 이를 그래프(Graph)라고 한다. 차수(Degree)는 자식 노드의 개수인데 B의 차수는 3, C의 차수는 2, M의 차수는 0이다. 차수가 0인 노드, 그러니까 자식이 하나도 없는 노드를 잎(Leaf) 노드 또는 외부(External) 노드라고 하며 자식이 있는 노드를 내부(Internal) 노드라고 한다. 위 트리에서 F, H, I, J, K, M, N이 트리의 마지막에 달린 잎 노드들이며 나머지는 내부 노드들이다. 노드의 자식들 사이에 순서가 있는 노드를 순서 트리(Ordered Tree)라고 하며 순서가 의미없는 노드를 비순서 트리(Oriented Tree)라고 한다. 다음 두 트리를 보자. 둘 다 A 밑에 B와 C가 있는데 순서 트리라면 이 둘은 다른 것이고 비순서 트리라면 같은 것이다. 순서 트리는 자식의 존재뿐만 아니라 순서도 의미가 있는 것이고 비순서 트리는 순서에 상관없이 어떤 자식이 있는가만이 중요한 트리이다. 트리를 구성하는 작은 트리를 서브 트리(Sub Tree)라고 한다. 마치 디렉토리의 계층에서 디렉토리 밑에 서브 디렉토리가 있는 것처럼 트리 아래에도 똑같은 모양의 서브 트리가 존재한다. 위 그림의 A 트리는 B 서브 트리와 C 서브 트리로 구성되어 있고 C 서브 트리는 다시 G, H 서브 트리로 구성되어 있다. 트리 여러 개가 모인 것은 포리스트(Forest)라고 하는데 나무들이 모여 숲을 이루는 것과 같다. |
자료구조 정리 pdf - jalyogujo jeongli pdf
관련 게시물
저작권 © 2024 ko.apacode Inc.
