Dynamic Sets (계속 추가될 예정 )

Dynamic Set?

 

Dynamic Set( 동적 집합 )이란 집합의 요소들이 계속해서 변화하는 집합입니다.

 

Dynamic Set의 자료구조는 여러개가 존재합니다.

• BST : 이진 탐색 트리
• AVL Tree : 균형잡힌 이진 탐색 트리
• 2-3 Tree
• Red-Black Tree
• Splay Tree
• ....?

 

동적 집합에서 몇몇의 쿼리와 수정 연산자를 지원하며, 모두 O(log n)의 시간복잡도를 가져야합니다.

 

• Search(S, k) : S 내에서 key가 k의 값을 가지는 원소 탐색
• Minimum(S) : S 내에서 key값이 가장 작은 값을 가지는 원소 
• Maximum(S) : S 내에서 key값이 가장 큰 값을 가지는 원소
• Successor(S, x) : S 내에서 x의 key 값을 가지는 원소의 다음 원소. 
• Predecessor(S, x) : S 내에서 x의 key 값을 가지는 원소의 이전 원소.
• Insert(S, x) : S에 x 삽입.
• Delete(S, x) : S에서 x 삭제.

 

 

BST( Binary Search Tree )

 

동적 집합을 처리하는 가장 기본적인 자료구조로 다음과 같은 구조를 지니고 있습니다.

 

 

이진 탐색 트리의 기본적인 성질은 특정 노드의 key값은 해당 노드의 왼쪽 서브트리의 모든 Key 값들보다 같거나 커야하며, 오른쪽 서브트리의 모든 Key값보다 작거나 같아야합니다.

 

그렇기 때문에 중위순회를 사용해 순회를 하게되면 정렬된 배열이 나타나게 됩니다.

 

 

BST 예시

 

위 BST를 중위순회하여 나타내면 [ 1, 2, 3, 4, 5, 6 ] 으로 정렬되어 있는 것을 확인할 수 있습니다.

 

 

 

 

한쪽 방향으로 편향된 구조의 트리가 만들어질 수 있으며, 그럴 경우 탐색하는데 노드의 개수만큼 시간이 걸린다.

 

 

Node 구조체

typedef struct Node {
	int key;
	Node* Left = NULL;
	Node* Right = NULL;
	Node* Parent = NULL;
};

 

 

 

Search(S, k)

Node* Search(Node *node, int key) {
	if (node == NULL || node->key == key) {
		return node;
	}// 빈 집합이거나 루트의 key값이 찾는 값일 때
	else if (node->key > key) {
		return Search(node->Left, key);
	}// 찾는 key값이 현재 노드의 값보다 작거나 경우
	else {
		return Search(node->Right, key);
	}// 찾는 key값이 현재 노드의 값보다 큰 경우
}

 

 

Mininum(S)

Node* Minimum(Node* node) {
	while (node->Left != NULL) {
		node = node->Left;
	}
	return node;
}

 

 

Maximum(S)

Node* Maximum(Node* node) {
	while (node->Right != NULL) {
		node = node->Right;
	}
	return node;
}

 

 

Successor(S, x)

Node* Successor(Node* node, int key) {
	if (node->Right != NULL) {
		node = node->Right;
		while (node->Left != NULL) {
			node = node->Left;
		}
		return node;
	}
    
    while(node->Parent != NULL && node->Parent->Left != node){
    	node = node->Parent;
    }// 노드의 부모노드가 존재하면서, 현재 노드가 부모노드의 왼쪽 서브트리의 노드일 때까지 반복 
	return node;
}

x의 바로 다음 노드를 찾는 함수입니다.

BST의 경우 중위순회하면 정렬되어있는 배열을 반환하기 때문에 x의 값보다 크면서 제일 작은 key값의 노드를 반환해야합니다.

 

첫번째 if문의 부분을 잘 보면 Minimum과 중복되는 연산을 확인할 수 있으므로 수정이 가능합니다.

 

Node* Successor(Node* node, int key) {
	if (node->Right != NULL) {
		return Minimum(node->Right);
	}
	
    while(node->Parent != NULL && node->Parent->Left != node){
    	node = node->Parent;
    }// 노드의 부모노드가 존재하면서, 현재 노드가 부모노드의 왼쪽 서브트리의 노드일 때까지 반복 
	return node;
}

 

 

