변수의 기록

B-Tree와 데이터베이스 인덱스1. B-Tree의 시간 복잡도B-Tree는 self-balancing 트리로, 다음과 같은 시간 복잡도를 가진다:탐색 (Search): O(logₙ N)삽입 (Insert): O(logₙ N)삭제 (Delete): O(logₙ N)여기서 N은 전체 키의 수, n은 자식 노드의 수(= branching factor)이다.즉, 자식 수가 많을수록 log의 밑이 커지므로 깊이가 얕아지고 탐색 횟수가 줄어든다.예시:자식 노드 수가 100일 경우, 1억 개의 키를 탐색할 때 최대 4단계만으로도 검색 가능.2. Secondary Storage의 특징하드디스크(HDD) 또는 SSD와 같은 보조 기억장치(Secondary Storage)는 다음과 같은 특징을 가진다:접근 속도는 RAM..

트리(Tree) 구조별 용도와 업무 적용 정리📌 1. 용도에 따른 분류 요약 트리 종류사용 환경사용 이유 / 장점B-Tree / B+Tree데이터베이스(DB)디스크 I/O 최소화 → 빠른 조회 성능AVL Tree / Red-Black TreeWAS (Java 등 메모리 내)정렬 + 빠른 삽입/삭제/검색, 메모리 기반 컬렉션에 적합BST (일반 이진 탐색 트리)거의 실무에 사용되지 않음교육용 / 알고리즘 연습용 📌 2. B-Tree / B+Tree – 왜 DB에서 사용하는가?✅ 사용 환경데이터베이스 인덱스 구조 (Oracle, MySQL, PostgreSQL 등)✅ 핵심 이유: 디스크 I/O 비용 최소화DB는 데이터를 디스크에 저장함 → I/O는 매우 느림B-Tree는 자식 노드 수가 많아서 트리 깊..

레드-블랙 트리(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..