티스토리 뷰
AVL 트리
AVL 트리란?
: AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다.
: AVL 트리에서는 왼쪽과 오른쪽의 높이 차이가 항상 1보다 작거나 같아야 합니다.
* 트리
1. 이진트리 : 모든 노드들이 둘 이하(0,1,2 개)의 자식을 가진 트리이다.
2. 이진탐색트리 : 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리이다.
3. 정 이진트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
4. 완전 이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다.
1 ) AVL의 노드
class Node<T>{
T data;
Node<T> left;
Node<T> right;
Node<T> parent;
// 생성자
public Node(T obj){
data = obj;
parent = left = right = null;
}
2) add 메소드
// AVL 클래스의 생성자
public AVLTree(){
root = null;
currentSize = 0;
}
// add 메소드
public void add(E obj){
Node<E> node = new Node<E>(obj);
// 트리가 비어있을 경우
if (root == null){
root = node;
currentSize++;
return;
}
// 트리에 노드가 있을 경우 add 메소드를 재귀로 호출
add(root, node);
}
3) 재귀 add 메소드
// newNode의 data가 parent의 data보다 크면 트리의 오른쪽에 추가하면 됩니다.
if (((Comparable<E>)newNode.data.compareTo(parent.data)>0{
if (parent.right == null){
parent.right = newNode;
newNode.parent = parent;
currentSize++;
}
else
add(parent.right, newNode);
// newNode의 data가 parent의 data보다 작거나 같으면 트리의 왼쪽에 추가하면 됩니다.
else{
if (parent.left == null){
parent.left = newNode;
newNode.parent = parent;
currentSize++;
}
else
add(parent.left, newNode);
// AVL트리가 규칙에 맞게 잘 되어있는지 확인합니다.
checkBalance(newNode);
}
4) 균형 확인 메소드
: AVL 트리에서는 왼쪽과 오른쪽의 높이 차이가 항상 1보다 작거나 같아야 합니다.
: 따라서, 노드를 추가하였을 때 높이의 차이가 1보다 커지면 회전을 하여 트리의 균형을 맞춰주어야 합니다.
public void checkBalance(Node<E> node){
// 높이 차이가 1 초과 혹은 -1 미만 (AVL 트리 규칙 위반)
if ((height(node.left) - height(node.right)>1) || (height(node.left) - height(node.right)<-1)){
rebalance(node);
// 부모 노드를 계속 확인해서 루트까지 갑니다.
if (node.parent == null)
return;
checkBalance(node.parent);
}
5) Rebalance 메소드
public void rebalance(Node<E> node){
// 왼쪽 자식 > 오른쪽 자식
if (height(node.left) - height(node.right)>1) {
if(height(node.left.left) > height(node.left.right)) // 왼쪽 서브 트리 > 오른쪽 서브 트리
node = rightRotate(node); // 우측 회전
else // 왼쪽 서브 트리 < 오른쪽 서브 트리
node = leftRightRotate(node); // 좌측-우측 회전
}
// 왼쪽 자식 < 오른쪽 자식
else{
if(height(node.left.left) > height(node.left.right)) // 왼쪽 서브 트리 > 오른쪽 서브 트리
node = rightLeftRotate(node); // 우측-좌측 회전
else // 왼쪽 서브 트리 < 오른쪽 서브 트리
node = leftRotate(node); // 좌측 회전
}
// 루트로 올 때까지 반복합니다.
if (node.parent == null)
root=node;
}
6) adding data 예제
: 위 사진은 지금까지 만든 add 메소드를 활용하여 43에 18, 22, 9, 21, 6, 8, 20, 63, 50, 62, 51을 순서대로 추가한 결과입니다.
: 먼저 트리의 규칙에 따라 내려가 잎에 새로운 데이터를 추가합니다. 그리고 균형이 깨졌는지 확인하고 회전을 하여 균형을 유지합니다.
RB Tree ( Red Black Tree)
레드 블랙 트리란?
: 자가 균형 이진 탐색 트리로서, AVL 트리처럼 스스로 균형을 잡는 트리입니다.
: 레드 블랙 트리에서는 다음의 규칙에 따라 정렬하여 균형을 맞춥니다.
규칙!
1. 모든 노드는 빨간색이나 검은색입니다.
2. 루트는 항상 검은색입니다.
3. 새로 추가되는 노드는 항상 빨간색입니다.
4. 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 합니다.
5. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어서는 안 됩니다.
6. 모든 빈 노드는 검은색이라고 가정합니다.
균형을 맞추는 방법
1) 이모 노드가 검은색일 경우
회전을 합니다. 회전을 하고 나면 부모 노드는 검은색, 두 자식 노드는 빨간색이 되어야 합니다.
2) 이모 노드가 빨간색일 경우
색상 전환을 합니다. 색상 전환을 하고 나면 부모 노드는 빨간색, 두 자식 노드는 검은색이 되어야 합니다.
*예제
1~10까지의 숫자들을 레드 블랙 트리 규칙에 따라 배열하면 위 사진과 같이 나타납니다.
1부터 숫자들을 하나씩 추가하면서 규칙에 적합한지 확인해주면 됩니다.
규칙을 위반하면 회전과 색상 전환으로 규칙에 맞게 바꾸어 줍니다.
1) 클래스
: 불리언 값을 가진 black로 참이면 검은색, 거짓이면 빨간색을 표시합니다.
: 이모 노드를 알아내기 위해 left, right, parent 노드를 가리키는 포인터뿐만 아니라 불리언 값을 가진 isLeftChild를 사용합니다.
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;
}
}
}
2) add 메소드
: add 메소드의 동작 방식은 AVL 트리와 동일합니다. 단, isLeftChild가 추가되기 때문에 이를 고려해주어야 합니다.
: 트리가 비어있으면 노드를 추가하고 비어있지 않다면 재귀 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){
if(parent.right == null){
parent.right = newNode;
newNode.parent = parent;
newNode.isLeftChild=false;
return;
}
return add(parent.right, newNode);
// newNode의 data가 parent의 data보다 작거나 같으면 트리의 왼쪽에 추가하면 됩니다.
if (parent.left == null){
parent.left = newNode;
newNode.parent = parent;
newNode.isLeftChild=true;
return;
}
return add(parent.left, newNode);
// 레드 블랙 트리가 규칙에 맞게 잘 되어있는지 확인합니다.
checkColor(newNode);
}
3) 색상 확인 메소드
: 검은색 이모노드가 있다면 로테이트 해준다.
: 빨간색 이모노드가 있다면 color flip 해준다.
public void checkColor(Node<K,V> node){
// 루트는 항상 검은색이므로 색을 확인할 필요가 없습니다.
if (node == root)
return;
// 빨간 노드 2개가 연속으로 나오는 경우 (레드 블랙 트리 규칙 위반)
if (!node.black && !node.parent.black){
correctTree(node);
// 부모 노드를 계속 확인합니다.
checkColor(node.parent);
}
public void correctTree(Node<K,V> node){
// 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;
}
// 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;
}
4) 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;
}
// 부모 노드가 오른쪽 자식
// 조부모 노드를 우측-좌측 회전
rightleftRotate(node.parent.parent);
node.black = true;
node.right.black = false;
node.left.black = false;
return;
}
// 현재 노드가 오른쪽 자식일 경우에도 부모 노드의 위치에 따라 좌측 회전, 좌측-우측 회전을 합니다.
else {
...
}
}
5) 좌측회전
: 레드 블랙 트리에서 좌측 회전을 하는 코드는 다음과 같습니다.
: 힙 & 트리에서 배운 좌측 회전 코드와 유사합니다.
: 다만, parent 노드를 가리키는 포인터와 isLeftChild 변수를 추가로 사용하기 때문에 이들을 고려해주어야 합니다.
// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
public void leftRotate (Node<K,V> node){
Node<K,V> temp = node.right;
node.right = temp.left;
// 부모 노드 node.right가 temp가 되면서 조부모 노드가 없어집니다.
if(node.right != null) {
node.right.parent = null;
node.right.isLeftChild = false;
}
// node가 루트인 경우
if(node.parent == null) {
root = temp;
temp.parent = null;
}
// node가 루트가 아닌 경우
else {
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;
}
}
6) 좌측 - 우측 회전
: 레드 블랙 트리에서 좌측-우측 회전을 하는 코드는 다음과 같습니다.
: 힙 & 트리에서 배운 내용과 동일합니다.
// 좌측 회전 후 우측 회전
public void leftRightRotate(Node<K,V> node){
leftRotate(node.left);
rightRotate(node);
}
7) 높이 구하기
public int height() {
if(root == null)
return 0;
return height(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;
}
8) 검은색 노드 개수
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
// or fix the tree
// 검은색 노드이면 해당 노드의 수를 늘려줍니다.
if (node.black)
leftBlackNodes++;
return leftBlackNodes;
}'자료구조' 카테고리의 다른 글
| 6. 정렬 (Sort) (0) | 2024.05.12 |
|---|---|
| 4. 힙(HEAP) & 트리(Tree) (0) | 2024.04.20 |
| 3. 해시(Hash) (0) | 2024.04.14 |
| 2. 선형 자료구조(연결 리스트&배열) (0) | 2024.04.14 |
| 1. 자료구조 기본 및 자바 특성 (0) | 2024.04.14 |
