[알고리즘] 레드 블랙 트리 (Red-Black Tree) 의 특징

이번 포스트에서는 Red Black Tree에 대해 다뤄보겠다. Red Black Tree는 이진검색트리 (BST; Binary Search Tree)에서 파생된 자료구조이다. 기존의 이진검색트리는 최악의 경우, 트리의 구조가 잘못 형성되어 한 쪽 (왼쪽/오른쪽)으로 치우친 경우 검색, 삽입, 삭제 과정이 Θ(n)까지 떨어질 수 있는 문제가 존재했다. 이러한 일을 방지하고자 트리의 균형을 맞추려는 시도가 이루어졌고, 그 중 하나가 레드 블랙 트리이다. 레드 블랙 트리는 개념적으로 노드의 색을 red와 black으로 설정하여 다음과 같은 규칙을 설정하여 트리의 균형을 맞춘다. Root 노드는 Black이다. 모든 Leaf(NIL)은 Black이다. Red 노드의 자식 노드는 Black이다. Root 노드에..

2024.03.06