Kim Geon Woo Unreal Client

레드블랙트리(Red Black Tree)는 자기 균형 이진 탐색 트리 구조로, 삽입과 삭제 연산 이후 레드/블랙의 색상을 사용하여 균형잡힌 정렬을 하는 이진 탐색 트리(BST)입니다.

속성

• 모든 노드는 빨간색 또는 검은색을 가지고 있다.
• 루트 노드는 항상 검은색 이다.
• Leaf(NIL) 노드는 항상 검은색 이다.
• 빨강 노드의 자식은 모드 검정색이다.
• 임의의 노드에서 모든 리프노드에 이르는 경로에는 동일한 수의 검정 노드가 필요하다.

※NIL : 아무 데이터도 가지고 있지않는 더미 노드. 

특징

• 이진 탐색 트리(BST)의 한 종류
• BST의 최악의 경우 O(N)의 시간 복잡도를 개선해서 모든 경우의 시간복잡도 O(log N)을 유지
• 항상 균형을 유지하여 특정 케이스에 치우친 성능 저하가 없다.
  • 삽입,삭제 시 회전 연산을 통해 균형을 유지한다.
• Map, Set 자료구조는 RBT를 기반으로 구현되었다.

회전연산

삽입,삭제,탐색시 시간복잡도가 항상 O(log N)을 유지하기위해서 항상 균형잡힌 상태를 유지합니다.

해당 과정에서는 RBT의 속성을 유지하며 트리 구조를 조정하는데에는 왼쪽회전, 오른쪽 회전의 방식이 있습니다.

삽입

• 새 노드는 처음에 빨간색으로 삽입된다.
• 삽입 후, 트리는 RB-T 속성을 위반할 수 있으므로, 이를 수정하기 위해 재조정 및 색상 변경이 수행된다.
  • 삽입된 노드의 부모가 검정이면 트리 속성이 유지되므로 조정하지 않는다.
  • 삽입된 노드의 부모와 삼촌이 둘다 빨강일 경우
    • 부모 삼촌은 검정으로 변경
    • 조부모를 빨강으로 변경
    • 재귀적 처리를 통해 색상 조정
  • 부모가 빨강이고 삼촌이 검정일 경우
    • 회전연산을 통해 색상이 조정된다.
• 노드들은 필요에 따라 색상이 변경될 수 있으며, 회전연산을 통해 균형을 유지한다.
• BST와같이 재귀적으로 노드를 호출하며 조정된다.

삭제

• 삭제 노드가 레드 노드일 경우
  • 삭제 후 조정 처리가 필요없다
• 삭제 노드가 블랙 노드인 경우
  • 삭제 노드의 자리가 RBT속성을 위반하므로 추가적인 작업을 수행한다.
  • 형제가 레드일 경우
    • 부모-형제 색상 교환
    • 부모를 기준으로 회전연산
  • 형제가 블랙, 형제의 자식이 모두 블랙
    • 형제를 레드로 변경
    • 부모노드를 검정으로 변경 후 형제가 레드일 경우의 단계를 처러리
  • 형제가 블랙, 형제의 자식중 하나가 레드
    • 형제와 형제의 자식(레드)의 색상을 교환
    • 자식(레드)가 왼쪽일 경우 형제노드를 기준으로 오른쪽 회전
      • ---- 형제의 자식(레드)가 오른쪽일 경우 다음 단계부터 수행 ----
    • 부모와 형제 노드의 색상을 교환
    • 부모를 기준으로 왼쪽 회전
    • 형제노드의 오른쪽 자식을 블랙으로 변경

회전연산 - 왼쪽 회전

	// Left Rotation
    void leftRotate(Node* node) {
        Node* rightNode = node->right; // 노드의 오른쪽 자식을 가져옴
        if (rightNode == nullptr) return; // 오른쪽 자식이 없으면 회전 불가

        node->right = rightNode->left; // 노드자식(오른쪽)의 왼쪽 서브트리를 노드의 오른쪽에 연결
        if (rightNode->left != nullptr) {
            rightNode->left->parent = node;
        }

        rightNode->parent = node->parent; // 노드의 부모를 노드자식(오른쪽)의 부모로 설정
        if (node->parent == nullptr) {
            root = rightNode; // 노드가 루트라면 노드자식(오른쪽)가 새 루트가 됨
        }
        else if (node == node->parent->left) {
            node->parent->left = rightNode;
        }
        else {
            node->parent->right = rightNode;
        }

        rightNode->left = node; // 노드를 노드자식(오른쪽)의 왼쪽 자식으로 설정
        node->parent = rightNode;
    }

