※ 이 글은 본인이 이해한 것을 저장용으로 정리한 것으로 오류가 있을 수도 있습니다.

[포인터 정리] 2차원 구조체포인터를 함수에 인자로 전달 / 링크드리스트 / 해시테이블

링크드리스트(linked list)로 해쉬 테이블(Hash Table) 만들기

이러한 링크드리스트(Linked List)를 만든다고 하자 ( 해시테이블(Hash Table)을 만들때 주로 사용되는 형태이다)

예시를 보자(편의를 위해 불필요한 부분은 생략하였다)

typedef struct linkedlist* lptr;

typedef struct linkedlist{

int value;

lptr next;

}linkedlist;

int main(){

lptr* hashtable;

hashtable = (lptr*)malloc(sizeof(lptr)*20);

for(int i=0;i<20;i++)

hashtable[i] = NULL;

}

위의 세팅을 기본으로 하고 함수에 인자를 넘기면 경우마다 어떻게 되는지 정리해보겠다.

(Push하는 함수를 linkedlist_push라고 하자

1. linkedlist_push( hashtable[index], value);

2. linkedlist_push( &(hashtable[index]), value);

내가 가장 헷갈렸던 것이 위의 두 경우인데 비슷하면서 매우 다르다.

void linkedlist_push([자료형 미정] head, int value)

라는 함수에서 만약 head가 NULL인지 확인을 하고 NULL일 경우 세팅을 해주려면 2번을 사용하여야한다(head의 값을 바꾸려면!).

이유는 어떻게 보면 매우 단순한데 우리가 

int a = 5;

random_function(a);

random_function(&a);

위처럼 단순한 int값을 넘길때와 같다. a를 넘기면 그 값이 넘어가지만 그 값을 변경해봐야 그 함수의 지역변수를 바꾸는 것으로 함수를 벗어나면 의미가 없어진다. 우리가 의도하는 대로 a의 값을 바꾸려면 주소값을 넘겨서 변경하여야한다.

위의 예제도 같다.

아래의 그림을 참고하자

1번의 경우 hashtable이라는 배열의 한 칸의 주소값을 넘겨준다. 따라서 *head = (lptr)malloc(sizeof(linkedlist))로 바꾸면 적용이된다.

하지만 2번의 경우 lptr형식이긴 하지만 int a를 넘긴것 처럼 내용물을 넘긴것으로 head = (lptr)malloc(sizeof(linkedlist))를 하여도 head라는 지역변수에 저장되어 함수를 벗어나면 찾을 수 없다.

헷갈릴수도 있는 부분이 만약 첫 칸이 무조건 있다고 가정을 하고 연결되는 다음칸을 추가하는 것이라면 2방법 둘다 가능하다. head의 노드의 주소값을 통하여 next를 접근하든, 내용물의 next를 접근하든 같은 주소를 접근하기 때문이다.

즉, head의 값을 직접적으로 바꾸는 것이 아니라면 상관이 없다.

트리는 1개 이상의 노드로 이루어진 유한집합으로서,

1) 노드 중에는 루트(root)라는 노드가 하나 있고,

2) 나머지 노드들은 n(>=0)개의 분리 집합 T1,T2, ... , Tn으로 분할될 수 있다.

차수(Degree): 한 노드의 서브트리의 수

- Leaf/Terminal Node: 차수가 0인 노드

- Sibling Node: 같은 부모노드를 가진 노드들

- Degree of a tree: 트리에 있는 노드의 최대 차수

- Ancestor: 루트에서부터 그 노드까지 경로상의 모든 노드

위의 그림의 예시로 들어보겠다.

1) Leaf/Terminal Nodes: K, L, F, G, M, I, J

2) Sibling Nodes: (K & L) , (F & G & H), (B & C & D) 등

3) Degree of the tree: 3 (C의 차수가 최대인 3이다)

4) M의 Ancestor: H, C, A

이진트리는 공백이거나 루트와 왼쪽 서브트리, 오른쪽 서브트리라고 하는 2개의 분리된 이진트리로 구성된 노드의 유한집합이다.

이진트리는 일반적인 트리와의 차이점을 비교하는 것으로 설명하도록 하겠다.