Predecessor(S, x)

Node* Predecessor(Node* node, int key) {
	if (node->Left != NULL) {
		return Maximum(node->Left);
	}

	while (node->Parent != NULL && node->Parent->Right != node) {
		node = node->Parent;
	}
	return node;
}

 

Successor와 거의 동일하나 방향이 반대인 경우입니다.

key값이 x보다 작되, 그 중에서 제일 큰 노드를 반환해야합니다.

 

 

 insert(S, x)

void insert(Node* node, int key) {
	while (1) {
		if(node->key < key && node->Right != NULL)
			node = node->Right;
		else if (node->key > key && node->Left != NULL) {
			node = node->Left;
		}
		else {
			break;
		}
	}

	Node* E = (Node*)malloc(sizeof(Node));;
	E->key = key;
	E->Left = E->Right = NULL;
	E->Parent = node;

	if (node->key > key) {
		node->Left = E;
	}
	else {
		node->Right = E;
	}
}

 

 

 

Delete(S, x)

void Delete(Node* node, int key) {
	
	Node* root = node;

	// key값의 노드 찾기.
	while (node->key != key) {
		if (node->key > key) {
			node = node->Left;
		}
		else {
			node = node->Right;
		}
	}

	switch (Children(node)) {
	case 0:
		if (node->Parent->Left == node) {
			node->Parent->Left = NULL;
		}
		else {
			node->Parent->Right = NULL;
		}

		free(node);
		break;
	case 1: // 왼쪽 자식만 존재
		if (node->Parent->Left == node) {
			node->Parent->Left = node->Left;
			node->Left->Parent = node->Parent;
		}
		else {
			node->Parent->Right = node->Left;
			node->Left->Parent = node->Parent;
		}

		free(node);
		break;
	case 2: // 오른쪽 자식만 존재
		if (node->Parent->Left == node) {
			node->Parent->Left = node->Right;
			node->Right->Parent = node->Parent;
		}
		else {
			node->Parent->Right = node->Right;
			node->Right->Parent = node->Parent;
		}

		free(node);
		break;
	default: // 양쪽 자식 모두 존재
		Node* successor = Successor(node, node->key);
		int tmp = successor->key;
		successor->key = node->key;
		node->key = tmp;

		Delete(successor, successor->key);
		break;
	}

}

삭제할 노드의 자식노드가 존재하지 않는경우.

삭제할 노드의 자식노드가 한 개인 경우.

삭제할 노드의 자식노드가 두 개인 경우를 모두 생각해 줘야합니다.

 

자식노드의 개수에 따라서

존재하지 않는 경우, 부모노드와의 관계를 끊고 그 노드를 삭제하며

한 개인 경우, 그 자리를 자식노드로 교체하며

두 개의 경우, Successor와 자리를 교체하고 삭제하면 됩니다. 

 

 

#include<iostream>
#include<stdlib.h>
using namespace std;

int counter = 0;

typedef struct Node {
	int key;
	Node* Left;
	Node* Right;
	Node* Parent;
};

Node* makeNode(int key) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->key = key;
	node->Left = node->Right = node->Parent = NULL;
	return node;
}

Node* Search(Node *node, int key) {
	if (node == NULL || node->key == key) {
		return node;
	}// 빈 집합이거나 루트의 key값이 찾는 값일 때
	else if (node->key > key) {
		return Search(node->Left, key);
	}// 찾는 key값이 현재 노드의 값보다 작거나 경우
	else {
		return Search(node->Right, key);
	}// 찾는 key값이 현재 노드의 값보다 큰 경우
}

Node* Minimum(Node* node) {
	while (node->Left != NULL) {
		node = node->Left;
	}
	return node;
}

Node* Maximum(Node* node) {
	while (node->Right != NULL) {
		node = node->Right;
	}
	return node;
}

