Data Structure
[자료구조] RB Tree(레드-블랙 트리)
RB Tree란? Red-Black Tree는 이진 탐색 트리의 한 종류이다. 가장 기본적인 형태의 이진 탐색 트리는 최악의 경우 트리의 높이가 n으로 나타나 비효율적인 면이 있는데, 이를 보완하기 위해 삽입 또는 삭제 연산 시 트리의 균형을 맞추는 트리들이 나타났다. 이를 자가 균형 트리라고 부르며, 대표적으로 AVL Tree와 Red-Black Tree가 있다. 이번에는 Red-Black Tree에 대해 알아보자. RB Tree에는 총 다섯 가지의 규칙이 있으며, 이 규칙을 통해 트리의 밸런스를 유지한다. 다섯 가지의 규칙은 아래와 같다. RB Tree의 다섯 가지 규칙 1. 모든 노드는 빨간색 혹은 검은색 노드이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드들은 검은색이다. 4. 빨간색 노..
