-
이진 검색 트리의 문제점
이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다.
이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다.레드 블랙 트리의 특성
레드 블랙 트리는 이진 검색 트리의 균형 유지를 위해 다음의 특성이 만족되도록 트리의 구성을 변경한다.
- 루트는 블랙이다.
- 모든 리프(NIL)는 블랙이다.
- 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
- 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
쉽게 배우는 알고리즘 레드 블랙 트리 그림 5-10 ※ 리프 노드는 NIL이라는 이름의 존재하는 노드로 색상을 블랙으로 표현하여 일관된 알고리즘을 적용할 수 있게 한다.
※ NIL 노드는 하나만 생성한 뒤 리프 노드를 가리킬 때 포인터로 이 NIL노드를 가리키는 것으로 메모리를 절약할 수 있다.