레드블랙트리

레드블랙트리 란?

레드블랙트리는 이진 탐색 트리의 노드가 편향적으로 배치되어 트리의 균형이 맞지 않을 수 있다는 단점을 보완한 균형 이진 트리이다. 즉 이진 탐색 트리에 데이터를 삽입하고 균형을 맞추는 알고리즘 가동시키는 자료구조라고 할 수 있다. 레드블랙트리는 아래와 같은 특성을 가진다. 이러한 특성을 만족하면 자동적으로 균형이 맞춰지게 된다. 

• 노드는 레드 혹은 블랙
• 루트노드는 블랙
• 리프노드(NIL)는  블랙
• 레드노드의 자식은 모두 블랙. 블랙노드만이 레드노드의 부모가 될 수있음.
• 어떤 노드부터 리프노드에 도달하는 경로는 리프노드를 제외하고 모두 같은 블랙노드 수를 가진다.

이런 특성을 맞추기 위해서는 노드 삽입, 삭제 시 추가적인 알고리즘이 적용되어야 한다.

이 알고리즘을 따라 코드를 구현하는 작업은 어렵지 않으나, 이러한 특성을 맞추면 어째서 균형 이진 트리가 되는지 이해하는 것은 어려울 수 있다.

 

트리 회전

레드블랙 트리의 삽입, 삭제를 알아보기 전에 필요한 유틸에 대해 알아야 한다. 그것은 노드 회전이다. 왼쪽, 오른쪽으로 회전시킬 수 있는데, 아래와 같은 과정을 말한다. 

• Left Rotation : 
• Right Rotation : 

 

INSERT 

노드 삽입 시에는 기본적으로는 이진 탐색 트리와 같이 삽입한다.

단, 레드 노드를 삽입하게 되며, 삽입 이후 레드블랙트리의 조건을 만족시키기 위해 노드의 색, 위치를 변경해주어야 한다는 점이 다르다. 

노드의 색, 위치를 바꿔주는 작업은 아래와 같은 과정을 부모 노드로 거슬러 올라가며 따르면 된다.

• 부모 노드가 왼쪽 자식인 경우

1. 부모 노드가 레드이고, 삼촌 노드가 레드인 경우 :  단순히 부모는 블랙, 삼촌은 블랙, 부모의 부모는 레드 노드로 바꾸어주면 된다.
2. 부모 노드가 레드이고, 삼촌 노드가 블랙인 경우( 삼각형 모양 ) : 왼쪽 회전을 통해 3번 경우로 만들어 주고 3번 경우의 과정을 따른다. 
3. 부모 노드가 레드이고, 삼촌 노드가 블랙인 경우( 일직선 모양 ) : 부모 노드를 블랙으로 바꾸고, 부모의 부모 노드를 레드로 바꾸고, 부모의 부모 노드 기준으로 오른쪽 회전을 해주면 된다. 

• 부모 노드가 오른쪽 자식인 경우 : 왼쪽 자식인 경우와 반대되는 회전을 해주면 된다. 
• 모든 과정이 끝나면 최종적으로 루트 노드를 블랙으로 만들어주기. 

DELETE

레드 노드 삭제일 경우 말단 노드면 그냥 삭제해주고, 아니라면 삭제하고 자식 노드를 그 자리에 올려 대체해주면 된다.

그런데 블랙 노드 삭제일 경우 위에서 설명한 5번 조건 '어떤 노드부터 리프노드에 도달하는 경로는 리프노드를 제외하고 모두 같은 블랙노드 수를 가진다.' 때문에 골치아파진다. 6가지 경우에 따른 회전, 색상변환 방법이 있는데, 자세한건 귀찮으니까 나중에 쓸래 응애