TIL 정리_92(레드블랙트리(2))

https://www.boostcourse.org/cs204

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

 

 

레드 블랙 트리

색상 변환 -> 노드의 색을 바꾸는 것 
색상변환을 하면 부모, 이모노드는 검은색 조부모 노드는 빨간색이 된다
회전을 하고나면 부모, 이모노드는 빨간색 조부모 노드는 검은색이 된다

레드 블랙 트리에서는 트리를 생성한 후 트리의 색을 파악하여
규칙을 어긴 것이 있는 지 확인한다
이때 해당 노드의 조부모 노드를 고쳐야한다 해당 노드를 고치는것이 아니다

 

 

레드 블랙 트리 코드

public void checkColor(Node<K, V> node) {
if(node == root) return;
if(!node.black && !node.parent.black)
//메서드를 호출하여 이모 노드의 색깔을 파악한다
correctTree(node); 
//노드를 추가할 때마다 오류가 없는지 확인
checkColor(node.parent);
}
//correctTree 메서드 정의 
public void correctTree(Node<K, V> node) {
//이모 노드의 색 확인, 빈 노드는 검은색이다
if(node.parent.isLeftChild) {
if(node.parent.parent.right == null || node.parent.parent.right.black)
return rotate(node);

if(node.parent.parent.right != null) //회전을 하지 않는 경우
node.parent.parent.right.black = true;
node.parent.parent.black = false;
node.parent.black = true; //색상 변환
return;
}
//이모 노드가 조부모 노드의 왼쪽 자식인 경우 
else {
if(node.parent.parent.left == null || node.parent.parent.left.black)
return rotate(node);

if(node.parent.parent.left != null) //회전을 하지 않는 경우
node.parent.parent.left.black = true;
node.parent.parent.black = false;
node.parent.black = true; //색상 변환
return;
}

 

 

• 레드 블랙 트리의 rotate 메서드

public void rotate(Node<K, V> node) {
if(node.isLeftChild) {
if(node.parent.isLeftChild) {
rightRotate(node.parent.parent); //우측 회전
node.black = false;
node.parent.black = true;
if(node.parent.parent != null) 
node.parent.right.black = false;
return;
}
rightLeftRotate(node.parent.parent); //조부모 노드 우측-좌측 회전 
node.black = true;
node.right.black = false;
node.left.black = false;
return;
}

//좌측 회전을 하는 코드 
public void leftRotate(Node<K, V> node) {
Node<K, V> temp = node.right;
node.right = temp.left;
//부모 노드의 포인터를 고쳐야 한다 
  if(node.right != null) {
node.right.parent = node;
node.right.isLeftChild = false;
}
if(node.parent == null) { // node가 루트인 경우
root = temp;
temp.parent = null;
} else { // node가 루트가 아닌 경우
temp.parent = node.parent;
if(node.isLeftChild) {
temp.isLeftChild = true;
temp.parent.left = temp;
} else {
temp.isLeftChild = false;
temp.parent.right = temp;
}
temp.left = node; //좌측 회전 코드 
node.isLeftChild = true;
node.parent = temp;
}
}
좌측 - 우측 회전
-> 한번에 할 수 없다 
public void leftRightRotate(Node<K, V> node) {
leftRotate(node.left); //좌측 회전
rightRotate(node); //우측 회전 
}

 

 

• 트리에서의 높이 계산

public int height() {
if(root == null) return 0;
 return height(root) -1; 
//잎 노드에서 null값인 자식 노드를 호출하여 +1이 되기때문에 root에서 -1을 해야한다 
}
public int height(node<K, V> node) {
if(node == null) return 0;
int leftheight = height(node.left) + 1;
int rightheight = height(node.right) +1;
if(leftheight > rightheight) return leftheight;
return rightheight;
}

 

 

• 트리의 검은색 노드의 개수 구하기 (재귀 메서드 사용)

public int blackNodes(Node<K, V> node) {
if(node == null) 
return 1;
int rightBlackNodes = blackNodes(node.right);
int leftBlackNodes = bloakNodes(node.left);
if(rightblackNodes != leftBlackNodes) 
//검은색 노드 개수가 다르면 에러를 내거나 고친다
if(node.black)
leftBlackNodes++; //검은색 노드인 경우 해당 노드의 수를 늘린다
return leftBlackNodes;
}