장난감

트리. Tree

자료구조에서 트리는 나무를 거꾸로 표현한 것 처럼 생겼다고 해서 트리라고 이름이 지어졌다.

트리는 뿌리(root)인 노드를 Level 1로 지칭하며 시작하며 뿌리 노드를 기준으로

자식 노드를 연결시켜 가지처럼 뻗어나가는 구조이다.

트리는 여러가지 종류가 있는데 대표적으로 Binary Tree, Normal Tree가 있다.

여기서 Binary Tree는 탐색, 힙 등 광범위하게 사용된다.

배우기 전에 용어를 정리해보자.

Root, 뿌리.

뿌리(Root)는 트리의 최상위에 존재하는 노드이며 Level은 1로 고정이다.

위 Tree에서 시초가 되는 '2'노드가 Root, 뿌리 노드이다.

(위 그림에서 '2'노드가 두번 나오는데, 가장 상위에 있는게 뿌리 노드이다.)

Child, 자식

Child, 자식노드는 어떠한 노드에 종속되어 있는 노드로

뿌리 노드를 기준으로 자식노드는 '7', '5'노드이다.

Parant, 부모

Parant, 부모노드는 자기 자신 노드 아래에 자식 노드가 있다면

해당 노드는 부모 노드가 된다.

예를 들어 '9' 노드의 부모는 '5'이다.

* 같은 부모를 가진 노드의 집합을 형제 노드라고도 칭한다.

Degree, 차수

Degree, 차수는 해당 노드에 연결된 자식 노드의 개수를 뜻한다.

트리에서 가장 큰 차수가 트리의 차수가 된다.

Level(Depth), 깊이, 레벨

Level, 혹은 Depth은 트리의 깊이 혹은 레벨을 뜻 한다.

위 그림에서는 최대 4 Level 혹은 4 Depth을 가지고 있다. 

트리의 최상 지점부터 1Level, 1 Depth으로 시작한다.

Height, 높이

트리에서 최대 Level 혹은 Depth을 의미한다.

해당 트리는 4의 높이를 가진다.

Stack과 Queue는 자료구조를 공부 했다면 100% 이해를 하고 넘어가야한다.

스케줄링, 알고리즘 등 많은 곳에서 쓰이는데 일단 개념부터 살펴보자.

Stack과 Queue는 뭘까?

두 자료구조 모두 데이터가 쌓이는 방식, 혹은 구조를 뜻한다.

역시나 글로는 이해가 잘 안될 것 같아 아래에 각각에 대한 설명과 사진을 첨부 했다.

1. Stack, 스택

Stack. 채우다. 쌓다 라는 뜻을 가진 단어이다.

자료구조에서도 마찬가지로 데이터를 순차적으로 쌓아준다.

또한 데이터를 빼낼 때는 마지막에 들어온 데이터부터 내보낸다.

즉, 후입선출( 혹은 선입후출 )의 구조를 지니게 된다.

쌓는 과정을 push, 빼내는 과정을 pop이라고 한다.

단점을 살펴보자면 Low level(먼저 들어온 데이터)의 데이터를 가져가려고 하면 

위에 존재하는 High level(나중에 들어온 데이터)의 데이터를 다 빼야지 가져갈 수 있다.

또한 스택의 크기를 동적으로 변경하지 않는 한 Overflow( 데이터가 들어갈 공간이 모자른 현상 )이 일어날 수 있다.

2. Queue, 큐

앞에서 봤던 Stack은 출구와 입구가 같다면, Queue는 출구와 입구가 별도이다.

따라서 들어왔던 것은 입구로 나가지 못하므로 늦게 들어오면 늦게 들어올 수록 나가는 속도는 늦어진다.

즉, 선입선출( 혹은 후입후출 )의 구조를 가지게 된다.

데이터를 넣는 것을 Enqueue, 데이터를 제거하는 것을 Dequeue라고 한다. ( 책마다 다를 수 있다. )

단점을 찾아보자면

Queue는 Dequeue를 실행하면 데이터를 당겨와야한다.

1->2->3->4 순으로 데이터가 들어왔다고 하면 Queue의 상태는 아래와 같다.

rear [4]-[3]-[2]-[1] front

이 때 Dequeue를 실행한다면 아래와 같이 변경 된다.

rear [4]-[3]-[2]-[null] front

만약 재배치를 해주지 않는다면 Dequeue를 충분히 많이 실행 했을 시

Enqueue를 하면 Overflow가 나타나게 된다.

rear [4]-[null]-[null]-[null] front

위와 같은 Queue가 구성되면 rear쪽이 비어있지 않다고 판단하여 Overflow를 내뱉는다.

실제로는 3 size나 비어있는데도.

따라서 재배치가 필요하다.

위와 같은 queue를 선형 큐라고 하고, 이 단점을 보완한 것이 원형 큐, 환영 큐 라는 것이다.

남는 메모리 공간을 없애기 위해서 rear과 front를 가르키는 변수를 추가해서 활용도를 높이는 방식인데, 

단점이라면 10 size를 가진 원형 Queue는 실제로 11 size을 지녀야되서 1 size가 낭비된다. ( full 과 empty를 구분하기 위한 공간 )

1size는 mod연산을 하면서 남는 공간이라고 생각하면 된다.

큐가 꽉 차있는 것을 판별하려면 

(rear+1) % Queue_Size == front 를 이용하면 된다.

원형 큐에 대한 내용은 따로 포스팅 해야겠다.

여기 가면 설명이 잘 되있으므로 참고해도 좋을 듯 하다.

사진 출처 : 나무위키(큐)

정리를 하기 위해 포스팅을 한다.

Linked List에서는 크게 3가지 유형이 존재한다.

1.  Single

2. Double

3. Circle

첫 번째로 Single Linked List

n번 째 블럭이 n+1번 째 블럭을 찾을 수 있는 Link를 가지고 있는 Node의 집합체이다.

Single인 이유는 n+1번 째 블럭은 n 번 째 블럭을 찾을 수 있는 Link가 없기 때문이다.

네트워크로 따지면 단방향이라고 볼 수 있다.

두 번째로 Double Linked List

Signle과 다른 점은 n 번 째 블럭은 이웃한 블럭을 찾을 수 있는 Link를 지니고 있다.

네트워크로 따지면 양방향이다.

세 번째로 Circle Linked List

앞에서 본 Single, Double은 모두 Head와 Tail이 존재한다.(시작과 끝)

하지만 Circle Linked List는 Head와 Tail이 연결 되어있는 순환구조이다.

사진 출처 : https://ko.wikipedia.org/wiki/연결_리스트