레드 블랙 트리란 완전 이진 트리의 종류 중 하나이다.
레드 블랙 트리의 가장 큰 특징은 높이는 logN에 바운드 되기에 레드블랙트리에서 search연산은 O(logn)의 시간복잡도가 나온다는 것이다.
레드 블랙 트리의 조건은 크게 4가지가 있는데
1. 루트노드의 색깔은 블랙이다.
2. 모든 external node의 색깔은 블랙이다.
3. 빨강 노드의 자식은 black이다.
4. 모든 리프노드에서 black depth는 같다.
레드블랙트리는 노드가 추가될시 Restructuring과 Recoloring이라는 방법을 통해서 색깔의 중복을 피합니다.
다만 restrucuring은 1번으로 끝날 수 있는 반면에 Recoloring은 여러번이 생길 수 있습니다.
장점
1. 삽입, 삭제 시 작업 횟수가 적다.
2. 색깔을 표현하는데 1bit면 충분하다.
단점
1. 조회시 성능이 AVL트리보다 낮다.
2. AVL트리등 색깔이 없는 트리보다 메모리를 더 잡아 먹는다.