노드들이 부모-자식 관계로 연결된 비순환 그래프이다.
부모 노드가 여러 자식을 가질 수 있는 계층구조를 다 Tree라고한다.
Root(뿌리), Edge(가지), Leaf(잎) 으로 나뉘며, 높이/깊이 특성이 있다.
Root : 트리의 가장 꼭대기 노드Edge : 노드와 노드를 잇는 연결선Leaf : 더 이상 자식이 없는 끝 노드
높이/깊이 : 루트에서 가장 먼 잎까지의 거리 (높이가 작을 수록 성능 높음)
BST(Binary Search Tree)
BT에 탐색을 위한 정렬 규칙을 얹은 모델
모든 노드에 대해 왼쪽 자식 값 < 부모 값 < 오른쪽 자식 값이라는 규칙이 강제된다.
탐색 성능이 $O(logN)$이다.
시간 복잡도
표기법 명칭 설명 문제 $O(1)$ 상수 시간 데이터 수에 상관없이 즉시 완료 배열의 인덱스로 값 찾기, Heap의 Peek $O(logN)$ 로그 시간 실행할 때마다 확인해야 할 데이터가 절반씩 줄어듦 이진 탐색, BST 탐색, Heap의 삽입/삭제 O(N) 선형 시간 데이터 수만큼 시간이 정비례해서 증가 for문 하나로 배열 처음부터 끝까지 훑기 $O(NlogN)$ 선형 로그 시간 $O(n)$과 $O(\log n)$이 중첩된 형태 Heap Sort, Quick Sort, Merge Sort $O(N2)$ 이차 시간 데이터가 조금만 늘어나도 시간이 확 늘어남 이중 for문, 선택 정렬, 버블 정렬 $O(2N)$ 지수 시간 데이터가 늘어날 때마다 시간이 2배씩 폭증 피보나치 수열의 단순 재귀 구현 $O(N!)$ 팩토리얼 시간 데이터가 10~20개만 되어도 컴퓨터가 멈춤 외판원 순회 문제(TSP)의 모든 경로 탐색
탐색Root부터 찾고자 하는 값(Target)과 현재 노드의 값을 비교한다.Target보다 작으면 왼쪽, 크면 오른쪽으로 이동한다.
bool Find(Node* node, int value)
{
if (nullptr == node)
return false;
if (value == node->data)
return true;
if (value < node->data)
{
if (nullptr != node->left)
Find(node->left, value);
}
else if (value > node->data)
{
if (nullptr != node->right)
Find(node->right, value);
}
return false;
}삽입
탐색과 논리는 같다. 빈 공간 발견하면 노드 생성하고 부모 노드와 연결한다.
void Insertion(Node* node, int value)
{
if (value == node->data)
{
cout << "Find!\n";
return;
}
if (value < node->data)
{
if (nullptr == node->left)
{
node->left = new Node();
node->left->data = value;
node->left->parent = node;
}
else
{
Insertion(node->left, value);
}
}
else if (value > node->data)
{
if (nullptr == node->right)
{
node->right = new Node();
node->right->data = value;
node->right->parent = node;
}
else
{
Insertion(node->right, value);
}
}
}삭제
노드를 지운 뒤에도 트리의 연결성과 정렬 규칙이 유지되게 해야한다.
삭제할 노드의 자식 개수에 따라 3가지 케이스로 나뉜다.
- 자식이 없는 경우 (Leaf 노드)
그냥 메모리를 해제.while (node && node->data != value) { if (value < node->data) node = node->left; else node = node->right; }
...
Node* deleteNode = node;
...
delete deleteNode;
2. 자식이 하나인 경우
왼쪽이 있으면 왼쪽을, 없으면 오른쪽을 연결한다.
``` cpp
Node* replaceNode = (deleteNode->left) ? deleteNode->left : deleteNode->right;
// 지울 노드의 값을 자식에 다 연결해준다.
if (replaceNode)
replaceNode->parent = deleteNode->parent;
if (nullptr == deleteNode->parent)
root = replaceNode;
else if (deleteNode == deleteNode->parent->left)
deleteNode->parent->left = replaceNode;
else
deleteNode->parent->right = replaceNode;
if (deleteNode != node)
node->data = deleteNode->data;
delete deleteNode;- 자식이 둘인 경우
삭제될 노드를 대신할 노드를 찾아야 한다. 오른쪽 서브트리에서 가장 작은 값을 가진 노드를 가져와서
삭제될 노드 자리에 끼워 넣는다. 왼쪽은 작고 오른쪽은 크다는 규칙이 유지되야 한다.
// 자식이 둘다 있으면
if (node->left && node->right)
{
// 오른쪽 자식 중에 제일 작은 값 찾기.
deleteNode = node->right;
while (deleteNode->left)
deleteNode = deleteNode->left;
}
// 자식이 하나인 코드 시작전체코드
void Delete(Node*& root, int value) {
Node* node = root;
// 데이터 탐색
while (node && node->data != value)
{
if (value < node->data) node = node->left;
else node = node->right;
}
// 없으면 return
if (nullptr == node) return;
Node* deleteNode = node;
// 자식이 둘다 있으면
if (node->left && node->right)
{
// 오른쪽 자식 중에 제일 작은 값 찾기.
deleteNode = node->right;
while (deleteNode->left)
deleteNode = deleteNode->left;
}
// node->right에 왼쪽이 아예 없는 경우, 오른쪽으로 대체
Node* replaceNode = (deleteNode->left) ? deleteNode->left : deleteNode->right;
// 지울 노드의 값을 자식에 다 연결해준다.
if (replaceNode)
replaceNode->parent = deleteNode->parent;
if (nullptr == deleteNode->parent)
root = replaceNode;
else if (deleteNode == deleteNode->parent->left)
deleteNode->parent->left = replaceNode;
else
deleteNode->parent->right = replaceNode;
if (deleteNode != node)
node->data = deleteNode->data;
delete deleteNode;
}
관련문제
https://www.acmicpc.net/problem/1991
https://www.acmicpc.net/problem/1240
https://www.acmicpc.net/problem/11725
BT(Binary Tree)
각 노드는 최대 2개의 자식만 가질 수 있는 Tree, 이진 트리라고 부른다.BST에서 Search가 빠졌다. 담는데 규칙이 없다. 정렬도 없고, 탐색, 삭제에 $O(N)$이 걸린다.
전부 탐색해야 하기 때문에 BFS(Breadth First Search)가 사용된다. BFS구현을 위해 Queue를 사용했다.
struct Node
{
int data = 0;
Node* left = nullptr; // 왼쪽 노드
Node* right = nullptr; // 오른쪽 노드
Node* parent = nullptr; // 부모
};
Node root; // 스택영역에 만든 뿌리 구조체탐색
순서는 상관없다 오른쪽이 먼저 와도 된다.
bool Find(Node* node, int value)
{
if (nullptr == node) return false;
if (node->data == value) return true;
// 왼쪽에서 찾거나, 오른쪽에서 찾거나
return Find(node->left, value) || Find(node->right, value);
}삽입Tree 전체를 순회하다가, left비었으면 채워서 값 넣고,right가 비었으면 채워넣고. right부터 해도된다.
void Insertion(Node* node, int value)
{
// Root가 비어있다면 데이터만 채우고 종료
if (node->data == -1)
{
node->data = value;
return;
}
queue<Node*> q;
q.push(node);
while (!q.empty())
{
Node* curr = q.front();
q.pop();
// 왼쪽
if (curr->left == nullptr)
{
curr->left = new Node();
curr->left->data = value;
curr->left->parent = curr;
return;
}
else
q.push(curr->left);
// 오른쪽
if (curr->right == nullptr)
{
curr->right = new Node();
curr->right->data = value;
curr->right->parent = curr;
return;
}
else
{
q.push(curr->right);
}
}
}삭제Queue를 사용해 전역탐색한다.
어차피 규칙이 없으므로, 삭제하기 쉽게 아무 마지막 노드의 값을 끌어오고
마지막 노드의 값을 지운다.
void Delete(Node* node, int value)
{
if (nullptr == node || node->data == -1) return;
// 1. 지울 노드 찾기
queue<Node*> q;
q.push(node);
Node* targetNode = nullptr;
Node* lastNode = nullptr;
while (!q.empty())
{
lastNode = q.front();
q.pop();
if (lastNode->data == value) targetNode = lastNode;
if (lastNode->left) q.push(lastNode->left);
if (lastNode->right) q.push(lastNode->right);
}
if (targetNode)
{
// 2. 마지막 노드의 데이터를 타겟 노드에 덮어쓰기
targetNode->data = lastNode->data;
// 3. 마지막 노드(lastNode)를 물리적으로 제거
if (lastNode->parent)
{
if (lastNode->parent->left == lastNode) lastNode->parent->left = nullptr;
else lastNode->parent->right = nullptr;
delete lastNode;
}
else
{
// Root인 경우
lastNode->data = -1;
}
}
}이진 트리 순회
전위, 후위, 중위 순회가 있다.
// 전위 순회 : Root - Left - Right
void PreOrder(Node* node)
{
if (nullptr == node)
return;
cout << node->data << ' ';
PreOrder(node->left);
PreOrder(node->right);
}
// 후위 순회 : Left - Right - Root
void PostOrder(Node* node)
{
if (nullptr == node)
return;
PostOrder(node->left);
PostOrder(node->right);
cout << node->data << ' ';
}
// 중위 순회 : Left - Root - Right
void InOrder(Node* node)
{
if (nullptr == node)
return;
InOrder(node->left);
cout << node->data << ' ';
InOrder(node->right);
}
5 → 3 → 9 → 1 → 2 → 8 → 10 순으로 데이터를 삽입했을 때
BT
전위 순회: 5 3 1 2 9 8 10
중위 순회: 1 3 2 5 8 9 10
후위 순회: 1 2 3 8 10 9 5
BST
전위 순회 : 5 3 1 2 9 8 10
중위 순회 : 1 2 3 5 8 9 10
후위 순회 : 2 1 3 8 10 9 5
자가 균형 트리(Red-Black-트리)
Red-Black-트리는 BST의 값이 한쪽으로 쏠리는 현상을 방지한다.
BST에 데이터가 들어 올 때 규칙을 적용해 트리 높이를 항상 최소한으로 유지한다.Red-Black-트리는 이름처럼 Red와 Black이라는 색상을 사용해 정렬한다.
탐색, 삽입, 삭제 모두 O(logN)의 시간 복잡도를 가진다.
- 모든 노드는
Red혹은Black이다. Root노드는 항상Black이다.- 모든
Leaf/NIL은Black이다. Red노드의 자식은 반드시Black이다. (Red가 연속으로 나올 수 없음)- 임의의 노드에서
Leaf까지 가는 경로의Black노드 개수는 모두 같다.
enum Color { RED, BLACK };
struct Node
{
int data;
Color color;
Node* left;
Node* right;
Node* parent;
};5번 규칙에 의해 모든 경로의 Black의 수는 같고,
4번 규칙에 의해 Red는 Black사이에만 올 수 있다.
제일 긴 경로라도 B-R-B-R, B-B의 2배를 넘을 수 없다.
이런 규칙을 통해 Key를 기준으로 항상 정렬된 상태를 유지한다.
규칙 위반시 구조를 재조정한다.
구조 재조정에는 할아버지, 부모, 삼촌을 사용해야한다.
Recoloring(색상 바꾸기)
부모 삼촌이 모두 Red라면, 둘 다 Black으로 칠하고
할아버지가 있다면 Red로 바꾼다.
할아버지가 Root라면 2번 규칙에 따라 다시 Black이 된다
Root일 때
Root가 아닐 때
바꾸는 코드는 간단하다.
curNode->parent->parent->color = RED; // 할아버지
curNode->parent->color = BLACK; // 부모
curNode->parent->left->color = BLACK; // 내가 오른쪽 자식일 때 삼촌Restructuring / Rotation (회전)
Recoloring을 통해 색을 바꿀 때,
할아버지를Red로 바꾸면서Double Red가 발생 할 수 있다.
또 할아버지가Red가 되면서 위쪽으로Double Red문제가 퍼진다.
삼촌 노드가Black이기 때문에Recoloring을 수행할 수 없다.
또 삽입마다Root까지 퍼질 수 있는Double Red를Recoloring으로 바꿀 순 없다.
이럴 때 Rotation을 쓴다.
이미 완성된 아래쪽 트리 뭉치를 통째로 들고 좌/우로 돌려버린다.
포인터 3쌍(부모-두 자식)을 물리적으로 재조립한다. 이 연산은 $O(1)$이 걸린다.
트리 높이를 낮춰 탐색 성능을 $O(n)$에서 $O(\log n)$으로 끌어올리는 연산이다.
우회전 (Right Rotation)
왼쪽 자식을 부모 자리로 끌어올리고 싶을 때 사용합니다.
부모 → 오른쪽 자식 자리로 내려감 (자기 자식의 오른쪽으로)
왼쪽 자식 → 부모 자리로 올라감
왼쪽 자식의 오른쪽 자식 → 원래 부모의 왼쪽 자식 자리로 옮겨감
void RotateRight(Node*& root, Node* parent) {
Node* leftChild = parent->left; // 부모의 왼쪽자식
parent->left = leftChild->right; // 부모의 왼쪽은 왼오른자식
if (leftChild->right != nullptr)
leftChild->right->parent = parent; // 왼오른자식과 부모를 이어줌
leftChild->parent = parent->parent; // 왼자식과 할아버지를 이어줌
if (parent->parent == nullptr) // 할아버지가 없으면 Root
root = leftChild;
else if (parent == parent->parent->left) // 할아버지가 있고 부모가 원래 왼쪽이었으면
parent->parent->left = leftChild; // 나도 왼쪽으로
else
parent->parent->right = leftChild; // 부모가 원래 오른쪽이면 나도 오른쪽
leftChild->right = parent; // 부모를 왼자식의 오른쪽으로
parent->parent = leftChild; // 왼자식을 부모의 부모로 임명
} 회전 그림은 RBTree의 일부분만 가져왔다.
포인터의 참조
root를 매개변수로 받을 때*&타입으로 받고 있다.
그냥 포인터 타입으로 들어온root가 Root를 바꾸면
원래 포인터root는 옛날 Root를 가리키고 있다.또 매개변수로 들어온
root를 바꾸면 지역변수로써
스택에서 벗어나면 없어지기 때문에, 바뀐 Tree의root를 못찾게 된다.포인터의 참조를 받아 매개변수로 들어온 지역변수
root가RedBlackTree의root를 대행하고 있다.
좌회전 (Left Rotation)
오른쪽 자식을 부모 자리로 끌어올리고 싶을 때 사용한다.
부모 → 왼쪽 자식 자리로 내려감 (자기 자식의 왼쪽으로)
오른쪽 자식 → 부모 자리로 올라감
오른쪽 자식의 왼쪽 자식 → 원래 부모의 오른쪽 자식 자리로 옮겨감
void RotateLeft(Node*& root, Node* parent) {
Node* rightChild = parent->right; // 부모의 오른자식
parent->right = rightChild->left; // 부모의 오른쪽에
// 오른자식의 왼자식을 붙임
if (rightChild->left != nullptr)
rightChild->left->parent = parent; // 오왼자식과 부모를 이어줌
rightChild->parent = parent->parent; // 오른자식과 할아버지를 이어줌
if (parent->parent == nullptr) // 할아버지가 없으면 Root
root = rightChild;
else if (parent == parent->parent->left) // 부모가 할아버지의 왼자식이라면
parent->parent->left = rightChild; // 할아버지의 왼쪽으로
else
parent->parent->right = rightChild; // 아니면 오른쪽으로
rightChild->left = parent; // 부모를 오른자식의 왼쪽으로
parent->parent = rightChild; // 오른자식을 부모의 부모로 임명.
} 회전 그림은 RBTree의 일부분만 가져왔다.
삽입
Gemini가 짜준 FixInsert 코드, 내부에서 색을 바꾸는 Recoloring, 구조를 바꾸는 Restructuring을 하고 있다.BST의 Insert를 하고 생기는 Red, Black색 겹침을 FixInsert에서 보정한다.
void FixInsert(Node*& root, Node* curNode)
{
while (curNode != root && curNode->parent->color == RED)
{
// 부모(Red)가 할아버지(Black)의 left이고
if (curNode->parent == curNode->parent->parent->left)
{
Node* uncle = curNode->parent->parent->right; // 삼촌
// 삼촌은 Red인 경우
if (uncle && uncle->color == RED)
{
curNode->parent->color = BLACK;
uncle->color = BLACK;
curNode->parent->parent->color = RED;
curNode = curNode->parent->parent;
}
else {
// 삼촌이 Black이고 내가 오른쪽 자식, 좌회전으로 일직선 만들고 균형 맞춤
if (curNode == curNode->parent->right)
{
// 일직선을 균형을 맞춤(Left Rotate)
curNode = curNode->parent;
RotateLeft(root, curNode);
}
// 삼촌이 Black이고 내가 왼쪽 자식, 일직선 → 우회전으로 균형 맞춤
curNode->parent->color = BLACK;
curNode->parent->parent->color = RED;
RotateRight(root, curNode->parent->parent);
}
}
// 부모(Red)가 할아버지(Black)의 right이고
else
{
Node* uncle = curNode->parent->parent->left;
// 삼촌은 Red인 경우
if (uncle && uncle->color == RED)
{
curNode->parent->color = BLACK;
uncle->color = BLACK;
curNode->parent->parent->color = RED;
curNode = curNode->parent->parent;
}
else
{
// 삼촌이 Black이고 내가 왼쪽 자식, 일직선으로 만들고 균형 맞춤
if (curNode == curNode->parent->left)
{
curNode = curNode->parent;
RotateRight(root, curNode);
}
// 삼촌이 Black이고 내가 오른쪽 자식, 일적선을 우회전으로 균형 맞춤
curNode->parent->color = BLACK;
curNode->parent->parent->color = RED;
RotateLeft(root, curNode->parent->parent);
}
}
}
root->color = BLACK; // 규칙: 루트는 항상 BLACK
}큰 틀은 현재 노드가 Root와 같지 않고
내 부모가 Red라면 계속되는 코드다.
부모(Red)가 할아버지(Black)의
left이고, 삼촌은Red인 경우
나를 기준으로Recoloring부모(Red)가 할아버지(Black)의
left이고, 삼촌은Black인 경우
2-1. 내가 오른쪽 자식
일직선으로 만들고(Left Rotate), 균형있게 맞춤(Right Rotate)
2-2. 내가 왼쪽 자식
일직선을 균형있게 맞춤(Right Rotate)부모(Red)가 할아버지(Black)의
right이고, 삼촌은Red인 경우
나를 기준으로Recoloring부모(Red)가 할아버지(Black)의
right이고, 삼촌은Black인 경우
4-1. 내가 왼쪽 자식
일직선으로 만들고(Right Rotate), 균형있게 맞춤(Left Rotate)
4-2. 내가 오른쪽 자식
일직선을 균형있게 맞춤(Left Rotate)
일직선으로 우선 만들고 균형을 맞춘다는 동일하다. 어느쪽 자식이냐에 따라
돌리는 순서가 달리질 뿐이다.
삭제BST의 삭제 로직과 비슷하지만, 노드를 제거하기 전에 보정 로직이 들어간다.
// 새로 짠 BST Delete
void DeleteNode(Node*& root, Node* node) {
... BST 삭제 알고리즘
// 삭제된 노드가 BLACK이었다면 보정(FixDelete) 호출
if (deleteNodeColor == BLACK) {
FixDelete(root, deleteNodeChild, deleteNode->parent);
}
delete deleteNode;
}FixDelete는 삭제할 노드가 Black일 때만 동작한다.Black인 노드를 지우면 Double black이 일어나기 때문이다.
용어만 보면 Black이 두 개 연속오는 상황을 말하는 것 같지만,
하나의 Black이 두 개분의 Black역할을 맡고 있는, Black이 하나 부족할 때를 말한다.
삽입이 Double red를 해결하기 위한 작업이었다면,
삭제는 Double black을 해결하기 위한 작업이다.
삭제 보정
void FixDelete(Node*& root, Node* x, Node* xParent) {
// x가 nullptr(Black 리프)이거나 실제 Black 노드인 동안 반복
while (x != root && (x == nullptr || x->color == BLACK)) {
if (x == xParent->left) {
Node* s = xParent->right; // 형제(Sibling)
// Case 1: 형제가 Red인 경우
if (s != nullptr && s->color == RED) {
s->color = BLACK;
xParent->color = RED;
RotateLeft(root, xParent);
s = xParent->right;
}
// Case 2: 형제의 자식들이 모두 Black인 경우 (nullptr는 Black으로 취급)
if ((s->left == nullptr || s->left->color == BLACK) &&
(s->right == nullptr || s->right->color == BLACK)) {
s->color = RED;
x = xParent; // x가 이제 부모 노드가 됨
xParent = x->parent; // 부모도 한 칸 위로 갱신
}
else {
// Case 3: 내 쪽(왼쪽) 조카가 Red인 경우
if (s->right == nullptr || s->right->color == BLACK) {
if (s->left != nullptr) s->left->color = BLACK;
s->color = RED;
RotateRight(root, s);
s = xParent->right;
}
// Case 4: 먼 쪽(오른쪽) 조카가 Red인 경우
s->color = xParent->color;
xParent->color = BLACK;
if (s->right != nullptr) s->right->color = BLACK;
RotateLeft(root, xParent);
x = root; // 루프 종료 조건
}
}
else { // 내가 오른쪽 자식인 경우 (대칭)
Node* s = xParent->left;
if (s != nullptr && s->color == RED) {
s->color = BLACK;
xParent->color = RED;
RotateRight(root, xParent);
s = xParent->left;
}
if ((s->right == nullptr || s->right->color == BLACK) &&
(s->left == nullptr || s->left->color == BLACK)) {
s->color = RED;
x = xParent;
xParent = x->parent;
}
else {
if (s->left == nullptr || s->left->color == BLACK) {
if (s->right != nullptr) s->right->color = BLACK;
s->color = RED;
RotateLeft(root, s);
s = xParent->left;
}
s->color = xParent->color;
xParent->color = BLACK;
if (s->left != nullptr) s->left->color = BLACK;
RotateRight(root, xParent);
x = root;
}
}
}
// 마지막에 x가 실제 노드라면 Black으로 확정 (Double Black 해소)
if (x != nullptr) x->color = BLACK;
}여기서 나는 삭제되는 노드이다.
내가 부모의 왼쪽이다.
1-1. 형제가Red인 경우
내 형제가Red라면, 부모는 반드시Black.
형제와 부모의 색을 바꾸고, 부모를 내 쪽으로 좌회전시킨다
형제가Black인 다른 케이스(2, 3, 4)로 전환된다.
여전히Double black은 남아 있다.
1은 문제를 해결하기 쉬운 상태로 만드는 과정이다.
1-2. 형제가Black이고, 형제 자식 전부Black
빌려올Black이 없는 상황.
형제를Red로 만들고,Double Black의 상황을 부모에게 넘긴다.(x = x->parent)
부모가 원래Red였다면Black이 되면서 종료.
부모도Black이었다면 다시 위쪽에서FixDelete가 반복된다.
1-3. 형제가Black이고, 내 쪽 조카가Red인 경우
형제와 그 조카의 색을 바꾸고 형제를 우회전 시킨다.
Case 4(일직선 모양)를 만들기 위한 준비 단계.
1-4. 형제가Black이고, 먼 쪽 조카가Red인 경우
형제에게 부모의 색을 물려준다.
부모와 먼 쪽 조카를Black으로 칠한다.
부모를 내 쪽으로 좌회전시킨다.
내가 부모의 오른쪽이다.
1의 과정들을 진행하되, 회전만 반대로.
Complete Binary Tree(CBT)
완전 이진 트리라고 부른다.
노드를 사용하지 않고 배열을 사용한다.BT, BST처럼 포인터를 가질 필요가 없다. 데이터 값만 배열에 순서대로 담으면 된다.
배열 하나를 쓰므로 캐시 지역성이 높다.
정렬이 없고 그냥 담는다. BT를 배열에 넣은 셈
배열을 사용하기 위해 두가지 규칙이 있다.
마지막 레벨을 제외한 모든 노드가 꽉 차 있어야 한다.
- 노드가 꽉차 있을 때 배열에 사용하기 알맞다.
- 비어있는 값이 없을 테니 예외 케이스를 생각하지 않아도 된다.
- 트리의 높이를 최소화 할 수 있다. 트리는 높이가 낮을 수 록 탐색, 삽입, 삭제가 빠르다.
- 별도의 탐색 로직 없이 산술 연산만으로 내려갈 수 있다.
- 배열 절반 이후는 무조건 자식이 없는
Leaf노드라는걸 알 수 있다.
마지막 레벨의 노드는 반드시 왼쪽 순서대로 채워져야 한다.
- 포인터 없이 배열에 넣기 위한 규칙
- 배열의 0번 index를 루트
왼쪽 자식 위치:부모 index * 2 + 1
오른쪽 자식 위치:부모 index * 2 + 2
부모의 위치:(내 index - 1) / 2
삽입
void Insert(int value)
{
tree.push_back(value);
}삭제
void Delete(int index)
{
if (index >= tree.size()) return;
// 마지막 요소를 삭제 위치로 복사
tree[index] = tree.back();
// 마지막 요소 제거
tree.pop_back();
}Heap
전체 정렬은 하지 않고 최댓값, 최솟값만 빨리 뽑을 때 사용한다.
CBT의 룰을 따르면서 부모는 자식보다 커야 한다라는 규칙이 있다.
이 정렬은 $O(N \log N)$이 걸린다.
$K$번째로 크거나 작은 값 찾기수억 개의 데이터 중에서 가장 큰 10개만 뽑을 때,
전체를 다 정렬($O(N \log N)$)할 필요 없이, 크기가 10인 힙을 유지하면서 데이터를 훑으면 된다.
길 찾기 알고리즘(Dijkstra)에서 현재 갈 수 있는 길 중 가장 짧은 길을 구할 때 힙을 사용한다.
삽입
삽입은 트리의 부모들과 비교만 하면 되기 때문에
void Insert(int value)
{
// 1. 일단 구조를 지키기 위해 맨 끝에 넣는다 (CBT 완성)
tree.push_back(value);
// 2. 이제 규칙(Heap)을 지키기 위해 부모와 비교하며 올라간다
int curr = tree.size() - 1; // 현재 내 위치 (방금 넣은 끝자리)
while (curr > 0)
{
int parent = (curr - 1) / 2; // 부모 인덱스 계산
// 만약 내가 부모보다 크다면? (Max Heap 기준) 자리를 바꾼다!
if (tree[curr] > tree[parent])
{
swap(tree[curr], tree[parent]);
curr = parent; // 내 위치를 부모 자리로 업데이트하고 다시 비교
}
else
break; // 부모가 나보다 크면 규칙 만족, 종료!
}
}
삭제
맨 뒤 값을 삭제 위치로 가져와 부모와 자식들과 비교하며 위치를 찾아간다.
void Delete(int index)
{
if (index >= tree.size()) return;
// 1. 마지막 요소를 삭제 위치로 복사
tree[index] = tree.back();
tree.pop_back();
if (tree.empty() || index >= tree.size()) return;
// 2. 위로 올라가야 하는지 확인 (부모보다 크면)
int parent = (index - 1) / 2;
if (index > 0 && tree[index] > tree[parent])
{
// HeapifyUp 로직 (삽입 때 썼던 로직)
int curr = index;
while (curr > 0) {
int p = (curr - 1) / 2;
if (tree[curr] > tree[p]) {
swap(tree[curr], tree[p]);
curr = p;
}
else break;
}
}
// 3. 아니라면 아래로 내려가야 하는지 확인 (자식보다 작으면)
else
{
// HeapifyDown 로직 (추출 때 썼던 로직)
int curr = index;
while (true) {
int left = curr * 2 + 1;
int right = curr * 2 + 2;
int largest = curr;
if (left < tree.size() && tree[left] > tree[largest]) largest = left;
if (right < tree.size() && tree[right] > tree[largest]) largest = right;
if (largest != curr) {
swap(tree[curr], tree[largest]);
curr = largest;
}
else break;
}
}
}
Heap은 최댓값을 추출하고 다시 최댓값이 0으로 오게 재구성하는데 걸리는 시간이 $O(log N)$이다.
문제
이진 탐색 트리(BST)에서 데이터가 한쪽으로 치우칠 경우 발생하는 문제점과
이를 해결하기 위한 자가 균형 트리의 필요성을 설명하세요.Red-Black Tree의 5가지 속성 중 "루트에서 리프까지의 모든 경로에 있는 블랙 노드의 수는 같다"는 규칙이
트리의 균형 유지에 어떤 기여를 하는지 설명하세요.게임 엔진에서 $O(N)$ 탐색과 $O(\log N)$ 탐색의 차이가
프레임워크 성능(FPS)에 미치는 영향에 대해 의견을 제시하세요.왜 C++ STL의 std::map이나 std::set은 주로 Red-Black Tree로 구현되어 있는지,
Hash Table($O(1)$)과 비교하여 설명하세요.포인터 기반의 트리 구조(BT/BST)와 배열 기반의 트리 구조(CBT/Heap) 중
메모리 지역성(Cache Locality) 측면에서 유리한 쪽은 어디이며 그 이유는 무엇인가요?게임 내 아이템 시스템에서 '등급별 정렬'과 '이름별 검색'이 동시에 빈번하게 일어난다면
어떤 트리 구조를 활용하는 것이 좋을까요?트리의 순회 방식(전위, 중위, 후위) 중 BST에서 데이터를
오름차순으로 정렬된 상태로 가져오기 위해 사용해야 하는 순회 방식은 무엇인가요?힙(Heap)에서 새로운 원소를 삽입할 때의 과정을 설명하고,
왜 이 과정이 $O(\log N)$의 시간 복잡도를 가지는지 서술하세요.
객관식 10문제
https://gemini.google.com/share/0bf4b3e47bd3
내용에 대한 질의나, 수정 요청은 저에게 큰 도움이 됩니다.