레드 블랙 트리

레드 블랙 트리란

이진 탐색 트리의 단점인 균형을 유지할 수 없는 부분을 보완한 트리이다.

 

이렇게 이진 탐색 트리의 단점을 보완하여 균형을 유지하는 트리를 밸런싱 트리라고 한다.

 

AVL 트리 와 Red-Black 트리가 대표적이다.

 

레드 블랙 트리의 구현

 

레드 블랙 트리는 노드에 레드와 블랙이라는 개념이 추가된다

struct NODE {
	int data;

	struct NODE* left;
	struct NODE* right;
	struct NODE* parent;

	// 0 : 레드 / 1 : 블랙 / 2 : 이중 블랙
	int black;
};

나는 위와 같이 black라는 변수로 나타냈다.

 

그리고 원래의 트리에서는 마지막 노드의 left right는 자식 노드가 없으므로 nullptr 이지만,

 

레드 블랙 트리는 nil이라는 black값을 같는 노드를 가르킨다.

 

균형 유지를 위한 흑색 null이라 보면됨 근데 노드임

 

그래서 레드 블랙 트리는 위와 같은 추가사항으로 몇 가지 규칙을 유지해야 한다.

 

1. 모든 노드는 레드이거나 블랙이다.

 

2. 루트 노드는 블랙이다.

 

3. 레드 노드의 자식은 블랙이다. 레드가 연속으로 올 수 없음

 

4. 루트 노드부터 리프 노드 (마지막 노드)까지의 모든 경로에서 블랙의 개수가 동일해야 한다.

 

5. 리프 노드는 검은색이다. ( nil )