회전연산 - 오른쪽 회전

    //Right Rotation
    void rightRotate(Node* node) {
        Node* leftNode = node->left; // 노드의 왼쪽 자식을 가져옴
        if (leftNode == nullptr) return; // 왼쪽 자식이 없으면 회전 불가

        node->left = leftNode->right; // 노드 자식(왼쪽)의 오른쪽 서브트리를 노드의 왼쪽에 연결
        if (leftNode->right != nullptr) {
            leftNode->right->parent = node;
        }

        leftNode->parent = node->parent; // 노드의 부모를 노드 자식(왼쪽)의 부모로 설정
        if (node->parent == nullptr) {
            root = leftNode; // 노드가 루트라면 노드 자식(왼쪽)가 새 루트가 됨
        }
        else if (node == node->parent->left) {
            node->parent->left = leftNode;
        }
        else {
            node->parent->right = leftNode;
        }

        leftNode->right = node; // 노드를 노드 자식(왼쪽)의 오른쪽 자식으로 설정
        node->parent = leftNode;
    }

이진탐색트리 (Binary Search Tree)

이진탐색트리는 이진탐색의 특징인 정렬된 데이터를 기반으로 빠른 탐색 을 장점으로 가지고 있는 트리구조입니다.

• 각 노드는 2개의 자식을 가질 수 있다.
• 왼쪽 서브트리에는 항상 해당 노드보다 작은 값을 가지고 있다.
• 오른쪽 서브트리에는 항상 해당 노드보다 큰 값을 가지고 있다.
• 중복된 값을 허용하지 않는다.
• 조회 시 평균적으로 O(log N)의 시간 복잡도를 가질 수 있다.
  • 정렬이 균형잡혀있지 않은 경우(최악) O(N)의 시간복잡도를 가지고 있다. 
• C++ : set, multiset, map, multimap 등이 내부적으로 이진 탐색중 하나인 R-BT로 구현되어있다.

탐색 수행 과정

1. 데이터의 중앙 요소를 고른다.
2. 중앙값과 목표값을 비교한다.
3. 목표값 < 중앙값이면 중앙을 기준으로 왼쪽, 목표값 > 중앙값이면 중앙을 기준으로 오른쪽으로 이진 탐색을 수행한다.
4. 찾는 값이 나올때까지 1~3단계를 반복한다.
5. 찾는값이 나오지 않는다면 null을 반환한다.

삽입 수행 과정

• 루트 노드의 값과 삽입 노드의 값을 비교한다.
• 삽입값 < 루트값이면 왼쪽, 삽입값 > 루트값이면 오른쪽 서브트리로 이동한다.
• 리프 노드에 도달한 후 삽입값과 리프 노드값을 비교하여 왼쪽 또는 오른쪽에 삽입한다.

삭제 수행 과정

1. 삭제할 노드가 리프노드일 경우
   1. 해당 리프노드를 삭제한다.
2. 삭제할 노드에 자식이 하나 있는 경우
   1. 해당 노드를 삭제한다.
   2. 해당 노드의 부모 노드와 자식 노드를 연결한다.
3. 삭제할 노드에 자식이 둘 있는 경우
   1. 삭제할 노드를 찾는다.
   2. 삭제할 노드의 successor 노드를 찾는다
      1. succesor : 오른쪽 서브트리의 최소값.
   3. 삭제할 노드와 successor 노드의 값을 바꾼다.
   4. 바뀐 successor 노드를 삭제한다.

구현

BinarySearchTree.h

