🖥 Computer Science/자료구조

이진트리는 배열과 Node를 사용하여 표현할 수 있습니다. 우선 배열을 사용한 표현방법부터 알아보겠습니다. 배열을 사용한 이진트리의 표현 배열을 사용하여 이진트리를 구현한 모습은 다음과 같습니다. 조금 살펴보면 특징이 보이실텐데 노드의 번호와 배열의 인덱스에 어떠한 관계가 존재합니다. 노드 번호와 배열 인덱스의 관계 배열의 첫 인덱스인 0은 사용하지 않고, 루트 노드의 인덱스를 1로 설정하겠습니다. 이러한 경우 배열의 인덱스가 i인 노드 N에 대하여 다음 관계가 성립합니다. N의 부모 노드의 인덱스는 [N/2] 입니다. (i가 1인 경우 루트 노드이므로 부모노드는 존재하지 않습니다.) N의 왼쪽 자식은 2 x i에 존재합니다. (2 x i가 노드의 개수보다 크다면 왼쪽 자식이 존재하지 않습니다.) N의 ..

트리의 탐색(순회) 트리를 탐색하는 방법으로는 다음과 같이 4가지 방법이 있습니다. 1. 중위 탐색 (Inorder traversal) 2. 전위 탐색 (Preorder traversal) 3. 후위 탐색 (Postorder traversal) 4. 레벨 순서 탐색 (Level order traversal) 이때 전위, 중위, 후위 탐색의 기준은 루트(Root)노드 입니다. 중위 탐색(Inorder Traversal) 다음과 같은 순서로 탐색합니다. 1. 왼쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다. 2. 루트를 방문합니다. 3. 오른쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다. 즉 루트가 탐색 순서의 중간에 위치합니다. 전위 탐색(Preorder Traversal)..

이진트리 (Binary Tree) 이진트리는 다음과 같이 정의됩니다. 비어있거나(노드가 0개), 혹은 루트(Root)와 두개의 서로 겹치지 않는 이진 트리로 구성되며, 각각 왼쪽 서브트리(left subtree)와 오른쪽 서브트리(right subtree)라 합니다. 이론적인 측면에서 노드가 없는 경우 트리는 노드가 하나 이상 존재해야 하므로 트리가 아니지만, 이진트리는 비어있을 수 있으므로 이진트리는 맞습니다. 이진트리는 다음과 같이 생겼습니다. 트리와 이진트리의 차이점 1. 노드의 최소 개수 트리는 노드가 하나 이상이어야 하지만 이진트리는 노드가 0개여도 됩니다. 2. 서브트리의 순서 트리의 서브트리에는 순서도, 위치도 존재하지 않습니다. 이진트리의 서브트리에는 위치와 순서가 있습니다. 예를 들어 다..

트리의 표현 트리에는 여러 종류가 있으나, 트리의 종류에 상관없이 모든 트리를 표현할 수 있는 두가지 방법에 대해서 알아보겠습니다. 리스트를 이용한 표현 가변길이의 리스트를 이용하여 트리를 표현할 수 있습니다. 자바로는 다음과 같습니다. public class ListTree { private E element; private List subTrees; } Left Child - Right Sibling (왼쪽 자식 - 오른쪽 형제) 표현 노드의 왼쪽에는 자식 노드, 트리의 오른쪽에서는 형제 노드를 가지게 함으로써, 고정 길이의 노드를 통해 표현 가능합니다. public class TreeNode { private E element; private TreeNode leftChild; private Tre..

트리의 정의와 트리에서 사용되는 용어들을 알아보도록 하겠습니다. 트리(Tree) 트리는 나무의 가지와 같은 형태의 자료구조입니다. 트리는 노드(Node)로 구성되는 유한집합으로, 다음의 조건을 만족해야 합니다. 1. 루트라 불리는 특별한 노드가 하나 존재합니다. 2. 루트가 아닌 나머지 노드들은 n개의 노드가 서로 중복되지 않는(disjoint) 집합 T1, ..., Tn으로 나누어지며, 각각의 노드 집합은 다시 트리입니다. 이때 이러한 트리를 루트의 서브트리(subtree)라 정의합니다. 위와 같이 루트 노드로부터 연결된 다른 노드들은 다시 각각이 트리가 되며, 이는 재귀적으로 계속됩니다. 트리의 용어 노드 (Node) 원소(element)와 다른 노드로의 간선(혹은 가지 - egde, branch)으..

배열로 구현한 Queue의 문제점 Queue는 배열로 구현하였을 때, 삽입과 삭제를 여러번 진행할 경우 배열의 위치가 점점 오른쪽으로 이동하게 됩니다. 즉 이렇게 구현하게 된다면, 붉게 표시된 배열의 빈 공간은 사용되지 않지만 메모리를 계속 차지함으로, 메모리 낭비를 발생시킵니다. 이를 해결하기 위한 방법으로 Circular Queue를 사용합니다. Circular Array Queue 기존의 Queue와 대부분 비슷하지만, 배열의 끝이 배열의 처음과 붙어 있는 것으로 생각합니다. 즉 다음과 같은 반지 형태를 생각하시면 이해하기 좋습니다. Circular Queue의 삽입과 삭제 즉 위와 같이 Circular Queue를 사용하면 배열의 모든 공간을 효율적으로 사용할 수 있습니다. 배열로 구현한 Circ..

큐(Queue) Queue 라는 단어는 대기줄 혹은 줄을 서서 기다리다 라는 의미의 단어로 단어의 뜻인 줄에 대해 생각해 보면 먼저 줄을 선 사람이 먼저 서비스를 받습니다. 마찬가지로 Queue에서도 먼저 들어온 자료가 먼저 빠져나가는 선입선출(First In First Out)이라는 특성을 가집니다. Offer과 Poll 대신 Enqueue와 Dequeue 등으로도 표현됩니다. 큐의 특징 정해진 한 곳을 통해서 삽입과 삭제가 이루어지는 스택과는 달리 큐의 삽입과 삭제는 양 끝에서 이루어집니다. 새로운 원소의 삽입은 항상 큐의 뒤쪽에서, 원소의 삭제는 큐의 앞쪽에서 이루어지며 프론트와 리어라는 용어를 다음과 같이 정의합니다. 프론트(front) : 큐의 삭제연산이 이루어지는 곳 리어(rear) : 큐의 ..

스택(Stack) Stack이라는 단어는 더미 혹은 쌓다 라는 의미의 단어로, 단어의 뜻 그대로 데이터를 쌓아 올린 형태의 자료구조입니다. 프링글스 통을 생각하면 편한데, 프링글스 통 안에 들어있는 과자들은 차곡차곡 쌓여있으며 과자를 집어먹을 때 맨 위에서부터 집어먹게 됩니다. Stack에서도 마찬가지로 맨 위에 들어있는, 즉 가장 마지막에 들어온 자료가 가장 먼저 빠져나가는 후입선출(Last In First Out, LIFO)이라는 특성을 가집니다. 스택의 특징 스택은 자료를 정해진 방향으로만 쌓을 수 있고 Top으로 정한 곳을 통해서만 스택의 삽입과 삭제가 이루어집니다. 즉 스택은 입구와 출구가 단 하나입니다. 스택의 사용 사례 웹 브라우저의 방문 History 관리 후위 표기법 계산 컴파일러와 인터..