변수의 기록

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

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 트리는..