알고리즘 ) Red-Black Tree

개념

이진 탐색 트리를 보안한 트리

1. 노드의 레벨이 (레드 & 레드가되면 안된다)
2. Root 노드는 항상 검정
3. 마지막 노드는 항상 검정

발생 원인

이진 탐색 트리의 경우, 배열과 연결 리스트의 장점만 적용하여 만들었으나 rebalance 문제가 발생함.(한쪽으로 노드가 쏠리는 현상)

이를 보안하기 위해 나온 자료 구조가 AVL Tree와 레드 & 블랙 트리 이다.

원리

이진 탐색 트리의 경우 중위 순회로 정렬하게 되면 오름차순으로 정렬이 되기 때문에 속도가 빠르다. 또한 데이터 검색에 log2N 으로 빠르다.

삽입 시 기존 이진 탐색 트리가 보였던 문제를 해결하기 위해 나왔다.

삽입

1. 삽입 시 더블 레드가 발생하면
   1. 삽입할 위치가 정해지면 부모노드의 형제노드(삼촌노드)가 무슨 색이냐에 따라 방식이 달라진다.
   2. 삼촌노드가 검은색인 경우, restructure를 한다.
      1. 본인, 부모노드, 할머니 노드를 정렬한다.
      2. 3개의 값 중 2번째(중간) 값을 부모노드로 하고 나머지 값들을 자식 노드로 리밸런스한다.
      3. 여기서 부모노드를 검은색으로하고 자식노드를 빨간색으로 변화한다.
      4. 기존의 노드에 딸려있던 노드를 붙인다.
      5. 삽입이 O(1), 총 수행시간 O(logN)
   3. 삼촌노드가 빨간색인 경우, recolor를 한다.
      1. 부모노드와 삼촌 노드를 검은색으로 변
      2. 할머니 노드를 빨간색으로 변화
         1. 만약 할머니 노드가 root 노드면 검은색
         2. 만약 할머니 노드의 부모 노드가 검은색이면 끝.
         3. 만약 할머니 노드의 부모 노드가 빨간색이면
            1. 삼촌노드의 색깔을 보고 restructure | recolor