Data Structure - 질문 Part 1

marafo·2021년 2월 11일

∙ Activation Record

시스템 스택에 함수가 호출될 때마다 만들어지는 활성 레코드를 의미한다. 스택에 저장되는 프레임으로서 특히 운영체제에서 문맥교환이 일어날 때, 함수 상태값들을 기록해놓는다. 프로세스가 (실행 -> 대기 or 준비) 상태가 되면 함수의 실행을 끝내고 돌아갈 복귀주소, 반환값, 로컬 변수, 파라미터 등이 기록된다.

∙ ADT(Abstract Data Type)

자세한 구현이나 프로세스 없이 기능 자체가 무엇인지만 나열한 자료형. 대표적인 배열의 추상데이터 타입은 다음과 같다.

create() : 원소를 저장할 수 있는 공백 배열 생성. 원소값 정의나 할당이 되지 않은 상태.

retrieve() : 원소를 단순히 원소자체로 생각하지 않고 index-값 조합으로 생각해서 출력하려는 index가 존재하면 해당 원소값을 출력하고 없으면 null이나 error를 반환

store() : 인덱스 유효성을 검사해서 index-원소 쌍으로 배열에 저장하고 반환한다.

∙ 연결리스트 구조 및 생성 과정

구조

연결리스트의 원소들은 노드로 구성되는데 이는 다시 데이터 필드와 링크 필드로 나뉜다. 링크 필드를 통해 다음 노드를 가리키는 포인터를 저장할 수 있고 데이터 필드는 문자열, 숫자형, 구조체 같은 실제 데이터가 저장된다. 단 처음 노드를 알아야 하는데 이를 가장 앞단의 head pointer에서 담당한다. 마지막 노드에서는 다음 노드가 존재하지 않으므로 링크 필드에는 null이 저장된다.

생성 과정(순차적 서술)

노드 정의 : 자기 자신을 참조하는 포인터 구조체를 만든다. 데이터 링크에 원소의 타입을, 링크 필드엔 포인터를 저장한다. 노드의 기본 골격을 정의하는 과정이다.

공백리스트 생성 : 연결리스트에 추가되는 노드를 찾을 수 있게 head pointer를 만들고 그 값을 null 공백 상태로 만들어 놓는다.

노드 생성 : 동적 메모리 할당을 활용해 노드를 생성하고 데이터 필드에 값이 할당되고 링크 필드는 null로 놔둔다. 반대로 노드 삭제는 포인터 연결을 끊고 동적메모리를 해제한다.

노드 연결 : 원하는 만큼 노드를 만들었다면 마지막 노드(null)를 제외하고 각 노드의 링크필드의 포인터를 통해 연결한다.

∙ 연결리스트와 배열의 차이

배열은 순차적인 메모리 공간 할당이 이루어지며 배열 내 상대적 위치인 index로 원소에 직접 접근을 하는 자료구조이다. 따라서 데이터 탐색 속도가 O(1)으로 빠르다. 하지만 배열의 크기가 고정되는 단점을 가진다. 또한 원소 삽입, 삭제 시에 기존 원소의 인덱스를 필요한 만큼 최대 O(n)으로 움직여야 한다(만약 가장 뒷단에 원소를 push한다면 O(1)으로 삽입이 가능할 수 있다).

연결리스트는 특정 원소의 다음 데이터의 위치를 포인터(원소 이외에 메모리 공간 따로 필요)로 표현하며 유연한 동적 메모리할당이 가능하다. 배열의 집합적 성격보단 데이터간 '연결성'이 더 부각된다. 따라서 데이터의 입력 순서가 연결리스트에서 물리적 순서와 일치하지 않을 수 있다. 원소 삽입 삭제시에 다음 원소를 가리키는 일부 포인터를 수정하여 O(1)의 복잡도로 배열보다 간편하게 수행할 수 있다. 하지만 데이터 탐색시에 맨 앞단부터 차례로 탐색해서 시간복잡도가 최악 O(n)이 될 수 있다.

+) 배열보다 연결리스트를 쓸 때 효율적인 경우

데이터 삽입, 삭제가 많이 필요한 연산이나 동적 메모리 할당이 요구되는 작업일 때 연결리스트가 배열보다 더욱 좋은 옵션이 될 수 있다.

∙ Tree

일상 생활이나 특정 현상(컴퓨터 파일구조, 그룹의 조직도 등)의 데이터를 배열, 스택, 큐처럼 선형적으로 나열하기 어렵고 계층적 구조를 필요로 할 때 사용되는 자료구조이다.

Edge : 노드와 노드를 연결하는 간선이다.
Degree : 특정 노드가 가지고 있는 자식 노드의 수
Height : 트리가 가지고 있는 최대 레벨의 길이
Terminal Node : 자식 노드가 없는 단말 노드
Non-Terminal Node : 자식 노드가 있는 비단말 노드

∙ Binary Tree

모든 노드에 2개의 서브 트리를 가지고 있는 트리이다. 서브트리는 특정 데이터를 갖거나 공집합(null)으로 구성된다. 서브트리가 최대 2개이므로 각 노드의 차수는 2를 넘어설 수 없다. 그리고 서브 노드도 부모 노드와 같이 이진 트리의 구조를 가져야 한다. 좌우 서브트리는 순서가 구별된다(특히 사칙 연산을 트리구조로 표현할 때).

나머지 이진트리의 특징은 다음과 같다.

노드의 개수가 n이라면 (n - 1)개의 Edge를 갖는다.
높이가 h인 이진 트리라면 최소 h개, 최대 (2^h - 1)개의 노드를 갖는다.
노드가 n개인 이진트리는 최대 높이 n, 최소 높이 log_2__(n + 1)을 갖는다.