struct Node {
	int data;
	Node* left;
	Node* right;

	Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BinarySearchTree
{
public:
	BinarySearchTree() : root(nullptr) {}

	void insert(int value);
	bool search(int value);
	void remove(int value);
	void inorderTraversal() const;
	int inorderTraversal(int value) const;

private:
	Node* root;

	Node* insertNode(Node* node, int value);
	bool searchNode(Node* node, int value);
	Node* removeNode(Node* node, int value);
	Node* findMin(Node* node);
	void inorder(Node* node) const;
	int inorder(Node* node, int value) const;

};

BinarySearchTree.cpp

void BinarySearchTree::insert(int value)
{
	root = insertNode(root, value);
}

bool BinarySearchTree::search(int value)
{
	return searchNode(root, value);
}

void BinarySearchTree::remove(int value)
{
	root = removeNode(root, value);
}

void BinarySearchTree::inorderTraversal() const
{
	inorder(root);
}

int BinarySearchTree::inorderTraversal(int value) const
{
	return inorder(root, value);
}

Node* BinarySearchTree::insertNode(Node* node, int value)
{
	if (node == nullptr) {
		return new Node(value);
	}

	if (value < node->data){
		node->left = insertNode(node->left, value);
	}
	else if (value > node->data) {
		node->right = insertNode(node->right, value);
	}


	return node;
}

bool BinarySearchTree::searchNode(Node* node, int value)
{
	if (node == nullptr){
		return false;
	}
	if (value == node->data){
		return true;
	}
	if (value < node->data){
		return searchNode(node->left, value);
	}
	else {
		return searchNode(node->right, value);
	}
}

Node* BinarySearchTree::removeNode(Node* node, int value)
{
	if (node == nullptr) {
		return nullptr;
	}


	if (value < node->data) {
		node->left = removeNode(node->left, value);
	}
	else if (value > node->data) {
		node->right = removeNode(node->right, value);
	}
	else {
		if (node->left == nullptr) {
			Node* temp = node->right;
			delete node;
			return temp;
		}
		else if (node->right == nullptr) {
			Node* temp = node->left;
			delete node;
			return temp;
		}

		Node* minNode = findMin(node->right);
		node->data = minNode->data;
		node->right = removeNode(node->right, minNode->data);
	}

	return node;
}

Node* BinarySearchTree::findMin(Node* node)
{
	while (node->left != nullptr) {
		node = node->left;
	}
	return node;
}

void BinarySearchTree::inorder(Node* node) const
{
	if (node == nullptr) {
		return;
	}
	inorder(node->left);
	std::cout << node->data << " ";
	inorder(node->right);
}

int BinarySearchTree::inorder(Node* node, int value) const
{
	if (node == nullptr) {
		std::cout << "Node Data : Can't Found." << std::endl;
		return NULL;
	}
	if (value < node->data) {
		inorder(node->left, value);
	}
	else if (value > node->data) {
		inorder(node->right, value);
	}

	if (value == node->data) {
		std::cout << "Node Data : " << node->data << std::endl;
	}
	return node->data;
}

트리 (Tree)

트리(Tree)는 계층적 관계를 나타내는 자료구조로 노드(Node)와 간선(Edge)로 구성되어잇으며 가장 상위 노드인 루트(Root)가있다. 각 노드는 다른 노드와 연결되어 부모.자식 관계를 형성하며 노드들은 자식 노드를 가질 수 있습니다.

• 노드(Node) : 트리의 각 요소. 데이터를 표현하는데 사용한다.
• 간선(Edge) : 두 노드를 연결, 관계를 나타낸다.
• 루트(Root) : 트리의 최상위 노드. 부모가 없는 노드
• 부모(Parent) : 다른 노드를 자식으로 가지는 노드
• 자식(Child) : 부모 노드에 의해 연결되는 노드
• 리프(Leaf) : 자식 노드가 없는 노드

특징 및 종류

• 트리는 계층적으로 구성되어 있으며, 루트노드를 시작으로 여러 자식 노드들이 존재 할 수 있다.
• 노드는 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
• 두 노드간의 경로는 유일하다.
  • 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 트리는 이진트리, 이진탐색트리(BST), 균형트리(AVL, RBT), 이진 힙(최대힙, 최소힙) 등이 있다.

이진트리(Binary Tree)

• 각 노드가 최대 두개의 자식을 갖는 트리
• 모든 트리가 이진 트리는 아니다
• 기본적인 트리 구조로, 이진 검색트리, 힙(Heap) 트리 등에 사용된다.

이진탐색트리 (Binary Search Tree)

• 이진 트리의 형태, 각 노드는 키 값이 왼쪽 서브 트리의 모든 값보다 크고, 오른쪽 서브트리의 모든 값보다 작다.
• 삽입, 삭제, 검색 등이 평균적으로 O(log n)의 시간 복잡도를 가지고 있다.
• 트리가 불균형시 최악의 경우 O(n)의 시간복잡도를 가진다.
• AVL Tree : 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이차이가 1인 이진 탐색 트리
  • 삽입,삭제시 회전(Rotate)하며 트리구조의 균형을 유지한다.
• RB Tree : 각 노드에 색깔(Red,Black)을 부여하여 균형을 맞추는 이진 탐색 트리
  • AVL과 같이 노드간의 균형을 유지하지만, 더 적은 회전을 하며 정렬한다.

힙(Heap)

• 각 부모 노드의 값이 자식 노드의 값보다 우선순위가 높은 구조
• 최대 힙과 최소 힙이 있다.
• 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
• 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
• 완전 이진 트리 형태를 가지며, 삽입,삭제 시 O(log n)의 시간복잡도를 가진다.

그래프 VS 트리