* Binary Tree(이진 트리)

자식이 최대 2개만 존재하는 트리구조 

각 층별로 숫자를 매겨서 Level이라고 부르는데 레벨 값은 0부터 시작하므로 루트 노드의 레벨은 0이다.

모든 레벨이 꽉 찬 경우 이를 포화 이진 트리라고 부르며 i번째 노드의 자식은 i*2번째와 i*2+1번째 노드가 된다.

이진 트리는 1차원 배열로 구현할 수 있으며 다음 그림과 같이 구현이 가능하다.

* Binary Search Tree

이진 탐색 트리에서 효율적으로 탐색하는 방법은, 이진 트리에 데이터를 효과적으로 넣는 방법에서부터 시작이다.

이진 탐색 트리는 다음과 같은 규칙을 통해 데이터를 저장한다.

1. 이진 탐색 트리에서 노드에 저장된 키는 유일하다.

2. 루트 키의 왼쪽 서브 트리에 존재하는 모든 키는 루트 키보다 작아야 한다.

3. 루트 키의 오른쪽 서브 트리에 존재하는 모든 키는 루트 키보다 커야 한다.

이러한 조건을 만족시키며 값을 저장하기 때문에 저장과 삽입, 삭제시의 시간복잡도는 O(logN)이다.

하지만, 한쪽으로만 데이터가 저장되는 경우 배열보다 많은 메모리를 사용하면서 시간복잡도가 같은 비효율적인 상황이 발생한다.(편항 트리)

이러한 문제를 해결하기 위해 Rebalancing 기법이 등장하였는데, 이를 구현한 트리중 하나인 Red-Black Tree가 있다.

* Red-Black Tree

Red-Black Tree는 자가 균형 이진 탐색 트리로 편향 트리의 단점을 보완한 이진 탐색 트리이다.

즉, 동일한 노드의 수를 가질 때 Depth를 최소화 하여 시간 복잡도를 줄이는 것이 주 목적이다.

Red-Black Tree의 모든 노드는 Red or Black 의 색깔을 가지며 다음 조건을 만족한다.

1. 루트 노드의 색깔은 Black이다.
2. 모든 리프 노드의 색깔은 Black이다.
3. Red 색깔 노드의 자식의 색깔은 Black이다.
4. 모든 리프 노드에서 루트 노드까지 가는 경로에서 만나는 Black 노드의 수는 같다.

이 경우 3번 조건인 Red 색깔 노드의 자식은 무조건 Black 이여야 하는 조건을 위배한다.

이를 해결하는 전략으로 Restructuring(회전), Recoloring(색깔 변환)의 방법이 있다.

Double Red 문제를 해결하기 위해서는 현재 추가된 Node의 부모의 친척의 색깔에 따라 달라진다. 

아래 그림에서는 Z의 부모 친척 노드는 W가 된다.

## 부모 친척 노드가(W) Black인 경우는 Restructuring 과정을 거친다.

1. 나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬한다       
2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다. 
3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다. 

## 부모 친척 노드가(W) Red인 경우는 Recoloring 과정을 거친다.

1. 현재 inset된 노드(z)의 부모와 그 형제(w)를 검정(Black)으로 하고 Grand Parent(내 부모의 부모)를 빨강(Red)로 한다. 
2. Grand Parent(내 부모의 부모)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다. 

위 과정을 거치면  같은 트리가 구성될 것이다.

하지만, 4가 루트 노드가 아니라면 또다시 Dobule Red 문제가 발생할 수 있고, 이 경우 다시 Restructuring / Recoloring 과정을 거쳐야 한다.

이러한 과정을 거치기 때문에 Red-Black Tree의 삽입, Restructuring, Recoloring 모든 작업의 시간복잡도는 O(logN)가 된다.