이진 탐색 트리 (Binary Search Tree)란? 이진 탐색 트리는 이진 트리에서 탐색(Search)란 단어가 들어가 있다. 탐색이 뜻하는 바와 같이 이진 트리에서 '자료의 검색'이 주된 기능이 된다. 이진 탐색 트리는 효율적인 자료 검색을 목적으로 기존 이진 트리에 몇 가지 제약 사항을 추가한 트리이다. 위 설명만 보면 앞서 설명 했던 힙(Heap)과 비슷하다. 힙 또한 이진 트리에서 최댓값 또는 최솟값을 빠르게 반환하도록 이진트리에서 몇가지 제약 사항을 추가했기 때문이다. 이진 탐색 트리는 힙과는 다르게 특정 값에 해당하는 노드를 빠르고 효율적으로 찾는 것을 목적으로 한다. 이진 탐색 트리는 다음 특성을 만족해야 한다. 1. 트리의 모든 노드는 유일한 값을 가진다. 2. 왼쪽 서브트리에 있는 ..

이글은 이전글과 이어집니다. dsbook.tistory.com/255 C로 만드는 자료구조- 힙(Heap)이란? 힙 (Heap)이란? 힙은 이진 트리의 하나이다. 힙의 특징은 루트 노드가 언제나 그 트리의 최댓값 또는 최솟값을 가지는 것이다. 힙의 루트 노드가 최댓값을 가지면 최대 힙, 최솟값을 가지면 최소 dsbook.tistory.com 위 글에서는 힙이란 무엇인지, 힙의 추상 자료형과 그 중 핵심인 삽입과 삭제 연산에 대해 다루었다. 이제는 실제로 코드 구현은 해볼려고 한다. 이글에서는 배열을 이용해 구현하려고 한다. 배열을 이용한 이진 트리 이진 트리는 자식 노드가 최대 2개 이기 때문에 규칙을 만들어 배열의 인덱스를 이용하여 부모,자식 노드간의 관계를 나타낼 수 있다. 규칙은 다음과 같다.( 편..

힙 (Heap)이란? 힙은 이진 트리의 하나이다. 힙의 특징은 루트 노드가 언제나 그 트리의 최댓값 또는 최솟값을 가지는 것이다. 힙의 루트 노드가 최댓값을 가지면 최대 힙, 최솟값을 가지면 최소 힙이라고 한다. 최대 힙은 모든 부모 노드가 자식 노드보다 큰 값을 가지느 최대 트리의 특성을 가지고 있고 최소 힙은 모든 부모 노드가 자식 노드 보다 작은 값을 가지는 최소 트리의 특징을 가지고 있다. 마지막으로 힙은 항상 완전 이진 트리이다. 힙이 되기 위한 조건을 정리하면 아래와 같다. 1. 완전 이진 트리여야 한다. 2. 최대 트리 혹은 최소 트리의 특징을 가진다. 아래는 최대 힙과 최소 힙의 예시이다. 두 개의 이진 트리 모두 완전 이진 트리이며 최대 힙은 모든 부모 노드가 자식 노드의 값보다 크기 때..

이전글에서 이진 트리의 순환을 다루었다. dsbook.tistory.com/245(이전 글) C로 만드는 자료구조- 이진 트리의 순회 트리의 순회란? 트리의 순회란 트리의 모든 모드를 한 번씩 방문 하는 것을 의미한다. 트리를 사용하면서 트리의 내용을 출력하거나 트리에서 원하는 노드를 찾고자 한다면 트리의 노드를 한 dsbook.tistory.com 이번 글에서는 이진 트리의 함수들을 다루고자 한다. 1) 복사 2) 동일성 검사 3) 노드 개수 구하기 4) 단말 노드 구하기 5) 이진 트리의 높이 구하기 위 함수들은 이진 트리의 구조와 순환 알고리즘들을 정확하게 이해하고 있다면 별다른 어려움 없이 구현이 가능하다. 이때 중요한점은 각 전위 순환, 중위 순환 ,후위 순환 알고리즘 중에서 함수에 적합한 순환..

