TIL 정리_91(레드블랙트리)

https://www.boostcourse.org/cs204

자료구조 강의를 듣고 정리한 내용입니다

 

 

adding data
균형이 맞아야한다는 규칙에 따른 트리 생성 
어떤 종류의 회전을 했는지 기입하고 트리의 상태를 항상 그려야 한다
-> 트리가 균형이 맞는지 확인하는 과정에서 필요하다 

 

 

트리의 균형을 맞추는 또 다른 방식

 

레드 블랙 트리

모든 노드를 빨강 또는 검정으로 설정한다
새로운 요소를 추가 할 때 마다 규칙을 확인한다

 

트리의 규칙(중요)

1. 모든 노드는 빨간색이거나 검은색이다
2. 루트는 항상 검은색이다 //아닐시 강제로 변환
3. 새로 추가되는 노드는 항상 빨간색이다 //빨강 -> 검정
4. 루트에서 잎 노드로 가는 모든 경로 (== 트리에서 만들 수 있는 모든 경로)는 같은 수의 검은색 노드가 있어야 한다
5. 어떤 경로에서도 빨간색 노드 두 개가 연속적으로 있어서는 안 된다. //검은색은 중복 가능
6. 모든 빈 노드는 검은색이라고 가정한다

 

균형을 맞추는 방법 
트리의 규칙이 어긋나게되어 트리를 고치는 경우
고치기 위한 규칙 == 트리의 균형을 다시 맞추기 위한 규칙이다 
1. 이모 노드가 검은색인 경우
회전을 한다. 
회전을 하고나면 부모 노드는 검은색, 두 자식 노드는 빨간색이 되야한다.

2. 이모 노드가 빨간색인 경우
색상을 전환한다.
색상을 바꾸면 부모 노드는 빨간색, 두 자식 노드는 검은색이 되어야 한다.


레드블랙트리는 회전 여부를 노드의 색깔로 파악해야 한다
-> boolean으로 판별 
이모 노드를 알아내기 위해 left, right, parent 노드를 가리키는 포인터와
불리언 값을 가진 isLeftChild를 사용한다

 

 

레드블랙트리 코드 

 

//레드블랙트리 클래스
public class RedBlackTree<K, V> implements RedBlackI<K, V> }
Node<K, V> root;
int size;
public Node<K, V> {
K key;
V value;
Node<K, V> left, right, parent; //부모가 null이면 root노드이다 
boolean isLeftChild, black;
public Node(K key, V value) { //생성자를 정의할 때는 제네릭 x
this.key = key;
this.value = value;
left = right = parent = null; //노드 초기화
black = false;
isLeftChild = false;
}

//add 메서드
public void add(K key, V value) {
Node<K, V> node = new Node<K, V>(key, value);
if(root == null) {
root = node;
root.black = true;
size++;
return;
}
add(root, node) // 트리에 노드가 있을 경우 재귀 메소드 사용
size++;
}

// add 재귀함수, 내부클래스
public void add(Node<K, V> parent, Node<K, V> newNode) {

//추가할 노드와 현재 노드의 크기 비교
If(((Comparable<K>)newNode.key).compareTo(parent.key) > 0) {
If(parent.right == null) { //오른쪽 노드
parent.right = newNode;
newNode.parent = parent;
newNode.isLeftChild = false;
}
return add(parent.right, newNode);
}
If(parent.left == null) { //왼쪽 노드
parent.left = newNode;
newNode.parent = parent;
newNode.isLeftChild = true;
return;
}
return add(parent.left, newNode);
checkColor(newNode); // 레드 블랙 트리가 규칙에 맞게 잘 되어있는지 확인
}

 

 

트리를 조작할 때의 규칙
노드의 이모노드가 black이고 boolean이 true이면 회전시킨다
회전을 할 때 조부모의 왼쪽 자식의 왼쪽 서브트리에서 문제가 발생했다면
우측 회전을 하면 된다

문제가 발생한 지점이 오른쪽 트리인 경우에는 좌측 회전을 한다
-> 다른 트리의 회전 규칙과 똑같다