Node* Successor(Node* node, int key) {
	if (node->Right != NULL) {
		return Minimum(node->Right);
	}
	
	while (node->Parent != NULL && node->Parent->Left != node) {
		node = node->Parent;
	}// 노드의 부모노드가 존재하면서, 현재 노드가 부모노드의 왼쪽 서브트리의 노드일 때까지 반복 

	return node;
}

Node* Predecessor(Node* node, int key) {
	if (node->Left != NULL) {
		return Maximum(node->Left);
	}

	while (node->Parent != NULL && node->Parent->Right != node) {
		node = node->Parent;
	}
	return node;
}

void insert(Node* node, int key) {
	
    while (1) {
		if(node->key < key && node->Right != NULL)
			node = node->Right;
		else if (node->key > key && node->Left != NULL) {
			node = node->Left;
		}
		else {
			break;
		}
	}

	Node* E = makeNode(key);
	E->Parent = node;

	if (node->key > key) {
		node->Left = E;
	}
	else {
		node->Right = E;
	}
}

int Children(Node* node) {
	int ret = 0;
	if (node->Left != NULL) ret++;
	if (node->Right != NULL) ret += 2;
	return ret;
}

void Delete(Node* node, int key) {
	
	Node* root = node;

	// key값의 노드 찾기.
	while (node->key != key) {
		if (node->key > key) {
			node = node->Left;
		}
		else {
			node = node->Right;
		}
	}

	switch (Children(node)) {
	case 0:
		if (node->Parent->Left == node) {
			node->Parent->Left = NULL;
		}
		else {
			node->Parent->Right = NULL;
		}

		free(node);
		break;
	case 1: // 왼쪽 자식만 존재
		if (node->Parent->Left == node) {
			node->Parent->Left = node->Left;
			node->Left->Parent = node->Parent;
		}
		else {
			node->Parent->Right = node->Left;
			node->Left->Parent = node->Parent;
		}

		free(node);
		break;
	case 2: // 오른쪽 자식만 존재
		if (node->Parent->Left == node) {
			node->Parent->Left = node->Right;
			node->Right->Parent = node->Parent;
		}
		else {
			node->Parent->Right = node->Right;
			node->Right->Parent = node->Parent;
		}

		free(node);
		break;
	default: // 양쪽 자식 모두 존재
		Node* successor = Successor(node, node->key);
		int tmp = successor->key;
		successor->key = node->key;
		node->key = tmp;

		Delete(successor, successor->key);
		break;
	}

}


void inorder(Node* node, int tab) {
	if (node->Left != NULL) {
		inorder(node->Left, tab + 1);
	}

	int i = 0;
	while (i < tab) {
		cout << "\t";
		i++;
	}

	cout << node->key << '\n';

	if (node->Right != NULL) {
		inorder(node->Right, tab + 1);
	}
}

int main() {
	Node* root = makeNode(3);


	insert(root, 5);
	insert(root, 1);
	insert(root, 6);
	insert(root, 8);
	insert(root, 7);
	insert(root, 2);
	insert(root, 4);



	inorder(root, 0);

	Delete(root, 6);


	inorder(root, 0);
	
	return 0;
}

 

 

 

AVL 트리

BST의 시간복잡도를 완화시키기 위하여 고안된 트리.

스스로 균형을 잡는 BST이며, 양쪽 서브트리의 높이차이가 최대 1인 트리를 의미한다.

 

 

 

RBT ( Red - Black 트리 )

 

연산자들의 시간복잡도가 O(log n)이 되도록 균형 있게 만들어진 트리.

 

기본적으로 BST이며, 5가지 제약이 존재한다.

 

1. 각 노드는 Red 또는 Black의 색을 가진다.
2. 리프노드에 NULL로 표시되는 단말노드가 존재하며 그 노드는 Black이다.
3. 어떤 노드가 Red이면 그 자식 노드는 Black 이여야한다.
4. 어떤 노드로부터 이 노드의 단말노드까지의 경로는 같은 개수의 Black노드를 가진다.
5. 루트노드는 Black 이다.

 

삽입, 삭제연산 수행 시에 5가지 조건을 맞춰줘야 하므로, 생각하기 좀 까다로울 수 있다.

 

 

 

출처 : 위키백과

