본 문서는 필자가 전공 수업을 수강하며 배운 내용에 대해 간략히 정리하기 위해 작성하는 문서이다. 복잡한 증명보다는 개념 이해를 위해 내용을 전개하고자 한다.
이진 탐색 트리는 데이터 검색에 효율적이지만, 데이터가 편향되게 삽입될 경우 성능이 저하되는 단점이 있다.
예를 들어, 오름차순으로 데이터가 계속 입력되면 트리가 한쪽으로 길게 늘어진 형태가 되어, 검색 시간이 O(n)에 가까워진다.
이는 순차 탐색과 비슷한 비효율적인 성능이다.
이러한 문제를 해결하기 위해 '자가 균형' 기능이 도입된 이진 탐색 트리가 사용된다.
이 트리들은 데이터 삽입 및 삭제 시, 스스로 구조를 재조정하여 트리가 한쪽으로 치우치는 것을 방지하고 항상 O(log n)의 검색 성능을 보장한다.
대표적인 자가 균형 이진 탐색 트리로는 AVL 트리와 RB 트리가 있다.
AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 엄격하게 균형을 관리한다.
데이터 삽입 또는 삭제로 균형이 깨지면, 트리 '회전(Rotation)'을 통해 구조를 재조정하여 균형을 맞춘다.
이러한 엄격함 덕분에 검색 성능이 매우 뛰어나지만, 삽입/삭제 시 회전이 빈번하게 발생할 수 있다는 특징이 있다.
RB 트리(Red-Black Tree)는 노드에 '색상(Red 또는 Black)' 속성을 부여하고, 특정 규칙을 통해 트리의 균형을 유지하는 또 다른 자가 균형 이진 탐색 트리이다.
AVL 트리보다 균형을 덜 엄격하게 관리하여, 삽입 및 삭제 시 발생하는 회전 횟수가 상대적으로 적을 수 있다.
이로 인해 삽입/삭제가 빈번한 환경에서 더 나은 성능을 보이는 경우가 많다.
RB 트리가 만족해야 하는 규칙은 다음과 같다.
1. 모든 노드는 Red 또는 Black이다.
2. 루트 노드는 항상 Black이다.
3. 모든 리프 노드(NIL)는 Black이다.
4. Red 노드의 자식은 반드시 Black이어야 한다. (Red 노드가 연속으로 나타날 수 없다.)
5. 특정 노드에서부터 그 자손인 리프 노드에 도달하는 모든 경로에는 동일한 개수의 Black 노드가 존재해야 한다. (이를 '블랙 높이(Black-Height)'라 한다.)
이러한 규칙들은 트리의 가장 긴 경로가 가장 짧은 경로의 두 배 이상이 되지 않도록 보장하여, 트리가 전체적으로 균형을 유지하도록 만든다. 결과적으로 RB 트리는 검색, 삽입, 삭제 연산에서 안정적으로 O(log n)의 시간 복잡도를 보장하게 된다.