본문 바로가기

CS118

선택 트리, 숲, 이진 트리 개수 선택 트리 1) 개념 선택 트리는 정렬된 여러 데이터 리스트를 효과적으로 병합하는 데 사용되는 트리 구조이다. 이는 합병 정렬 과정에서 중요한 역할을 한다. 예를 들어, 8개의 정렬된 리스트가 있을 때, 이들 중 가장 작은 값을 빠르게 찾아내어 새로운 리스트를 생성하는 과정을 단순화한다. 선택 트리는 이러한 비교 과정의 횟수를 줄이는 데 크게 기여한다. 이 트리는 주로 승자 트리와 패자 트리의 두 가지 형태로 구성된다. 승자 트리는 더 작은 값을 가진 노드가 승자가 되어 상위 노드로 올라가는 완전 이진 트리 구조이다. 이는 각 노드가 두 자식 노드 중 작은 값을 선택하여 상위 노드로 올라가는 토너먼트와 유사한 방식으로 작동한다. 반면, 패자 트리는 루트 노드 위에 최상위 0번 노드를 두어 최종 승자를 저.. 2023. 11. 25.
힙 - 개념, 우선순위 큐, 삭제 삽입 연산 힙 개요 힙은 부분적으로 정렬된 완전 이진 트리이며, 부모 노드와 자식 노드 간의 크기 관계를 통해 정의된다. 이러한 힙의 특성은 두 가지 주요 형태인 최대힙과 최소힙에서 나타난다. 최대힙에서는 부모 노드가 자식 노드보다 크며, 최소힙에서는 그 반대의 관계를 갖는다. 힙은 노드의 삽입 및 삭제 연산 시에 완전 이진 트리의 형태를 유지해야 하며, 이를 위해 노드 간의 관계를 조정한다. *피라미드 모양으로 쌓아올린 더미를 힙이라고 한다. 우선순위 큐 우선순위 큐는 데이터가 우선순위에 따라 처리되는 자료 구조이다. 이 구조에서는 가장 높은 우선순위를 갖는 데이터가 먼저 나오는 것이 특징이다. 일반적인 큐와는 달리, 우선순위에 따라 데이터의 순서가 결정된다. 정의 및 특징: 우선순위 큐는 각 요소가 우선순위를 .. 2023. 11. 24.
스레드 트리, 개념, 구현, 연산 (순회 삽입 삭제) 스레드 트리 개요 스레드 트리의 발생 배경: 이진 트리의 순회 과정에서 스택을 사용하여 관리하는 번거로움을 해결하기 위해 등장. 이 과정에서 방문하지 않은 노드들을 스택에 저장하는 대신, 스레드라는 포인터를 사용하여 순회를 효율적으로 수행한다. 스레드 트리의 특징: 스레드 트리는 오른쪽 및 왼쪽 스레드를 활용하여 순회 순서를 유지한다. 오른쪽 스레드는 후속 노드를, 왼쪽 스레드는 선행 노드를 가리킨다. 개념 스레드의 정의와 역할: 스레드는 특정 순회 방법에 따라 다음에 방문할 노드를 가리키는 포인터이다. 이를 통해 순회 과정에서 다음 노드로의 이동이 간소화된다. 스레드 트리의 구현 방식: 포인터 추가 방식: 이 방법은 왼쪽 및 오른쪽 스레드 포인터 필드를 추가하여 노드 구조를 확장한다. 기억장소 부담이 .. 2023. 11. 24.
트리 용어 및 개념, 이진 트리, 순회 연산, 생성 삭제 조회 연산 - 자바 코드 트리 개요 트리(Tree)란? 개념과 특성: 트리는 계층적 구조를 나타내는 자료구조로, 노드(node) 또는 정점(vertex)으로 이루어진다. 데이터 간의 계층 관계와 포함 관계를 나타내는 데 적합하다. 비유적 표현: '트리'라는 용어는 거꾸로 세워진 나무를 연상시키며, 이 구조에서는 뿌리(root), 잎(leaf), 서브트리(subtree)와 같이 나무와 관련된 용어들이 사용된다. 이진 트리(Binary Tree): 트리의 모든 노드가 최대 두 개의 자식을 갖는 특별한 형태의 트리로, 수학적 이론 정리 및 컴퓨터 구현에 적합하여 자주 사용된다. 이진 트리의 종류 가득 찬 이진 트리(Full Binary Tree): 각 레벨의 노드가 최대한 많을 때, 즉 모든 레벨이 노드로 가득 차 있는.. 2023. 11. 24.
깊이 우선 탐색 (Depth-First Search) 깊이 우선 탐색 (Depth-First Search) 깊이 우선 탐색의 기본 원리 깊이 우선 탐색(DFS, Depth-First Search)은 그래프의 모든 정점을 탐색하는 효율적인 방법 중 하나이다. 이 알고리즘은 특정 시작 정점에서 출발하여, 가능한 한 깊이 있게 그래프를 탐색한다. 시작점에서의 탐색 DFS는 시작 정점 v에서 시작한다. 이 정점이 첫 방문 지점이다. 그런 다음에는 v에 인접한 미방문 정점 w를 찾아, w에서 다시 DFS를 시작한다. 이 과정은 모든 정점을 방문할 때까지 계속된다. 더 이상 방문할 정점이 없을 때 만약 현재 정점에 인접한 모든 정점을 방문했다면, 최근에 방문했던 정점 중에서 아직 방문하지 않은 인접 정점을 가진 정점으로 돌아가 탐색을 계속한다. 깊이 우선 탐색의 이해.. 2023. 11. 24.

티스토리툴바