지난 포스팅에서는 레드-블랙트리 클래스를 만들었다.
이번에는 레드-블랙트리의 규칙을 만족하는 메소드를 몇가지 만들어보았다.
add 메소드
레드-블랙트리에 요소를 추가할때도 AVL트리와 다름없이 재귀함수를 사용해야한다.
키와 값을 인자로 가지는 public add함수와 현재노드, 추가할 노드를 인자로 가지는 private 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 재귀함수
private void add(Node<K,V> parent, Node<K,V> newNode){
// 새로운 노드의 키와 현재 노드의 키를 비교
// 키와 값이 있는 데이터 구조는 키만 비교하고 값은 신경쓰지 않아도 된다.
// newNode의 data가 parent의 data보다 크면 트리의 오른쪽에 추가
if (((Comparable<K>) newNode.key).compareTo(parent.key) > 0){
// parent가 잎노드가 된 경우
if(parent.right == null){
//새로운 노드를 추가할 곳을 찾았으므로 parent의 자식에 새 노드를 추가
parent.right = newNode;
// 새로운 노드의 부모노드를 parent로 지정
newNode.parent = parent;
// 노드의 방향에 따라 지정
newNode.isLeftChild=false;
return;
}
return add(parent.right, newNode);
// newNode의 data가 parent의 data보다 작거나 같으면 트리의 왼쪽에 추가
// parent가 잎노드가 된 경우
if (parent.left == null){
//새로운 노드를 추가할 곳을 찾았으므로 parent의 자식에 새 노드를 추가
parent.left = newNode;
// 새로운 노드의 부모노드를 parent로 지정
newNode.parent = parent;
// 노드의 방향에 따라 지정
newNode.isLeftChild=true;
return;
}
return add(parent.left, newNode);
// 레드 블랙 트리가 규칙에 맞게 잘 되어있는지 확인
checkColor(newNode);
위와 같이 add 메소드가 완성되었으나 요소를 추가한 이후엔 규칙을 모두 만족했는지 다시 확인해야한다.
규칙이 지켜지지 않았다면 트리를 다시 조작해 노드를 올바른 위치로 옮겨야한다.
아래에서 요소의 규칙을 다시 확인하고 규칙을 확인하는 메소드를 만들어보겠다.
1. 루트는 항상 검정색
트리를 조작한 후에 루트의 색깔을 검정으로 바꿔줘야한다.
2. 새로운 노드는 항상 빨간색
add메소드를 실행하면 black을 false 설정
3. 빈 노드는 검정색
회전과 색상변환에 적용
4. 두개의 빨간색 노드가 연달아 있으면 안된다.
5. 모튼 잎노드부터 루트까지 가는 경로엔 검은 노드의 개수가 같아야한다.
checkColor 메소드
노드의 색이 모두 규칙을 만족하는지 확인해 보겠다.
역시 재귀함수를 사용해서 모든 노드를 탐색하게했다.
public void checkColor(Node<K,V> node){
if (node == root){
return; // 루트는 항상 검은색이므로 색을 확인할 필요가 없다.
}
// 빨간 노드 2개가 연속으로 나오는 경우 (레드 블랙 트리 규칙 위반-> 수정대상)
if (!node.black && !node.parent.black){
correctTree(node); // 문제노드를 인자로 전달
}
// 부모 노드를 계속 확인.
checkColor(node.parent);
}부모와 자식노드의 색이 모두 빨간색인 경우 수정대상이 된다.
다음은 문제가 되는 노드를 인자로 받아서 생성한 메소드이다.
이 메소드는 레드-블랙트리의 다음 규칙을 따라야한다.
1. 문제노드의 이모노드가 검은색인 경우 (즉, 이모노드가 비어있거나 black이 true)
회전
2.문제노드의 이모노드가 빨간색 경우
색상변환
public void correctTree(Node<K,V> node){
// 문제노드의 이모노드가 검은색인지 확인
// node의 부모 노드가 왼쪽 자식이면 이모 노드는 조부모 노드의 오른쪽 자식.
if (node.parent.isLeftChild) {
// node.parent.parent(조부모)의 right -> 이모노드
// 이모 노드가 검은색 (이모 노드가 비어있는 경우 포함, 비어있는 노드는 검정색이므로)
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;
}
// node의 부모 노드가 오른쪽 자식이면 이모 노드는 조부모 노드의 왼쪽 자식.
// 위 코드와 동일하게 하되, 이모 노드를 node.parent.parent.left로 바꾼다.
} 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.right != null) {
node.parent.right.black = false;
}
return;
} else {
// 부모 노드가 오른쪽 자식
// 조부모 노드를 우측-좌측 회전
rightleftRotate(node.parent.parent);
node.black = true;
node.right.black = false;
node.left.black = false;
return;
}
// 현재 노드가 오른쪽 자식
} else {
// 부모 노드가 오른쪽 자식
if (!node.parent.isLeftChild) {
// 조부모 노드를 좌측회전
leftRotate(node.parent.parent);
node.black = false; // 현재노드 빨간색
node.parent.black = true; // 부모노드 검정색
// 현재노드의 형제노드가 있다면 형제 노드도 빨강색
if (node.parent.left != null) {
node.parent.left.black = false;
}
return;
} else {
// 부모 노드가 왼쪽 자식
// 조부모 노드를 좌측-우측 회전
leftrightRotate(node.parent.parent);
node.black = true;
node.left.black = false;
node.right.black = false;
return;
}
}
}
leftRotate 메소드
레드-블랙 트리에서 좌측회전을 하는 경우는 다음과 같다.
힙-트리 회전과 유사하지만 parent 노드를 가리키는 포인터와 isLeftChild 변수가 추가되었다.
조부모노드를 이용해야하기 때문에 임시 노드를 사용했다.
인자로 받아오는 노드는 문제가 되는 노드의 조부모 노드이다.
// 좌측 회전 : 조부모 노드를 부모 노드의 왼쪽 자식 노드로 이동.
public void leftRotate (Node<K,V> node){
// 부모노드(node.right)를 가르키는 임시 노드 생성
Node<K,V> temp = node.right;
// 부모노드를 임시 노드의 왼쪽자식으로 설정
node.right = temp.left;
// 부모 노드(node.right)가 temp가 되면서 조부모 노드가 없어진다.
if(node.right != null) {
// 부모 노드의 포인터 갱신
node.right.parent = node;
node.right.isLeftChild = false;
}
// node.right위에 부모노드가 더 있는지 확인
// node가 루트인 경우
if(node.parent == null) {
// 전역변수 root 포인터가 temp를 가르킴.
root = temp;
temp.parent = null;
// node가 루트가 아닌 경우
} else {
// 임시 노드의 parent 포인터가 node.paren를 가르키게함.
temp.parent = node.parent;
// node가 왼쪽 자식이었다면 temp도 왼쪽 자식이 되어야함
if(node.isLeftChild) {
temp.isLeftChild = true;
temp.parent.left = temp;
// node가 오른쪽 자식이었다면 temp도 오른쪽 자식이 되어야함
} else {
temp.isLeftChild = false;
temp.parent.right = temp;
}
temp.left = node;
node.isLeftChild = true;
node.parent = temp;
}
}leftRightRotate 메소드
// 좌측 회전 후 우측 회전
public void leftRightRotate(Node<K,V> node){
leftRotate(node.left);
rightRotate(node);
}height 메소드
트리의 높이는 왼쪽, 오른쪽 중 가장 긴 경로의 길이 이다.
정수를 반환하는 메소드와 정수를 반환하고 노드를 인자로 가지는 메소드 두가지 메소드를 만들었다.
public int height() {
if(root == null){
return 0;
}
return height(root) - 1;
}트리가 비어있는 경우 높이는 0이므로, 트리가 비어있지 않는 경우에만 트리의 높이를 구하면 된다.
노드의 높이는 노드의 개수가 아니라 간선의 개수를 의미한다.
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;
}재귀 함수를 반복하면서 왼쪽 자식의 노드가 null인 곳에 도착해 0이 반환되면 왼쪽 자식의 높이를 구할 수 있다.
이어서 오른쪽 자식도 0이 반환될 때까지 재귀 함수를 반복하고 0이 반환되면 오른쪽 자식의 높이를 구할 수 있다.
그중 더 긴 값이 트리의 높이가 된다.
blackNodes 메소드
검은색 노드의 개수를 구하는 메소드이다.
인자로 주어진 노드부터 그 아래에 있는 검은 노드의 개수를 계산하면 된다.
오른쪽과 왼쪽을 따라내려가면서 검은 노드를 세되, 주의해야 할 점은 레드-블랙 트리의 규칙 중 빈 노드는 검정색이라는 규칙이다.
빈 노드를 만나면 더 이상 내려갈 필요가 없으므로, 1을 반환해주면 된다.
public int blackNodes(Node<K,V> node) {
if (node == null){
return 1;
}
int rightBlackNodes = blackNodes(node.right)
int leftBlackNodes = blackNodes(node.left)
// 오른쪽과 왼쪽의 검은색 노드 개수가 다르면 에러를 내거나 고쳐줍니다.
if (rightBlackNodes != leftBlackNodes){
// throw an error
}
// 검은색 노드이면 해당 노드의 수를 늘려줍니다.
if (node.black){
leftBlackNodes++;
}
return leftBlackNodes;
}