이진트리의 성질

1) 이진트리의 레벨 i에서의 최대 노드의 수는 2^(i-1)  (i>=1)이다.

2) 깊이가 k인 이진트리의 최대 노드 수는 2^k - 1    (k>=1)이다.

3) 공백이 아닌 모든 이진트리에서 리프 노드 수 = 차수가 2인 노드의 수 + 1 이다.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

typedef struct stack* sptr;

typedef struct stack {

char data;

sptr low;

sptr high;

}stack;

sptr top;

int sCnt=0;

void push(char n)

{

sptr temp;

temp = (sptr)malloc(sizeof(stack));

if (sCnt == 0)

{

top->data = n;

top->low = NULL;

top->high = NULL;

sCnt++;

}

else if (sCnt >= 1)

{

temp->data = n;

temp->low = top;

temp->high = NULL;

top->high = temp;

top = temp;

sCnt++;

}

}

void pop()

{

sptr temp;

if (sCnt == 0)

{

printf("Nothing Inside! \n");

return;

}

else if (sCnt == 1)

{

sCnt = 0;

return;

}

else

{

temp = top;

top = top->low;

free(temp);

sCnt--;

}

}

void print()

{

int i;

sptr temp;

temp = top;

printf("sCnt: %d\n",sCnt);

for (i = 0; i < sCnt; i++)

{

printf("%c\n",temp->data);

if(i+1 < sCnt)

temp=temp->low;

}

}

완전 이진트리(Complete Binary Tree)는 규칙적으로 모든 노드가 순차적으로 2개의 지식 노드를 갖는다. 따라서, 배열은 사용할 경우 배열의 모든 칸이 낭비없이 가득 차게 되어 구현하기 편한 배열을 주로 사용한다. 하지만 연결리스트(Linked List)를 사용해서 구현하려면 어떻게 해야할까? 생각보다 복잡하지 않다. 이 글에서는 방법만을 설명하도록 하겠다.

- 완전이진트리란?

완전이진트리를 구성함에 있어 가장 걸림돌이 되는 부분은 새로 노드를 삽입해야 할 때, 이를 "어디에" 삽입해야 될 지를 모른다는 것이다. 여러가지 방법이 있지만, 필자가 소개하는 방법은 큐(Queue)를 사용하는 방법이다.

바로 방법을 소개하도록 하겠다.

그림으로 보면 이해가 더 빠르게 될 것이다 (A, B, C, D를 삽입하는 경우)

위의 그림을 보면 노드를 삽입해야 되는 노드는 Queue의 front에 항상 위치하게 된다. 이는 모든 노드가 Queue에 삽입되고, 2개의 자식 노드를 가지게 되면 Queue에서 삭제되기 때문에, 완전 이진트리 생성에 필요한 순서대로 Queue의 front에 위치하게 된다.

- 이진트리란?

이진트리의 한 종류인 완전 이진트리는 그림으로 보면 쉽게 이해됩니다.

위의 그림은 완전이진트리(Complete Binary Tree)인 트리들이고, 밑의 그림은 아닌 트리들입니다. 차이가 느껴지시나요?

완전 이진트리들은 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리입니다. 완전이진트리가 아닌 트리들을 보시면 왼쪽이 비어있는데 오른쪽부터 들어가 있죠? 이런 트리들은 완전 이진트리가 아닙니다.

From  https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진 트리

위키백과, 우리 모두의 백과사전.

크기가 9이고, 높이가 3인 이진 트리

이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰인다.

목차

  [숨기기] 

• 1정의
• 2종류
• 3특징
• 4이진 트리 탐색
• 5표현 방법

정의[편집]

