레드-블랙트리

레드-블랙트리는 AVL트리처럼 스스로 균형을 잡는 자가 균형 이진 탐색트리다.

레드-블랙트리 규칙

1. 모든 노드는 빨간색이나 검은색.
2. 루트는 항상 검은색.
3. 새로 추가되는 노드는 항상 빨간색, 즉 잎 노드는 항상 빨간색
4. 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 한다.
   모든 잎노드가 루트까지 올라가는 동안 만나는 검은 노드의 개수가 모두 같다.
5. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어서는 안 된다.
   빨간색 노드의 자식은 모두 검은색 노드여야하지만, 검은색 노드의 자식은 빨간색이 아니어도 된다.
6. 모든 빈 노드는 검은색이라고 가정.

균형을 맞추는 방법

이모 노드가 검은색일 경우
회전을 한다.
회전은 모든 트리가 동일하다.
회전을 하고 나면 부모 노드는 검은색, 두 자식 노드는 빨간색이 되어야한다.

이모 노드가 빨간색일 경우
색상 전환을 한다.
색상 전환을 하고 나면 부모 노드는 빨간색, 두 자식 노드는 검은색이 되어야 한다.

클래스

레드-블랙트리를 키와 값을 가진 클래스와 인터페이스를 가지고 구현해보자.

public class RedBlackTree<K,V> implements RedBlackI<K,V> {
	Node<K,V> root;
	int size;
	class Node<K,V> {
		K key;
		V value;
		Node<K,V> left, right, parent;
		boolean isLeftChild, black;
		public Node (K key, V value) {
			this.key = key;
			this.value = value;
			left = right = parent = null;
			black = false;
			isLeftChild = false;
		}
	}
}

루트 노드와 크기 카운터를 전역변수로 설정해주었다.

내부클래스에서는 이모노드를 알아내기위해 left, right, parent포인터와 isLeftChild라는 불리언 값을 정의했다.

isLeftChild는 규칙을 망가트린 노드의 부모노드가 오른쪽 자식이라면 이모노드는 왼쪽자식일것이고, 부모노드가 왼쪽 자식이라면 이모노드는 오른쪽 자식에 있을 것이기 때문이다.

그리고 또 다른 불리언 값은 노드가 검정이면 참, 빨간색이면 거짓을 표시하기 위해 black이라고 정의했다.

생성자는에서는 노드를 초기화 하기위해서 left,right,parent 를 모두 null로 두고, 새로운 노드는 모두 빨간색 이기때문에 black을 거짓으로 정의했다.

생성자의 노드는 아직 누구와도 붙어있지 않기때문에 isLeftChild를 거짓으로 했으나 참으로 해도 상관은 없다.