목록트리 (6)
변수의 기록
트리(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는 자식 노드 수가 많아서 트리 깊..

B-Tree : 구조, 작동 원리, DB에서의 활용1. B-Tree란?B-Tree는 **Binary Search Tree(이진 탐색 트리)**를 일반화한 트리 자료구조입니다. 데이터베이스와 파일 시스템 등, 디스크 기반의 저장 시스템에서 대량의 데이터를 효율적으로 검색, 삽입, 삭제할 수 있도록 설계된 구조입니다.왜 B-Tree가 필요한가?일반 이진 탐색 트리는 삽입 순서에 따라 한쪽으로 치우칠 수 있어 최악의 경우 O(n) 시간복잡도를 가집니다.반면 B-Tree는 항상 균형을 유지하며, 트리의 높이를 제한해 모든 연산이 O(log n) 시간에 수행됩니다.특히 디스크 I/O 비용이 큰 환경에서 적은 횟수의 블록 접근으로 원하는 데이터를 찾을 수 있도록 설계되었습니다.2. B-Tree의 구조기본 구성M차 ..

레드-블랙 트리(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)노드와 노드를 연결하는 선. 구현 관점에서는 레퍼런스(포인터) 의미.루트..