위 이미지에서 루트노드인 13을 기준으로 모든 단말노드까지의 black노드의 개수가 4임을 확인할 수 있으며, 나머지 노드를 기준으로 하더라도 단말노드까지의 Black노드의 개수가 같음을 확인할 수 있다.

 

 

 

Rotate ( 회전 ) 

 

삽입 또는 삭제연산에서 노드의 위치를 변경시킬 때 사용되는 연산이다.

 

 

오른쪽 회전연산을 수행하면 위와 같이 서브트리의 위치가 변화하며

 

 

 

왼쪽 회전연산을 수행하면 이렇게 서브트리의 위치가 이동된다.

 

 

Node* LeftRotate(Node* now) {
	// 내 부모노드를 우측노드의 부모노드로 만듬
	now->Right->Parent = now->Parent;

	if (now->Parent != NULL) {
		if (now->Parent->Right == now) {
			now->Parent->Right = now->Right;
		}
		else {
			now->Parent->Left = now->Right;
		}
	}
	// 내 부모노드를 오른쪽에 있던 노드로 만듬
	now->Parent = now->Right;

	// 내 오른쪽 노드를 부모 노드의 왼쪽 노드로 만듬
	now->Right = now->Parent->Left;

	if (now->Right != NULL) {
		// 내 오른쪽 노드의 부모를 나로 갱신
		now->Right->Parent = now;
	}

	// 내 부모노드의 왼쪽 방향을 나로 갱신
	now->Parent->Left = now;

	return now;
}

Node* RightRotate(Node* now) {
	// 내 부모노드를 왼쪽노드의 부모노드로 바꿈
	now->Left->Parent = now->Parent;

	if (now->Parent != NULL) {
		if (now->Parent->Right == now) {
			now->Parent->Right = now->Left;
		}
		else {
			now->Parent->Left = now->Left;
		}
	}
	// 내 부모노드를 왼쪽에 있던 노드로 변경
	now->Parent = now->Left;

	// 내 왼쪽 노드를 부모노드의 오른쪽 노드로 만듬
	now->Left = now->Parent->Right;

	if (now->Left != NULL) {
		// 내 왼쪽 노드의 부모를 나로 갱신
		now->Left->Parent = now;
	}

	// 내 부모노드의 오른쪽 방향을 나로 갱신
	now->Parent->Right = now;

	return now;
}

 

Insertion ( 삽입 )

 

BST처럼 삽입을 하되, 첫 색깔을 빨간색으로 주고 RBT의 조건을 만족하도록 조정해주는 과정을 거친다.

 

삽입된 노드의 부모노드 색깔에 따라 취해줘야하는 작업이 달라진다.

 

먼저 검정색일 경우, RBT의 규칙이 깨지지않으므로 별다른 작업을 취해줄 필요가 없으며

빨간색인 경우 부모노드의 형제노드 색상을 고려해 주어야한다.

 

모든 조건에 부합되는 RBT의 경우 어떠한 노드의 색이 빨간색이라면 그 부모노드는 반드시 검정색이며, 형제노드는 검정 또는 빨간색일 수 있다.

 

 

이미지로 표현하면 위의 3가지 경우가 존재하는데, 왼쪽부터 1번이라고 가정하여 생각해보자.

 

1번.

부모노드와 형제노드의 색을 모두 검정색으로 만들어주고, 부모노드의 부모노드, 즉., 삽입된 노드의 조부모노드의 색을  빨간색으로 바꿔준 다음, 바뀐 조부모 노드를 기준으로 다시 RBT의 조건에 부합하는지 판단해야한다.

 

 

2번.

삽입된 노드의 부모노드와 조부모노드의 색깔을 바꾼 따음, 조부모노드를 기준으로 오른쪽 회전연산을 수행해야하며. 이 경우 더이상 조건을 맞춰줄 필요가 없다.

 

 

3번.

삽입된 노드의 부모노드를 기준으로 왼쪽 회전연산을 하고, 원래 부모노드였던 노드를 기준으로 다시 1~3번 조건을 맞춘다.

 

 

 

만약, 삽입된 노드의 위치가 오른쪽 서브트리인 경우에는 회전연산을 반대로 해주면 된다.

 

 

 

