IT, FIRE, License and Daily life

<이진 탐색 트리(Binary Search Tree)>

이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조이다.
[이진 탐색 트리의 정의]

1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.
4. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.

[이진 탐색 트리의 탐색 연산]
1. 루트에서 시작한다.
2. 탐색할 킷값 x를 루트 노드의 킷값과 비교한다.
3. (킷값 = 루트노드의 킷값)인 경우 : 원하는 원소를 찾았으므로 탐색연산 성공
4. (킷값 < 루트노드의 킷값)인 경우 : 루트노드의 왼쪽 서브트리에 대해서 탐색연산 수행
5. (킷값 > 루트노드의 킷값)인 경우 : 루트노드의 오른쪽 서브트리에 대해서 탐색연산 수행
-> 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

[알고리즘]

예) 원소 11 탐색하기
① 찾는 킷값 11을 루트노드의 킷값 8과 비교
(찾는 킷값 11 > 노드의 킷값 8) 이므로 오른쪽 서브트리를 탐색
② (찾는 킷값 11 > 노드의 킷값 10) 이므로, 다시 오른쪽 서브트리를 탐색
③ (찾는 킷값 11 < 노드의 킷값 14) 이므로, 왼쪽 서브트리를 탐색
④ (찾는 킷값 11 = 노드의 킷값 11) 이므로, 탐색 성공! (연산 종료)

[이진 탐색 트리의 삽입 연산]
1. 먼저 탐색 연산을 수행
- 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.
- 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 된다.
2. 탐색 실패한 위치에 원소를 삽입한다.

예) 원소 4 삽입하기
① 찾는 킷값 4를 루트노드의 킷값 8과 비교하여, (찾는 킷값 4 < 노드의 킷값 8) 이므로, 왼쪽 서브트리를 탐색한다.
② (찾는 킷값 4 > 노드의 킷값 3) 이므로, 오른쪽 서브트리를 탐색한다.
③ (찾는 킷값 4 < 노드의 킷값 5) 이므로, 왼쪽 서브트리를 탐색해야하는데 왼쪽 자식노드가 없으므로 탐색 실패!
이때, 탐색 실패가 결정된 위치 즉, 왼쪽 자식노드의 위치가 삽입 위치가 된다.
④ 탐색작업으로 찾은 자리 즉, 노드 5의 왼쪽 자식노드 자리에 노드 4를 삽입한다.

[이진 탐색 트리의 삭제 연산]
1. 먼저 탐색 연산을 수행
2. 탐색하여 찾은 노드를 삭제한다.
3. 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업)가 필요하다. 

−삭제할 노드의 경우

① 삭제할 노드가 단말노드인 경우 : 차수가 0인 경우

② 삭제할 노드가 하나의 자식노드를 가진 경우 : 차수가 1인 경우

노드를 삭제하면, 자식 노드는 트리에서 연결이 끊어져서 고아가 된다.
- 후속 처리 : 이진 탐색 트리의 재구성. 삭제한 부모노드의 자리를 자식노드에게 물려준다.

③ 삭제할 노드가 두개의 자식노드를 가진 경우 : 차수가 2인 경우

Copyrightⓒ2014 By 한빛아카데미(주)

<이진트리(Binary Tree)>

트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리이다. 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 만을 가진다.
- 부모 노드와 자식 노드 수와의 관계 -> 1:2
- 공백 노드도 자식 노드로 취급한다.
0 ≤ 노드의 차수 ≤ 2

[이진트리의 특성]
1. n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.
− 루트를 제외한 (n-1)개의 노드가 부모 노드와 연결되는 한 개의 간선을 가짐

2. 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다.
− 이진 트리의 높이가 h가 되려면 한 레벨에 최소한 한 개의 노드가 있어야 하므로 높이가 h인 이진 트리의 최소 노드의 개수는 (h+1)개
− 하나의 노드는 최대 2개의 자식 노드를 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 2i개 이므로 높이가 h인 이진 트리 전체의 노드 개수는 2^(h+1)-1 개

ex) 높이가 3이면서 최소의 노드를 갖는 이진트리와 최대의 노드를 갖는 이진트리

<포화이진트리(Full Binary Tree)>

<편향 이진 트리(Skewed Binary Tree)>

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리 

왼쪽 편향 이진 트리
−모든 노드가 왼쪽 자식 노드만을 가진 편향 이진 트리
오른쪽 편향 이진 트리

−모든 노드가 오른쪽 자식 노드만을 가진 편향 이진 트리

<연결 자료구조를 이용한 이진트리>

단순 연결 리스트를 사용하여 구현. 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현

[구조체]

typedef struct treeNode {
char data;
struct treeNode *left;
struct treeNode *right;
} treeNode;

[연결 자료구조의 이진트리 그림]

<이진 트리의 순회(traversal)>

계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산이다.
순회를 위해 수행할 수 있는 작업 정의
⑴ 현재 노드를 방문하여 데이터를 읽는 작업 D
⑵ 현재 노드의 왼쪽 서브트리로 이동하는 작업 L
⑶ 현재 노드의 오른쪽 서브트리로 이동하는 작업 R

