변수의 기록

레드-블랙 트리의 삭제 동작 방식과 시간복잡도레드-블랙 트리(Red-Black Tree)는 삽입보다 삭제가 더 복잡한 구조적 조정을 필요로 한다.이는 트리의 속성(#2~#5)이 깨질 가능성이 높기 때문이며,특히 Black 노드가 삭제되는 경우 트리의 균형이 크게 영향을 받는다. 참고 (레드-블랙 트리의 5가지 주요 속성)모든 노드는 Red 또는 Black이다.루트 노드는 항상 Black이다.모든 leaf 노드(NIL 노드)는 Black이다.실제 값이 없는 NIL 노드는 트리의 균형 계산에 사용됨.Red 노드의 자식은 모두 Black이다.즉, Red 노드가 연속적으로 나타날 수 없다.임의의 노드에서 그 자손인 모든 NIL 노드로 가는 경로에는 같은 수의 Black 노드가 있다.이를 Black Height라..

레드-블랙 트리(Red-Black Tree) 개념과 속성 정리레드-블랙 트리는 자기 균형 이진 탐색 트리(Self-balancing BST) 의 일종이다. 일반 이진 탐색 트리(BST)는 삽입 순서에 따라 한쪽으로 편향될 수 있는데, 레드-블랙 트리는 특정 규칙을 통해 항상 트리의 높이를 O(log N) 수준으로 유지함으로써 검색, 삽입, 삭제 연산을 효율적으로 만든다.✅ 기본 개념이진 탐색 트리(BST)의 변형으로, 추가적인 색상 속성을 가지는 트리.모든 노드는 Red 또는 Black 색을 가짐.자체적으로 균형을 유지하여, 최악의 경우에도 탐색 시간이 O(log N)을 보장함.✅ 레드-블랙 트리의 5가지 주요 속성모든 노드는 Red 또는 Black이다.루트 노드는 항상 Black이다.모든 leaf 노드..

AVL 트리 개념과 특징1. AVL 트리란?AVL 트리는 **이진 탐색 트리(BST)**의 일종이다.스스로 균형을 잡는(self-balancing) 특성을 갖는다.1962년 Georgy Adelson-Velsky와 Evgenii Landis가 고안했다. (AVL 이름 유래)2. AVL 트리의 핵심: 밸런스 팩터 (Balance Factor)임의의 노드 X에 대해 밸런스 팩터(BF)는 다음과 같이 정의한다. BF(X) = 높이(왼쪽 서브트리) - 높이(오른쪽 서브트리) AVL 트리의 모든 노드는 반드시 다음 중 하나의 BF 값을 가진다. BF ∈ {-1, 0, 1}이 범위를 벗어나면 트리의 균형이 깨진 것으로 판단하여 **균형 조정 작업(회전)**을 수행한다. AVL 트리 균형 잡기 메커니즘AVL 트리는..

이진 탐색 트리 (Binary Search Tree, BST)1. 개념이진 탐색 트리(Binary Search Tree, BST)는이진 트리의 일종으로, 다음의 조건을 만족하는 트리 구조를 말한다.모든 노드의 왼쪽 서브트리: 현재 노드의 값보다 작은 값을 가진 노드들로 구성모든 노드의 오른쪽 서브트리: 현재 노드의 값보다 큰 값을 가진 노드들로 구성이러한 규칙 덕분에 탐색(search), 삽입(insert), **삭제(delete)**를 효율적으로 수행할 수 있다. 2. 이진 탐색 트리 순회 방법 (Traversal)트리의 모든 노드를 방문하는 방법을 **트리 순회(Tree Traversal)**라고 한다.이진 탐색 트리에서는 주로 다음 세 가지 순회 방법을 사용한다.(1) 중위 순회 (In-order..

트리(Tree) 기본 구조와 핵심 개념 정리1. 트리(Tree)란 무엇인가?트리는 **노드(Node)**들의 집합으로 구성된 비선형 자료구조이다.각 노드는 하나의 값(value)과 여러 개의 자식 노드(child nodes)에 대한 **레퍼런스(참조)**를 가진다.트리의 특징루트(Root): 최상단에 위치한 하나의 노드사이클 없음: 어떤 경로로도 다시 자신에게 돌아올 수 없다.부모-자식 관계: 각 자식 노드는 오직 하나의 부모 노드만 가진다.계층적 구조: 데이터가 순차적으로가 아닌 계층적으로 저장된다.재귀적 성질: 각 노드 자체가 또 다른 서브트리(subtree)를 구성할 수 있다.2. 트리 기본 용어 정리 용어 설명간선(Edge)노드와 노드를 연결하는 선. 구현 관점에서는 레퍼런스(포인터) 의미.루트..

2024년 4월 3일메모리 공부 (스택 집중)   전체 메모리 구조 개요 (낮은 주소 → 높은 주소)   📘 스택(Stack) 구조 정리 - 시스템 관점 요약1️⃣ 스택의 기본 개념항목내용구조LIFO (Last In, First Out)위치프로세스 메모리의 Stack 영역방향높은 주소 → 낮은 주소 방향으로 성장사용 목적함수 호출 시 지역 변수, 매개변수, 반환 주소, 이전 상태 저장 등2️⃣ 주요 레지스터: ESP vs EBP레지스터역할설명ESP (Stack Pointer)스택의 현재 꼭대기 위치지역 변수 할당, push/pop 시 변동EBP (Base Pointer)함수의 스택 프레임 기준점지역 변수/매개변수 접근 시 기준점, 함수 내 고정✅ ESP는 변동, EBP는 고정된 기준3️⃣ 함수 호출 시..

2025년 4월 3일자바 자료구조 공부자료구조 기초 정리1. 배열 (Array)배열은 동일한 자료형의 데이터를 연속된 메모리 공간에 저장하는 선형 자료구조로, 인덱스를 기반으로 한 임의 접근(random access)이 가능하다. Java에서 배열은 선언 시 고정된 크기를 가지며, 이후 크기를 변경할 수 없다. 배열은 인덱스를 이용한 조회 연산에서 시간 복잡도 O(1)의 효율을 가지며, 삽입 또는 삭제 시 전체 데이터를 이동해야 하므로 O(n)의 시간 복잡도를 갖는다. ex) int[] arr = new int[5];arr[0] = 10; 배열은 메모리상 연속된 공간을 점유하므로 CPU 캐시 효율이 높고, 인덱스를 통한 접근이 매우 빠르다. 그러나 삽입과 삭제 연산이 잦은 경우에는 성능상의 단점이 존재한..