Node* RBTinsert(Node* node, int key) {
	Node* now = insert(node, key);

	while (now->Parent != NULL && now->Parent->color == 'R') {
		Node* p = now->Parent;
		if (p->Parent->Left == p) { 
			// 부모노드 위치가 왼쪽인 경우
			Node* uncle = p->Parent->Right;
			if (uncle == NULL || uncle->color == 'B') {
				// 형제노드가 BLACK
				if(p->Right == now){
					now = LeftRotate(p);
				}

				now->Parent->color = 'B';
				now->color = 'R';
				now->Parent->Parent->color = 'R';
				now = RightRotate(now->Parent->Parent);

			}
			else {
				// 형제노드가 RED
				now = p->Parent;
				now->color = 'R';
				now->Left->color = now->Right->color = 'B';
			}
		}
		else { 
			// 부모노드 위치가 오른쪽인 경우
			Node* uncle = p->Parent->Left;
			if (uncle == NULL || uncle->color == 'B') {
				if (p->Left == now) {
					now = RightRotate(p);
				}

				now->Parent->color = 'B';
				now->color = 'R';
				now->Parent->Parent->color = 'R';
				now = LeftRotate(now->Parent->Parent);
			}
			else {
				now = p->Parent;
				now->color = 'R';
				now->Left->color = now->Right->color = 'B';
			}
		}
	}

	if (node->Parent != NULL) {
		node = node->Parent;
	}
	node->color = 'B';
	return node;
}

 

 

Deletion ( 삭제 )

 

삭제의 경우도 삽입과 마찬가지로 BST와 동일하게 동작하고나서 색깔을 맞춰주는 작업을 해야한다.

 

먼저 삭제된 노드의 색이 빨간색이라면, 따로 조건에 어긋나는 경우가 발생하지 않으므로 그냥 작업을 종료해주면 된다.

 

 

그럼 삭제된 노드의 색이 검정색이라고 생각하고 어떻게 동작해야하는지 생각해보자.

 

앞서 BST에서 삭제될 노드의 자식이 두개라면 삭제될 노드의 Successor와 현재 노드의 위치를 바꾼다고 배웠는데, RBT의 경우 마찬가지로 위치를 바꾸되 Successor의 위치로 변경된 노드를 기준으로 작업을 수행한다.

 

 

이렇게 되면 결국 색을 맞춰주는 작업을 수행할때, 노드의 자식의 개수는 0개 또는 1개가 된다.

(Successor의 자식이 2개일 수가 없다.)

 

이 자식노드를 삭제된 노드의 위치로 올리고 해당 노드의 형제노드의 색과 부모노드의 색에 따라 작업을 결정해준다.

 

( 여기서 올라온 자식노드를 A라고 부르겠습니다. )

 

 

 

 

 

1. 형제노드가 빨간색일 경우.

 

형제노드가 빨간색이므로, 부모노드는 자연스럽게 검정색이 됩니다. 

형제노드와 부모노드의 색깔을 서로 바꾼다음 부모노드를 기준으로 삽입된 노드의 방향으로 회전연산을 수행합니다.

 

 

 

 

 

2. 형제노드가 검정색이면서 형제노드의 자식노드들도 모두 검정색인 경우.

 

형제노드의 색을 빨간색으로 변경하고 부모노드에 검은색을 입힙니다.

이때, 부모노드가 가지고있던 색깔에 따라 해줘야하는 작업이 조금 달라집니다.

 

부모노드가 만약 빨간색이었다면 그냥 검정색으로 바꿔주고 작업을 종료합니다.

반면에 부모노드가 검정색인 경우에는 이 부모노드를 새로운 기준노드로 삼고 색을 맞춰주는 작업을 계속해서 수행합니다.

 

 

 

3. 형제노드가 검정색이면서 형제노드의 자식노드 중 하나가 빨간색인 경우

 

빨간색을 띄는 자식노드의 방향에 따라 추가적인 작업을 해줘야 합니다.

 

빨간색을 띄는 자식노드가 A노드 방향일 경우, 형제노드와 색을 서로 변경하고 형제노드를 기준으로 A의 반대쪽으로 회전연산을 해줍니다.

 

