2024-05-17-16. Red-Black Tree

Red-Black Tree

2-3-4 트리에서는 노드마다 3개의 키를 담을 공간이 필요하다. 이때, 2-노드와 3-노드에는 자리가 2개, 1개가 비게 된다. 이로 인해 메모리가 낭비될 수 있다.

2-3-4트리를 Red-Black 트리로 표현하면 빈 자리가 생기는 것을 막을 수 있다.

Red-Black 트리의 각 노드는 키를 하나만 가지며, 간선의 색깔을 지정하는 라벨을 가진다.

간선에는 두 가지 색깔 중 하나가 지정될 수 있는데, 검은색 간선은 일반적인 BST의 간선이다.

또한 붉은색 간선이라는 특수한 간선이 있는데, 이를 통해 3-노드, 4-노드를 표현한다.

3-노드는 Red-Black 트리에서 다음과 같이 표현된다.

2-3-4트리에서 하나의 노드 안에 있던 키값들은, Red-Black 트리에서 두 노드로 나뉘어저 붉은색 간선으로 연결된다.

4-노드는 다음과 같이 표현된다.

마찬가지로 하나의 노드 안에 있던 키값들이 나뉘어져 붉은색 간선으로 연결된다.

다만 4-노드를 위와 같이 세 개의 층으로 표현해선 안 된다.

즉, 아래로 내려가는 경로에서, 붉은색 간선이 연속적으로 등장해선 안 된다.

위와 같은 정의를 바탕으로, 레드-블랙 트리는 다음과 같은 특성을 가진다.

2-3-4트리에서 모든 리프 노드의 깊이가 같으므로, Red-Black 트리의 루트에서 널 포인터까지 내려갈 때 거치는 검은 간선 개수도 항상 같다.

여기서 루트부터 ‘리프 노드’까지 내려갈 때의 검은 간선 개수가 같다고만 하는 것은 불충분하다. 2-3-4트리와 달리 붉은 간선 하나와 널 포인터 하나를 갖는, 자식이 하나비어 있는 노드가 존재할 수 있기 때문이다.

2-3-4트리에서는 insert과정에서 4-노드를 만나면 두 개의 2-노드로 분할하였다.

red-black 트리에서는 (붉은 간선으로 표현된) 4-노드를 만나면 다음과 같이 처리한다.

노드 b에 붉은 간선으로 연결된 두 자식 노드가 연결되어 있을 때, 두 붉은 간선을 검은색으로 바꾸고 b의 부모 노드로 이어지는 검은 간선을 붉은색으로 바꾸기만 하면 된다.

단, 여기서 b의 부모 노드가 x이고, x의 부모 노드가 y라고 할 때, x와 y를 잇는 간선이 붉은색이면 문제가 발생한다.

위와 같이 연속된 붉은 간선이 생기게 된다. 이는 AVL트리와 마찬가지로 회전을 통해 해결할 수 있다.

다음과 같이 연속된 붉은 간선의 방향이 서로 다르면 처리하기 좀 더 복잡하다.

이때는 회전을 다음과 같이 두 번 해주면 된다.

insert후에도 연속된 붉은 간선이 생길 수 있다. 이런 경우 위와 마찬가지로 회전을 통해 해결한다.

Red-Black 트리는 2-3-4트리와 독립적으로 다음과 같이 정의할 수 있다.

Red-Black 트리는 붉은 간선과 검은 간선으로 구성된 BST이다.

또한 다음 두 조건을 만족해야 한다.

insert는 다음과 같이 진행된다.

먼저 일반적인 BST방식으로 노드를 insert한다. 이때 새 노드를 잇는 데 red edge를 사용한다.
연속적인 붉은 간선이 생겼다면 rotate를 수행하여 고친다.
한 노드 밑에 두 개의 붉은 간선이 있는 경우, 두 붉은 간선을 검은색으로 바꾸고, 부모 노드와 이어진 간선을 붉은색으로 바꾼다. 이러한 연산은 위쪽으로 전파될 수 있다.

Red-Black 트리와 AVL트리는 다음과 같은 세 가지 지점에서 유사하다.

← Previous Post Next Post →

목록으로