1. 전위 순회(preorder traversal) : root-left-right
[수행 방법]
① 현재 노드 n을 방문하여 처리한다. : D(루트에서 아래로 내려서 처리)
② 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위 트리 끝까지 처리)
③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(오른쪽 하위 트리 처리)

2. 중위 순회(inorder traversal) : left – root - right
[수행 방법]
① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위 트리를 시작하여)
② 현재 노드 n을 방문하여 처리한다. : D(하위에 걸친 루트까지 거친 후)
③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(오른쪽 하위 트리로 이동)

3. 순회(postorder traversal): left - right - root
[수행 방법]
① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위트리부터 시작후)
② 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(우측 형제노드이동방문후)
③ 현재 노드 n을 방문하여 처리한다. : D(루트 노드까지만이동후, 다시 L)

Copyrightⓒ2014 By 한빛아카데미(주)

<트리(Tree)>
​

원소들 간에 1:多 관계를 가지는 비선형 자료구조이며, 원소들 간에 계층관계를 가지는 계층형 자료구조이다. 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

[트리관계 해설]

① 노드(node) – 트리의 원소
−트리 A의 노드 - A,B,C,D,E,F,G,H,I,J,K,L
② 루트 노드(root node) – 트리의 시작 노드 (루트노드 - A)
③ 간선(edge) – 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
④ 형제 노드(sibling node) – 같은 부모 노드의 자식 노드들 (B,C,D는 형제 노드)
⑤ 조상 노드 – 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 (K의 조상 노드 : F, B, A)
⑥ 서브 트리(subtree) – 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
−각 노드는 자식 노드의 개수 만큼 서브 트리를 가진다.
⑦ 자손 노드 – 서브 트리에 있는 하위 레벨의 노드들 (B의 자손 노드 – E,F,K,L)

⑧ 차수(degree) - 노드의 차수 : 노드에 연결된 자식 노드의 수.
A의 차수=3, B의 차수=2, C의 차수=1, D의 차수=3
⑨ 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
트리 A의 차수=3
⑩ 단말 노드(리프 노드) : 차수가 0인 노드. 자식 노드가 없는 노드

노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
B의 높이=1, F의 높이=2

포리스트(forest) : 서브트리의 집합
−트리A에서 노드 A를 제거하면, A의 자식 노드 B, C, D에 대한 서브 트리가 생기고, 이들의 집합은 포리스트가 된다.

Copyrightⓒ2014 By 한빛아카데미(주)

<덱(Deque)>

큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있다. 스택의 특성과 큐의 특성을 모두 가지고 있다.

덱의 front와 rear의 구조를 보면 다음과 같다.

Copyrightⓒ2014 By 한빛아카데미(주)

<연결 큐(연결리스트 큐)>

[연결 큐 알고리즘]

1. 공백 연결 큐 생성

createLinkedQueue()

   front <- null;

   rear <- null;

end createLinkedQueue()

2. 공백 연결 큐 검사

isEmpty(LQ)

   if(front=null) then return true;

   else return false;

end isEmpty()

3. 연결 큐의 삽입

enQueue(LQ, item)

   new <- getNode();   // ⓐ

   new.data <- item;

   new.link <- null;

   if(front=null) then {  // ⓑ

      rear <- new;

      front <- new;

   }

   else {   // ⓒ

      rear.link <- new;

      rear <- new;

   }

end enQueue()

ⓐ 삽입할 새 도르를 생성하여 데이터 필드에 item을 저장.

ⓑ 새 노드를 삽입하기 전에 연결 큐가 공백인지 아닌지를 검사

ⓒ 큐가 공백이 아닌경우, (노드가 있는 경우) 현재 큐의 마지막 노드의 다음에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정

4. 연결 큐 삭제

deQueue(LQ)

   if(isEmpty(LQ)) then Queue_Empty();

   else {

      old <- front;          // ①

      item <- front.data;

      front <- front.link;   // ②

      if (isEmpty(LQ)) then rear <- null;  // ③

      returnNode(old);     // ④

      return item;

}

end deQueue()

​

​①  old <- front;

front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정한다.

② front <- front.link;

삭제연산 후에는 현재 front 노드의 다음 노드가 front 노드(첫번째 노드)가 되어야 하므로, 포인터 front를 재설정한다.​ 

③ if (isEmpty(LQ)) then rear <- null;

현재 큐에 노드가 하나뿐이어서 삭제연산 후에 공백 큐가 되는 경우 큐의 마지막 노드가 없어지므로 포인터 rear를 null로 설정한다.​

④ ​returnNode(old);

포인터 old가 가리키고 있는 노드를 삭제하고, 메모리 공간을 시스템에 반환한다​

삭제만 하는 연산