트리의 순회란? 트리의 순회란 트리의 모든 모드를 한 번씩 방문 하는 것을 의미한다. 트리를 사용하면서 트리의 내용을 출력하거나 트리에서 원하는 노드를 찾고자 한다면 트리의 노드를 한 번씩 방문해야 한다. 근데 트리는 리스트,스택,큐와 같은 선형 자료구조가 아니라 계층 구조이기 때문에 순회 알고리즘을 잘 이해해야 하고 알고리즘에 방향성에 따라 다양한 순회 방법이 가능하다. 트리의 다양한 함수,알고리즘들은 기본으로 순회를 기반으로 하기 때문에 순회 알고리즘을 이해하고 사용용도에 따른 순회 알고리즘을 선택하는 것이 중요하다. 이진 트리의 순회 이 글에서 다루는 것은 이진 트리의 순회를 다룰 것이다. 이진 트리는 최대 차수가 2이기 때문에 구성요소를 크게 3가지로 (L: 왼쪽 서브트리 R: 오른쪽 서브트리 V..

이진트리 (Binary Tree)란? 이진트리는 모든 노드의 차수가 2 이하인 트리를 말한다. 다시 말해 하나의 노드가 가질 수 있는 자식 노드는 최대 2개라는 뜻이다. 이진트리의 종류 이진트리는 형태에 따라 3가지로 분류할 수 있다. 1) 포화 이진 트리(Full Binary Tree) 포화 이진 트리는 모든 레벨의 노드가 가득 차 있는 이진트리를 말한다. 한 노드가 자식 노드를 가지게 된다면 무조건 자식 노드가 2개라는 뜻이다. 이러한 특징 덕분에 포화 이진트리에서 모든 노드의 개수는 다음과 같다. 아래 그림은 포화 이진 트리의 예시이다. 2) 완전 이진트리(Complete Binary Tree) 완전 이진 트리는 높이가 h인 이진트리 일 때 h-1단계까지는 포화 이진트리와 동일하지만 h단계에서 노드..

대기열 시물레이션 큐의 선입선출 특성을 이용하여 다양한 시물레이션을 진행할 수 있다. 지금 해볼 것은 대기열에서 평균 대기 시간이 얼마나 되는지 이다. 예를 들어 한 손님이 은행에 갔다고 생각해보자. 은행에 들어가면 앞에 손님이 없다면 바로 서비스를 받을 수 있지만 손님이 있다면 먼저 온 손님이 모두 서비스를 받고 난 후에야 서비스를 받을 수 있을 것이다. 우리는 이러한 상황을 구현하여 어떤 손님이 은행에서 서비스를 받을 때까지의 대기 시간은 얼마이며, 은행이 문을 닫을때까지 손님들의 총 대기 시간, 평균 대기 시간을 예측할 것이다. 먼저 시물레이션에 사전 조건에 대해서 설명하자면 서비스를 처리하는 곳(은행 창구)는 1개이다. 그리고 손님의 정보로는 도착 시간, 서비스를 처리하는데 드는 시간(서비스시간)..

연결 리스트로 구현한 큐 연결 리스트로 구현한 큐의 장점은 미리 큐의 최대 크기를 정하지 않아도 된다는 점이다. 미리 최대 크기를 정하지 않기 때문에 배열 큐에서 빈공간이 있어도 리어 노드 앞에 공간이 없어 인큐 연산을 못하는 경우가 생기지 않기 때문에 메모리를 좀더 효울적으로 사용이 가능하다. 연결 리스트 큐의 구현 얀결 리스트를 이용해 스택을 구현할 때와 마찬가지로 연결 리스트를 사용하는데 연결 리스트를 통째로 사용하기 보다는 큐의 프런트 노드와 리어 노드에 대한 접근만 하면 되기 때문에 프런트 노드와 리어 노드를 가리키는 포인터만 사용한다. 각 함수 중간에 LQ가 있는데 LinkedQueue을 의미한다. 소스 파일 구성은 다음과 같다. 파일 이름 내용 linkedqueue.h 구조체 및 함수 선언 ..

배열 큐(Array Queue)란? 배열을 이용해 구현한 큐를 의미한다. 1차원 배열을 이용하기 때문에 자료들끼리 물리적으로도 연결되어 있고 배열 생성하기 전에 배열의 크기를 미리 정해주어야 한다. 배열로 만든 큐는 자료의 추가/제거를 반복하다 보면 빈 공간이 있음에도 이를 인식하지 못하는 경우가 생겨 메모리가 비효율적으로 쓰이는 문제점이 있다. 이는 다음에 구현해볼 배열을 이용한 원형 큐, 연결 리스트를 이용한 큐로 이를 해결할 수 있다. 각 함수 중간에 AQ가 있는데 ArrayQueue을 의미한다. 배열 큐의 구현 소스 파일 구성은 다음과 같다. 파일 이름 내용 arrayqueue.h 구조체 및 함수 선언 arrayqueue.cpp 함수 구현 arrayqueuemain.cpp main 함수 실행 1...

큐(Queue)이란? 큐도 자료를 차례대로 저장하는 선형 자료구조이다. 큐가 가지는 고유 특성은 FIFO(First-In-First-Out) - 선입선출(先入先出), 즉, 가장 먼저 들어간 자료가 가장 먼저 나오는 자료이다'라는 특성이다. 일상생활에서도 큐라는 단어를 자주 접한다.. 예를 들어 식당에 들어가기 위해 길게 늘어진 사람들의 줄을 대기열 혹은 큐라고 말한다. 큐가 길다는 말은 기다리는 사람들이 많아서 시간이 오래 걸린다는 의미로도 사용한다. 이러한 큐에 특징은 선입선출의 특성을 가진다. 스택에서는 스택의 특성 때문에 모든 연산이 스택의 제일 위(Top)에서 일어난다. 큐에서는 자료를 추가할 때는 뒤에서 추가하고 자료를 반환할 때는 앞에서 자료를 빼가기 때문에 스택보다 좀 더 생각해야 하는 부분..