ITPE * JackerLab

개요레드-블랙 트리(Red-Black Tree)는 자가 균형(Self-Balancing)을 유지하는 이진 탐색 트리(BST)의 한 종류로, 삽입과 삭제 연산 시 트리의 높이를 일정하게 유지하여 O(log n)의 시간 복잡도를 보장한다. 주로 표준 라이브러리의 Map, Set 구조 및 데이터베이스 인덱스 구현에 활용된다.1. 개념 및 정의레드-블랙 트리는 각 노드가 색상(빨강 또는 검정)을 가지며, 특정 규칙을 통해 트리의 균형을 유지하는 자료구조이다. AVL 트리보다 삽입/삭제 비용이 낮아 실무에서 널리 사용된다.2. 특징항목설명비고색상 속성각 노드는 Red 또는 Black균형 유지 핵심루트/리프 규칙루트는 항상 Black안정성 확보연속 Red 금지Red 노드의 자식은 Black균형 유지Black Hei..

개요이진 탐색 트리(BST, Binary Search Tree)는 이진 트리의 일종으로, 왼쪽 서브트리에는 루트보다 작은 값이, 오른쪽 서브트리에는 루트보다 큰 값이 저장되는 자료구조이다. 중복 없는 정렬된 데이터를 저장하면서 빠르게 탐색, 삽입, 삭제가 가능하며, 평균적으로 O(log n)의 성능을 보인다. 알고리즘 문제풀이와 데이터베이스, 메모리 관리 등 다양한 분야에 활용된다.1. BST의 구조와 특징 구성 요소 설명 루트(Root)트리의 최상위 노드노드(Node)데이터와 자식 포인터를 포함한 단위왼쪽 자식루트보다 작은 값오른쪽 자식루트보다 큰 값BST는 모든 노드에 대해 왼쪽 이 성립한다.2. BST의 연산 동작 원리연산동작 방식시간 복잡도 (평균/최악)탐색(Search)루트부터 값 비교, 작으..

개요트리(Tree)는 노드(Node)와 간선(Edge)로 구성된 계층적 비선형 자료구조로, 하나의 루트 노드(Root)에서 시작하여 자식 노드로 분기되는 구조를 가진다. 트리는 컴퓨터 과학에서 데이터 분류, 탐색, 계층 구조 표현 등 매우 널리 사용되며, 이진 트리, 이진 탐색 트리, 힙, 트라이, AVL 트리, B트리 등 다양한 종류가 있다.1. 트리의 개념과 구성 요소 구성 요소 설명 노드(Node)데이터를 담는 기본 단위루트(Root)트리의 시작 노드 (부모가 없음)부모(Parent), 자식(Child)노드 간 관계 정의리프(Leaf)자식이 없는 마지막 노드서브트리(Subtree)특정 노드를 루트로 하는 부분 트리간선(Edge)노드 간 연결 관계2. 트리의 특성특성설명비선형 구조노드 간 관계가 계..