자료구조 알아보기

자료구조란

• 자료의 추상화를 통해 자료의 논리적 관계를 구조화한 것
• 측정하고 관찰하여 쌓아 놓은 자료를 컴퓨터에서 사용할 수 있게 정리하고 분류해 놓은 것
• 알고리즘이 효율적으로 작동하기 위해서 필요한 다양한 자료의 논리적 구조나 관계

자료구조는 입력값에 대한 추상화의 결과, 알고리즘은 프로그램에 대한 추상화의 결과
 
추상 자료형: 자료값의 집합과 연산 집합에 대한 정의

(C언어 기준)
기본 자료구조: 정수, 실수, 문자 등
파생된 자료구조: 배열, 구조체, 포인터 등
사용자 정의 자료구조: 스택, 큐, 트리, 그래프, 리스트 등
 
알고리즘: 명령어들이 사람의 머릿속에서 추상화되어 존재하는 것
 
알고리즘의 조건

• 출력
  • 수행 후 적어도 한 가지 결과 생성
• 유효성
  • 반드시 실행 가능해야 한다
• 입력
  • 입력이 없을 수도 있고, 내부에서 제공될 수도 있지만 반드시 입력 형태가 정의될 수 있는 유한한 입력이어야 한다
• 명확성
  • 실행 주체가 달라져도 같은 의미로 해석되고 같은 결과를 생성해야 한다
• 유한성
  • 종료가 명확하게 정의되어 있어야 한다

 

---

배열

원소들이 같은 자료형의 값과 같은 크기의 기억공간 가짐
물리적 순서와 논리적 순서가 일치
추상화된 의미와 구체화된 의미가 같다

---

스택

 

스택의 순서는 연산에 의해 보호받는다

스택에서 삭제할 때: 값 반환 후 top 감소시킨다 (top--)
스택에 삽입할 때: top 증가 후 삽입한다 (++top)

스택으로 후위 표기식 만드는법
- 새로운 연산자의 우선순위가 스택 top보다 높으면 push
- 스택 top의 우선순위가 새로운 연산자보다 우선순위가 높거나 같다면 pop
- push 가능한 건 top보다 우선순위가 높을 때이므로 계속 비교해서 push 가능할때까지 pop
- 여는 괄호는 무조건 push, 닫는 괄호 나오면 여는 괄pl....56-0]]]]]\\\\호 나올때까지 전부 pop

후위표기식 스택 이용해서 계산하는법
- 피연산자는 push
- 연산자 나오면 스택에 저장된 상위 2개 pop
  (이때 먼저 pop한 것을 op2로 지정하면 op1 (연산자) op2 순서로 만들 수 있음)
- 계산 결과는 다시 스택에 push

---

큐

삽입 연산: [++rear] rear값 더한 후 그 자리에 삽입
삭제 연산: [++front] front값 증가 후 그 자리에 있는 값 반환 (원래 front값이 가장 끝 값보다 이전 값을 가리키고 있는 경우)

원형 큐에서 front, rear 값 관리하는 방법

 

큐의 크기 = n

rear ← (rear + 1) mod n

front ← (front + 1) mod n

 => 예를 들어 원형 큐의 크기가 5면, 인덱스는 0~4이므로 4까지 채워지고 나면 다시 5 % 5 = 0으로 가게 됨

 

 

 

---

연결 리스트

 

리스트의 원소는 논리적인 순서만 따르면 되기 때문에 저장 위치를 연속적으로 메모리에 할당할 필요가 없다

 

 

cf) 리스트를 배열로 구현하기

 

1차원 배열에 저장하면 메모리에 순차적으로 저장돼서 삽입, 삭제에 시간 오래 걸림

대신 포인터 메모리가 필요 없어서 공간적으로는 효율적

 

 

연결 리스트: 포인터를 이용하여 구현하는 리스트

노드 하나는 데이터 필드 + 링크 필드

C에서는 struct 자료형으로 노드를 구현한다.

 

포인터를 이용한 리스트의 구현

포인터는 메모리의 주소값을 저장하는 변수

포인터 변수도 지정할 수 있는 주소값에 대한 데이터 타입을 가져야 한다!

 

int a = 1;
int *b;   // 정수형 포인터 변수, 정수형 변수의 주소값 할당 가능

b = &a; 	// a의 주소값이 b에 저장된다.

// 이때 *b의 값을 출력하면 1이 출력된다. *를 통해 역참조

 

 

malloc(): 프로그램 실행 중에 필요한 만큼의 메모리 공간 추가로 할당

주소값을 반환해주면 그 주소값을 포인터 변수로 받아서 사용한다.

 

#include <stdio.h>
#include <stdlib.h>

int main() {
    int *p_a;
    
    p_a = (int *)malloc(sizeof(int));
    *p_a = 10;
    
    printf("p_a is %d", *p_a);	// a is 10
    
    return 0;
}

 

 

연결 리스트에 삽입하기 

1. 새로운 노드를 만든다

2. 새로운 노드가 삽입될 위치의 다음 노드를 가리키게 한다.

3. 삽입될 위치의 이전 노드가 새로운 노드를 가리키게 한다.

 

특정 노드 뒤에 삽입하기

- 이전 노드가 가리키던 값을 새 노드가 가리키게 한 뒤에 이전 노드의 링크 바꿔야 함

- 순서를 반대로, 이전 코드가 가리키던 값에 새 노드 먼저 넣으면 안됨

 

마지막 노드 삭제하기

- prevNode, delNode를 head 다음과 그 다음으로 놓고

- delNode가 NULL 을 가리킬때까지 찾는다

- 이때 prevNode를 먼저 delNode와 같게 증가시키고, delNode가 가리키는 값을 확인해라.