빨간색을 띄는 자식노드가 A노드의 반대방향인 경우 A노드의 부모노드에 대하여 A노드 방향으로 회전연산을 해줍니다.

 

 

 

 

Node* RBTDeletefix(Node* node, Node* check) {
	if (check->color == 'R') {
		check->color = 'B';
		return node;
	}

	while (check->Parent != NULL && check->color == 'B') {
		Node* p = check->Parent;
		if (p->Left == check) {
			Node* uncle = p->Right;
			if (uncle->color == 'R') {
				p->color = 'R';
				uncle->color = 'B';
				p = LeftRotate(p);
				uncle = p->Right;
			}

			if ( (uncle->Left == NULL || uncle->Left->color == 'B') && (uncle->Right == NULL || uncle->Right->color == 'B') ) {
				uncle->color = 'R';

				if (check->key == -1) {
					p->Left = NULL;
				}
				if (p->color == 'R') {
					p->color = 'B';
					break;
				}
				else {
					check = p;
				}
			}
			else if (uncle->Right == NULL || uncle->Right->color == 'B') {
				uncle->color = 'R';
				uncle->Left->color = 'B';
				RightRotate(uncle);
			}
			else if (uncle->Right->color == 'R') {
				uncle->color = p->color;
				p->color = 'B';
				uncle->Right->color = 'B';

				if (check->key == -1) {
					p->Left = NULL;
				}

				LeftRotate(p);

				break;
			}
		}
		else {
			Node* uncle = p->Left;
			if (uncle->color == 'R') {
				p->color = 'R';
				uncle->color = 'B';
				p = RightRotate(p);
				uncle = p->Left;
			}

			if (uncle == NULL) {
				p->color = 'R';

			}
			else if ((uncle->Left == NULL || uncle->Left->color == 'B') && (uncle->Right == NULL || uncle->Right->color == 'B')) {
				uncle->color = 'R';

				if (check->key == -1) {
					p->Right = NULL;
				}
				if (p->color == 'R') {
					p->color = 'B';
					break;
				}
				else {
					check = p;
				}
			}
			else if (uncle->Left == NULL || uncle->Left->color == 'B') {
				uncle->color = 'R';
				uncle->Right->color = 'B';
				LeftRotate(uncle);
			}
			else if (uncle->Left->color == 'R') {
				uncle->color = p->color;
				p->color = 'B';
				uncle->Left->color = 'B';

				if (check->key == -1) {
					p->Right = NULL;
				}

				RightRotate(p);

				break;
			}
		}
	}
	while (node->Parent != NULL) {
		node = node->Parent;
	}
	return node;
}

Node* Delete(Node* node, int key) {

	Node* ret = node;

	// key값의 노드 찾기.
	while (node->key != key) {
		if (node->key > key) {
			node = node->Left;
		}
		else {
			node = node->Right;
		}
	}

	Node* deleted;

	if (node->Left == NULL || node->Right == NULL) {
		deleted = node;
	}
	else {
		deleted = Successor(node, node->key);
	}

	Node* focus = (Node*)malloc(sizeof(Node));
	if (deleted->Left != NULL) {
		focus = deleted->Left;
	}
	else {
		if (deleted->Right == NULL) {
			focus->key = -1;
			focus->color = 'B';
		}
		else {
			focus = deleted->Right;
		}
	}

	if (focus != NULL) {
		focus->Parent = deleted->Parent;
	}


	// 삭제할게 루트이면
	if (deleted->Parent == NULL) {
		if (focus->key != -1) {
			deleted = focus;
			return focus;
		}
		else
			return NULL;
	}
	else if (deleted->Parent->Left == deleted) {
		deleted->Parent->Left = focus;
	}
	else {
		deleted->Parent->Right = focus;
	}

	if (deleted != node) {
		node->key = deleted->key;
	}

	if (deleted->color != 'R') {
		ret = RBTDeletefix(ret, focus);
	}
	else {
		if (focus->key == -1) {
			if (focus->Parent->Right == focus) {
				focus->Parent->Right = NULL;
			}
			else {
				focus->Parent->Left = NULL;
			}
			focus = NULL;
		}
	}

	return ret;
}