• 방향 간선(directed edge)은 부모에서 자식으로 가는 경로를 가리킨다. (그림의 화살표 부분)
• 루트 노드(root node)는 부모가 없는 노드이다. 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node)는 자식이 없는 노드이다.
• 각 노드의 깊이(depth)는 루트 노드에서 자신까지 가는 경로의 길이이다. 트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부르기도 한다. 루트 노드의 깊이는 0이다.
• 트리의 높이(height)는 루트 노드에서 가장 깊이 있는 노드까지 가는 경로의 길이이다. 루트 노드만 있는 트리의 높이는 0이다.
• 형제(sibling)은 같은 부모를 가지는 노드이다.
• p에서 q까지 가는 경로가 존재할 때, p가 q보다 루트에 가까운 노드라면 p를 q의 조상(ancestor)이라 하고 q를 p의 자손(descendent)이라 한다.
• 노드의 크기(size)는 자신을 포함한 모든 자손 노드의 개수이다.
• 노드의 진입차수(In-degree)는 노드에 들어오는 모든 간선의 수이다.
• 노드의 진출차수(Out-degree)는 노드에서 나가는 모든 간선의 수이다.

종류[편집]

• 루트를 가진 이진 트리(rooted binary tree)는 모든 노드의 자식이 최대 2개인 루트를 가진 트리(rooted tree)이다.
• 정 이진 트리(full binary tree)는 단말 노드가 아닌 모든 노드가 2개의 자식을 가진 트리이다.
• 포화 이진 트리(perfect binary tree)는 모든 단말 노드의 깊이가 같은 정 이진 트리이다.
• 완전 이진 트리(complete binary tree)는 끝 부분(마지막 레벨)을 제외하고 모든 노드가 채워진(마지막 레벨을 제외하고는 모든 노드가 자식노드를 2개를 가진) 이진 트리. 마지막 레벨의 노드들은 왼쪽으로 채워져 있다. 마지막 레벨이 다 채워질 수도 있다.
• 무한 완전 이진 트리(infinite complete binary tree)는 레벨이 ${\displaystyle \aleph _{0}}$인 이진 트리에서, 각각의 레벨 d에 존재하는 모든 노드의 수가 ${\displaystyle 2^{d}}$인 트리이다. 모든 노드 집합의 기수는 ${\displaystyle \aleph _{0}}$이다. 모든 경로 집합의 기수는 ${\displaystyle 2^{\aleph _{0}}}$이다.
• 균형 이진 트리(balanced binary tree)는 모든 단말 노드의 깊이 차이가 많아야 1인 트리이다. 균형 이진 트리는 예측 가능한 깊이(predictable depth)를 가진다. 균형 트리의 노드의 개수를 n이라고 하면 깊이는 ${\displaystyle \lfloor log_{2}n\rfloor }$과 같다.
• 변질 트리(degenerate tree)는 각각의 부모 노드가 하나의 자식만을 갖는 트리이다. 이는 성능 측정에서, 트리가 연결 리스트와 같이 움직인다는 것을 의미한다.

특징[편집]

트리의 높이를 h라고, 트리에 존재하는 모든 단말 노드의 개수를 L이라고 할 때,

• 포화 이진 트리의 노드의 개수는 ${\displaystyle 2^{h+1}-1}$이다.
• 완전 이진 트리의 노드의 개수는 ${\displaystyle 2^{h}}$에서 ${\displaystyle 2^{h+1}-1}$ 사이의 값을 가진다.
• 포화 이진 트리의 노드의 개수는 또한 ${\displaystyle 2L-1}$로 나타낼 수 있다.
• 포화 이진 트리의 단말 노드의 개수는 ${\displaystyle 2^{h}}$이다.

이진 트리 탐색[편집]

 이 부분의 본문은 트리 순회입니다.

이진 트리의 모든 노드를 방문하는 것 혹은 방문하여 어떤 작업을 하는 것을 이진 트리 탐색이라고 한다. 이진 트리 탐색의 방법에는 여러 가지가 있으며, 다음의 방법들이 유명하다.

1. in-order : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문한다.
2. pre-order : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다.
3. post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다.
4. level-order : 내 노드, 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, ... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

표현 방법[편집]

이진 트리를 표현하는데는 크게 두 가지 방법이 있다.

• 1차원 배열 표현

이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법이다.

1. 장점 : 노드의 위치를 색인에 의하여 쉽게 접근할 수 있다.
2. 단점 : 특정 트리에서 기억 공간의 낭비가 심할 수 있다.

• 연결리스트 표현

왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법이다.

1. 장점 : 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
2. 단점 : 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.