변수의 기록

레드-블랙 트리의 삭제 동작 방식과 시간복잡도레드-블랙 트리(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 트리는..