CS/자료구조24 힙 - 개념, 우선순위 큐, 삭제 삽입 연산 힙 개요 힙은 부분적으로 정렬된 완전 이진 트리이며, 부모 노드와 자식 노드 간의 크기 관계를 통해 정의된다. 이러한 힙의 특성은 두 가지 주요 형태인 최대힙과 최소힙에서 나타난다. 최대힙에서는 부모 노드가 자식 노드보다 크며, 최소힙에서는 그 반대의 관계를 갖는다. 힙은 노드의 삽입 및 삭제 연산 시에 완전 이진 트리의 형태를 유지해야 하며, 이를 위해 노드 간의 관계를 조정한다. *피라미드 모양으로 쌓아올린 더미를 힙이라고 한다. 우선순위 큐 우선순위 큐는 데이터가 우선순위에 따라 처리되는 자료 구조이다. 이 구조에서는 가장 높은 우선순위를 갖는 데이터가 먼저 나오는 것이 특징이다. 일반적인 큐와는 달리, 우선순위에 따라 데이터의 순서가 결정된다. 정의 및 특징: 우선순위 큐는 각 요소가 우선순위를 .. 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. 연결 리스트의 변형: 원형 연결 리스트, 이중 연결 리스트 1. 연결 리스트의 변형 단순 연결 리스트의 문제점 단순 연결 리스트는 각 노드가 단일 링크(포인터)만을 갖는 구조로, 다음 노드에 대한 접근은 용이하지만, 이전 노드로의 접근이 어렵다. 즉, 노드 검색 시 처음부터 순차적으로 탐색해야 하므로 효율성이 떨어진다. 이러한 제한은 데이터 구조에서의 유연성을 감소시키며, 특정 애플리케이션에서는 이러한 단일 링크 구조가 비효율적일 수 있다. 이중 연결 리스트 이중 연결 리스트는 각 노드가 두 개의 링크를 갖는 구조로, 하나는 다음 노드를, 다른 하나는 이전 노드를 가리킨다. 이 구조는 노드 검색과 조작이 더 유연해지며, 특히 노드의 삽입과 삭제가 더 간단하고 빠르다. 하지만, 추가적인 메모리가 필요하다는 단점이 있다. 자바 코드 예시: class DoublyLi.. 2023. 11. 19. 이전 1 2 3 4 5 다음