/*

delete(LQ)

   if(isEmpty(LQ) then Queue_Empty();

   else {

      old <- front;

      front <- front.link;

      if(isEmpty(old)) then rear <- null;

      returnNode(old);

   }

end delete()

*/

5. 연결 큐의 검색

peek(LQ)

   if(isEmpty(LQ)) then Queue_Empty()

   else return (front.data);

end peek()

​

​

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<원형 큐>

1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하고 사용.

초기 공백 상태 : front = rear = 0
front와 rear의 위치가 배열의 마지막 인덱스 n-1에서 논리적인 다음 자리인 인덱스 0번으로 이동하기 위해서 나머지연산자 mod를 사용한다.
3 ÷ 4 = 0 …3 (몫=0, 나머지=3)
3 mod 4 = 3

[원형 큐 알고리즘]

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<큐(Queue)>

스택과 마찬가지로 삽입과 삭제의 위치가 제한되어있는 유한 순서 리스트이다. 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조로 되어 있다.
선입선출 구조 (FIFO, First-In-First-Out) : 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)된다.

2개의 포인터를 가지고 한쪽 끝에서 삽입이 발생되고 다른 한쪽 끝에서 삭제가 일어나는 순차적 구조이다. 뒤(rear)에서 노드가 삽입되고 앞(front)에서 삭제가 일어나도록 제한된다.

[적용분야] -> 정보처리 산업기사/기사 문제에도 나옴
컴퓨터 운영체제 작업 스케쥴링(job scheduling)이나 시분할 방식에 많이 사용되고, 키보드를 사용한 컴퓨터로의 입력이나 모니터, 프린트기를 사용한 출력에 사용된다.

큐의 연산은 enQueue와 deQueue로 한다.

enQueue : 삽입연산, (스택으로 비교하자면 push를 말함)

deQueue : 삭제연산 (스택으로 비교하자면 pop을 말함)

[큐 알고리즘 풀이]

<1차원 배열을 이용한 큐>

큐의 크기 = 배열의 크기
- 변수 front : 저장된 첫 번째 원소의 인덱스 저장
- 변수 rear : 저장된 마지막 원소의 인덱스 저장
- 초기 상태 : front = rear = -1 공백 큐 생성
- 공백 상태 : front = rear
- 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

[코드]

<전위 표기법(prefix notation)>

연산자를 피연산자를 앞에 표기하는 방법
예) +AB

중위 표기를 전위 표기법으로 바꿔보자.

① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

② 각 연산자를 그에 대응하는 왼쪽괄호의 앞으로 이동시킨다.

③ 괄호를 제거한다.​

<중위 표기법(infix notation)>

연산자를 피연산자의 가운데 표기하는 방법
예) A+B

<후위 표기법(postfix notation)>

연산자를 피연산자 뒤에 표기하는 방법

예) AB+

중위 표기를 후위 표기법으로 바꿔보자.

① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
② 각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다.
③ 괄호를 제거한다.

<스택을 사용한 후위표기식으로 변환>

⑴ 왼쪽괄호를 만나면 무시하고 다음 문자를 읽는다.
⑵ 피연산자를 만나면 출력한다.
⑶ 연산자를 만나면 스택에 push한다.
⑷ 오른쪽괄호를 만나면 스택을 pop하여 출력한다.
⑸ 수식이 끝나면, 스택이 공백이 될 때까지 pop하여 출력한다.

[코드]

<역순 문자열>

스택의 후입선출(LIFO) 성질을 이용한다.

​
① 문자열을 순서대로 스택에 push 하기

② 스택을 pop하여 문자열로 저장하기

<수식의 괄호의 쌍 검사>

수식에 포함되어있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어있으므로, 후입선출 구조의 스택을 이용하여 괄호를 검사한다.
수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호를 검사.

[방법]

① 왼쪽 괄호를 만나면 스택에 push
② 오른쪽 괄호를 만나면 스택을 pop, 마지막에 저장한 괄호와 같은 종류인지를 확인
- 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식임.

※ 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 됨
•수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식임.

[수식의 괄호의 쌍 검사 코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<스택(Stack)>

접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조

스택에 저장된 원소는 top(맨 위)으로 정한 곳에서만 접근 가능

- top 위치에서만 원소를 삽입하므로, 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 LIFO(Last In First Out)구조이다.

[스택 실생활 활용 예]

1. 연탄 쌓기

연탄을 하나씩 쌓으면서 아궁이에 넣는다. 마지막에 넣은 연탄이 가장 위에 있게 된다.

꺼낼때는 위에서부터 하나씩 꺼내야 한다. 마짐가에 넣은 연탄을 가장 먼저 꺼낸다.

[Push 알고리즘]

[배열 구조]

① 공백 스택 생성 : createStack(S);

② 원소 A 삽입 : push(S, A);

③ 원소 B 삽입 : push(S, B);

④ 원소 C 삽입 : push(S, C); 

⑤ 원소 삭제 : pop(S);

[연결리스트를 이용한 스택의 코드]

Copyrightⓒ2014 By 한빛아카데미(주)