본문 바로가기

전체 글669

스레드 트리, 개념, 구현, 연산 (순회 삽입 삭제) 스레드 트리 개요 스레드 트리의 발생 배경: 이진 트리의 순회 과정에서 스택을 사용하여 관리하는 번거로움을 해결하기 위해 등장. 이 과정에서 방문하지 않은 노드들을 스택에 저장하는 대신, 스레드라는 포인터를 사용하여 순회를 효율적으로 수행한다. 스레드 트리의 특징: 스레드 트리는 오른쪽 및 왼쪽 스레드를 활용하여 순회 순서를 유지한다. 오른쪽 스레드는 후속 노드를, 왼쪽 스레드는 선행 노드를 가리킨다. 개념 스레드의 정의와 역할: 스레드는 특정 순회 방법에 따라 다음에 방문할 노드를 가리키는 포인터이다. 이를 통해 순회 과정에서 다음 노드로의 이동이 간소화된다. 스레드 트리의 구현 방식: 포인터 추가 방식: 이 방법은 왼쪽 및 오른쪽 스레드 포인터 필드를 추가하여 노드 구조를 확장한다. 기억장소 부담이 .. 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.
컴퓨터는 실제로 배열의 데이터에 index로 접근할까? 컴퓨터는 실제로 배열의 데이터에 index로 접근할까? 배열과 인덱스의 기본 이해 배열은 연속적인 메모리 공간에 데이터를 저장하는 구조이다. 각 요소는 인덱스를 통해 접근된다. 메모리 주소와 인덱스의 관계 그러나, 인덱스는 실제 메모리 주소를 직접 나타내지는 않는다. 인덱스는 기본적으로 메모리 주소에 대한 '오프셋'을 의미한다. 실제 메모리 접근 방식 실제 메모리 주소 계산을 예로 들어보자. 배열의 시작 주소가 1000이고, 각 요소가 4바이트를 차지한다면, 인덱스 3의 요소는 어떻게 계산될까? 계산식은 '1000 + (3 * 4)'가 되어, 이 요소의 메모리 주소는 1012가 된다. 이처럼 배열은 실제로는 '기준 주소 + (인덱스 * 요소 크기)'로 계산된 값.. 2023. 11. 24.
연결 리스트의 변형: 원형 연결 리스트, 이중 연결 리스트 1. 연결 리스트의 변형 단순 연결 리스트의 문제점 단순 연결 리스트는 각 노드가 단일 링크(포인터)만을 갖는 구조로, 다음 노드에 대한 접근은 용이하지만, 이전 노드로의 접근이 어렵다. 즉, 노드 검색 시 처음부터 순차적으로 탐색해야 하므로 효율성이 떨어진다. 이러한 제한은 데이터 구조에서의 유연성을 감소시키며, 특정 애플리케이션에서는 이러한 단일 링크 구조가 비효율적일 수 있다. 이중 연결 리스트 이중 연결 리스트는 각 노드가 두 개의 링크를 갖는 구조로, 하나는 다음 노드를, 다른 하나는 이전 노드를 가리킨다. 이 구조는 노드 검색과 조작이 더 유연해지며, 특히 노드의 삽입과 삭제가 더 간단하고 빠르다. 하지만, 추가적인 메모리가 필요하다는 단점이 있다. 자바 코드 예시: class DoublyLi.. 2023. 11. 19.

티스토리툴바