+) 완전 이진 트리(complete binary tree)

(높이 k라는 가정)레벨 1인 루트노드에서 레벨 k - 1 까지는 모두 서브트리 노드가 채워지고 가장 아래 레벨k에서는 왼쪽 -> 오른쪽순 차례로 채워지는 트리를 말한다. 단, 가장 아래 높이 레벨에서의 서브트리는 왼쪽부터 순서만 지켜진다면 다 채워질 필요는 없다.

+) Binary Tree 표현 및 순회 : c언어로 풀어쓴 자료구조 263p

+) 성능

높이 h : O(h)
노드 n개 : O(log_2_n)
경사이진탐색트리(노드가 한쪽 편향) : 탐색, 삽입, 삭제가 O(n). 거의 선형 탐색

∙ Binary Search Tree

이진 탐색트리에서 각 노드의 원소가 구별될 수 있는 유일한 'key'를 가진다. 좌측 서브트리 < 부모 노드 < 우측 서브트리 순의 대소 관계를 가진다. 또한 좌우 서브트리도 이진 탐색트리의 구조를 가져야 한다. 이 조건들을 만족한다면 어느 정도의 느슨한 정렬 상태를 가지며 중위순회를 기초로 탐색한다.

삽입연산 : 원소 삽입 전, 이진 탐색을 먼저 수행한다. 삽입 추가하려는 키 값이 기존 트리에 중복되지 않는지 체크하고 탐색에 실패한 지점이 삽입될 위치이기 때문이다.

삭제연산(c언어로 풀어쓴 자료구조 301p)

1) 단말노드
단말노드의 부모노드의 link field를 null로 만든다.

2) 비단말노드 - 서브트리 1개
해당 비단말노드를 삭제하고 서브트리를 그 자리로 옮긴다.

3) 비단말노드 - 서브트리 2개
해당 노드를 삭제하고 좌측 서브트리에서 가장 큰 오른쪽 값, 우측 서브트리에서 가장 작은 왼쪽 값 중 하나를 골라 삭제된 자리로 옮긴다.

∙ AVL Tree

이진 탐색 트리에서 |좌우 양쪽 서브트리의 높이차| <= 1 (-1, 0, 1)인 트리를 말한다. 높이차(균형인수)가 1 이하가 아닐 때 비균형 상태라 정의하고 1로 맞춰가기 위해 노드를 회전으로 재배치한다. 새로운 노드가 추가되어 비균형이 되면 추가된 노드부터 균형인수가 2인 지점에 있는 부모 노드를 회전 재배치한다. 시간복잡도는 이진 탐색 트리와 동일한 O(log_2_n)이 된다.

∙ Priority Queue

기본적인 큐에 우선순위를 입힌 자료구조를 정의한다. 우선 순위가 높은 원소순으로 가장 중요한 삽입, 삭제 연산을 먼저하게 된다. 물론 우선순위 큐는 스택이나 큐로 동작할 수 있다. 보통 히프(Heap)를 통해 효율적 구현이 가능하다.

히프는 계층적 완전 이진트리 구조에서 부모 노드의 키값(우선순위)을 자식 노드보다 높게 할당(최대 Heap 기준)해서 여러 데이터의 집합에서 최대나 최솟값을 신속하게 찾아내기 위한 자료구조이다. 일반 트리에서는 value 값만 가지지만 우선순위 큐는 key-value 조합의 비선형 데이터다. 또한 노드값들의 중복을 허용하며 부모 노드 상위 - 자식 노드 하위 구조만 지키는게 목적이므로 반드시 완벽한 정렬 상태를 갖진 않는다.

최소 Heap : 부모 노드의 값이 자식 노드보다 작거나 같은 완전 이진트리
최대 Heap : 부모 노드의 값이 자식 노드보다 크거나 같은 완전 이진트리

+) 히프의 삽입 삭제 연산 : c언어로 풀어쓴 자료구조 330p

+) 히프의 삽입 삭제 연산 : c언어로 풀어쓴 자료구조 340p

+) 히프의 복잡도 : 삽입 삭제 모두 연산이 끝나고 우선순위에 따라 부모-자식간 위치 교환이 발생한다. 가장 많은 교환이 발생하는 경우 log_2_n이 히프의 높이까지 고려하기 때문에 삽입 삭제는 O(log_2_n)의 복잡도를 필요로 한다.

참고)

Activation Record
∙ c언어로 풀어쓴 자료구조 103p
∙ https://m.blog.naver.com/PostView.nhn?blogId=swryu02&logNo=220696545412&proxyReferer=https:%2F%2Fwww.google.com%2F

ADT
∙ https://rap0d.github.io/study/2019/07/16/ds_3_배열추상데이터타입/
∙ c언어로 풀어쓴 자료구조 177p

연결리스트와 배열의 차이
∙ c언어로 풀어쓴 자료구조 184p
∙ https://noahlogs.tistory.com/30
∙ https://letitkang.tistory.com/111
∙ https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/

연결리스트의 구조
∙ c언어로 풀어쓴 자료구조 185p

Priority Queue
∙ https://eremo2002.tistory.com/21
∙ https://eremo2002.tistory.com/21
∙ c언어로 풀어쓴 자료구조 322p, 326p
∙ https://mangkyu.tistory.com/90
∙ https://chanhuiseok.github.io/posts/ds-4/

Tree
∙ c언어로 풀어쓴 자료구조 254p

Binary Tree
∙ c언어로 풀어쓴 자료구조 258p