- 그래야 delNode 반환 후 prevNode가 가리키는 값을 NULL로 바꿀 수 있다.

 

 

---

 

트리

 

트리는 데이터의 계층 관계, 포함 관계 등을 나타내는 자료구조이다.

 

잎 노드: 서브트리를 갖지 않는다.

루트를 제외한 모든 노드의 진입 차수는 1.

진입 차수가 2 이상이면 그래프가 된다.

트리에서 각 노드의 차수는 진출 차수로 정의

트리의 차수는 트리 안 노드의 차수 중 최대 차수

 

전 이진 트리: 모든 노드가 0개 또는 2개의 자식 갖는다.

각 레벨이 허용되는 최대 개수 노드를 가지면 가득 찬(perfect) 이진 트리

루트 레벨이 0이면 높이가 k인 가득 찬 이진 트리의 노드 개수는 2^k - 1

 

전위, 중위, 후위는 루트 노드를 언제 방문하는지에 따라 나뉜다

전위 순회(PLR): 루트 > 왼쪽 서브트리 > 오른쪽 서브트리

중위 순회(LPR): 왼쪽 서브트리에 속한 모든 노드 방문 후 루트 노드 방문

후위 순회(LRP): 왼쪽, 오른쪽 서브트리 다 탐색 후 루트 노드 방문

 

이진 트리에서 노드 삭제하기

 

//지정한 노드를 제거, 제거한 노드(자식 포함)를 반환해서 적절한 조처를 할 수 있게 한다.
//부모를 찾아서 제거
//root는 삭제불가 
node *delete(node *root, node *it, char direction) {
	node *parent = search_parent(root, it);  // 루트 노드인 경우 (parent 찾을 수 없는 경우)
		if (parent == NULL) {
		printf("삭제 불가!\n");
		return NULL;
	} else {
	    if (direction == 'l') {parent->left = NULL; free(parent->left);  return it;}
	    else if (direction == 'r') {parent->right = NULL; free(parent->right); return it;}
	    else return NULL;
	}
}

 

 

스레드 트리

 

스레드: 정해진 순회 방법에 따른 방문 순서를 유지하는 포인터

스레드 트리는 내부에 순회 순서를 유지한다.

 

이진 트리에서 NULL 포인터의 개수는 2n - (n -1) = n + 1개

(루트 노드를 제외한 각 노드는 진입 차수가 1이므로, null이 아닌 포인터는 n-1개. 전체 포인터의 개수는 2n이므로 2n - (n - 1)이 NULL 포인터의 개수이다)

 

---

힙

 

힙: 부분적으로 정렬된 완전 이진 트리

부모 노드가 크면 최대 힙, 부모 노드가 작으면 최소 힙

 

힙은 우선순위 큐의 한 종류

 

우선순위 큐: 삭제 함수를 실행하면 우선순위가 가장 높은 값이 삭제되고(높은 오버플로우), 나머지 데이터들의 저장 순서는 문제가 되지 않는다.

완전 이진 트리여서 기억장소 낭비가 없으므로 배열로 구현 (인덱스를 1부터 쓰면 프로그램이 단순해진다)

 

선택 트리

 

승자 트리: 각 노드가 두 자식 노드 중 작은 값

 

숲: 분리된 트리 모임

아무것도 없는 것도 트리이다 (공집합)

 

어떤 이진 트리에 대한 전위-중위 순회 방문 순서를 이용해서 트리 구조를 유일하게 하나 구할 수 있다.

 

BS 트리: 왼쪽 서브트리의 모든 노드의 키값이 작고, 오른쪽 서브트리의 모든 키값이 더 크다. 

중위 순회 통해 같은 순서 데이터를 만들 수 있는 다양한 모양의 트리

 

Splay 트리: 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치시킨다.

 

AVL 또는 BB 트리는 O(log2n) 개의 노드를 옮기면 된다. (균형 유지 시)

 

 

높이 균형 트리: AVL 트리

- 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이난다.

- 완전히 균형잡힌 트리와 탐색 경로의 길이가 크게 다르지 않다. 

 

---

m원 탐색 트리: 노드가 m개 이하의 가지를 가질 수 있다.

 

B 트리: 인덱스 구조 구현에 가장 일반적으로 사용한다.

 - 루트와 잎 제외 각 노드는 최소 ⌈m/2] 개의 서브트리 갖는다 (내부 노드가 최소한 반은 차 있어야 함

 - 루트는 최소 두 개의 서브트리 가짐

 - 모든 잎 노드는 같은 레벨

 

B* 트리

 - 노드의 2/3 이상이 차야 한다.

 - 모든 잎 노드는 같은 레벨

 

B+ 트리

 - B트리처럼 각 노드의 키값이 적어도 1/2는 차야 함

 - 잎 노드를 순차적으로 연결하는 포인터 집합이 있다.

 - 잎 노드의 마지막 포인터가 다음 키값 갖는 노드를 가리킨다.

 

높이가 h인 2-3트리의 키 개수는 2^h - 1개에서 3^h -1

 

2-3-4 트리

 - lchild-lkey-lmchild-mkey-rmchild-rkey-rchild

 - 모든 잎 노드는 같은 레벨 

 - 2-3 트리보다 삽입과 삭제가 용이

 - 경우에 따라서는 기억장소 낭비 가능

 - 2-3트리와 같은 수의 노드를 더 작은 레벨로 구축할 수 있다.

 

레드 블랙 트리

 - 2-3-4 트리를 이진 트리로 나타낸다

 - 레드: 노드 내에 있던 항복

 - 블랙: 2-3-4 트리의 포인터

 

 

 

출처: 자료구조(강태원, 정광식)