이진탐색 트리 : 부모노드보다 값이 작은 것은 왼쪽 자식, 값이 더 크다면 오른쪽 자식으로 값을 저장한다. (문제점 : 20, 30, 40, 50 순서로 들어온다면 오른쪽으로 치우친 트리가 된다.)
일반적인 이진탐색 트리는 트리의 높이만큼 시간이 필요하므로, 데이터의 삽입이 한쪽으로만 치우치는 경우 트리의 높이가 높아져서 성능이 저하되는 문제가 발생한다.
레드 블랙 트리에는 4가지 규칙이 존재한다.
루트부터 리프까지의 블랙노드의 수가 동일하다는 규칙에 따라 트리의 가장 짧은 높이(모두 블랙노드일 경우)와 가장 긴 높이(블랙-레드의 반복)의 차이는 최대 2배가 안된다는 것이 보장된다.
따라서 삽입, 삭제의 경우에도 최선의 상황에서는 O(1), 최악의 상황(아래의 예시)이 오더라도 시간복잡도는 O(logn)으로 좋은 성능을 자랑한다.
삽입 시, 삽입되는 노드는 무조건 레드로 삽입된다. 삽입되는 노드의 부모노드가 블랙노드일 경우에는 괜찮지만, 레드노드일 경우에는 3번 규칙에 위배되므로 재배열 또는 색상변경이 필요하다.
이 경우는 부모노드의 형제노드가 블랙인 경우와 레드인 경우에 따라 다르게 처리된다.
1. 나(삽입노드)와 부모, 부모의 부모 노드 3개를 정렬하여 가운데 값을 부모로 설정한다.
2. 부모로 설정된 노드는 블랙, 자식은 레드로 설정한다.
3. 형제노드인 w노드를 왼쪽아래에 삽입한다.
-> 변환 후에도 블랙노드의 수가 변하지 않기 때문에 한번의 Restructuring으로 해결 가능
Restructuring : O(1), 삽입 : O(logn) 이므로 총 O(logn)의 시간복잡도가 생김
1. 나(삽입노드)의 부모와 부모형제 노드를 블랙으로 만들고, 부모의 부모를 레드로 바꿈
따라서 Recoloring은 한번으로 끝나지 않을 수 있다.
Recoloring : O(logn), 삽입 : O(logn) 이므로 결과적으로는 O(logn)이 성립된다.