트리의 종류 - 이진트리
이진 트리에는 또 종류가 있습니다.
완전 이진 트리 (Complete Binary Tree):
모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 차례대로 채워져 있는 트리입니다.
포화 이진 트리 (Full Binary Tree):
모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리입니다.
이진 탐색 트리 (Binary Search Tree, BST):
왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 이진 트리입니다. 효율적
인 탐색, 삽입, 삭제가 가능합니다.
AVL 트리:
자가 균형 이진 탐색 트리로, 모든 노드의 서브트리 높이 차이가 1 이하로 유지됩니다. 균형을 유지하여 탐색 효율성을 높
입니다.
레드-블랙 트리 (Red-Black Tree):
특정 속성을 가진 자가 균형 이진 탐색 트리로, 삽입과 삭제 시 균형을 유지합니다.
말로 설명하는것보다 코드 한번 보는것이 편할 수 도있습니다.
아래는 이진 탐색 트리입니다.
#include <iostream>
class TreeNode {
public:
int value; // 노드의 값
TreeNode* left; // 왼쪽 자식 노드
TreeNode* right; // 오른쪽 자식 노드
TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};
class BinaryTree {
public:
TreeNode* root; // 트리의 루트 노드
BinaryTree() : root(nullptr) {}
// 삽입 함수
void insert(int value) {
if (root == nullptr) {
root = new TreeNode(value);
} else {
insertRecursive(root, value);
}
}
void insertRecursive(TreeNode* node, int value) {
if (value < node->value) {
if (node->left == nullptr) {
node->left = new TreeNode(value);
} else {
insertRecursive(node->left, value);
}
} else {
if (node->right == nullptr) {
node->right = new TreeNode(value);
} else {
insertRecursive(node->right, value);
}
}
}
// 탐색 함수
TreeNode* search(int value) {
return searchRecursive(root, value);
}
TreeNode* searchRecursive(TreeNode* node, int value) {
if (node == nullptr || node->value == value) {
return node;
}
if (value < node->value) {
return searchRecursive(node->left, value);
}
return searchRecursive(node->right, value);
}
// 전위 순회
void preorderTraversal(TreeNode* node) {
if (node != nullptr) {
std::cout << node->value << " ";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
}
// 중위 순회
void inorderTraversal(TreeNode* node) {
if (node != nullptr) {
inorderTraversal(node->left);
std::cout << node->value << " ";
inorderTraversal(node->right);
}
}
// 후위 순회
void postorderTraversal(TreeNode* node) {
if (node != nullptr) {
postorderTraversal(node->left);
postorderTraversal(node->right);
std::cout << node->value << " ";
}
}
};
int main() {
BinaryTree bt;
bt.insert(15);
bt.insert(10);
bt.insert(20);
bt.insert(8);
bt.insert(12);
bt.insert(17);
bt.insert(25);
std::cout << "전위 순회: ";
bt.preorderTraversal(bt.root);
std::cout << std::endl;
std::cout << "중위 순회: ";
bt.inorderTraversal(bt.root);
std::cout << std::endl;
std::cout << "후위 순회: ";
bt.postorderTraversal(bt.root);
std::cout << std::endl;
int searchValue = 12;
TreeNode* result = bt.search(searchValue);
if (result) {
std::cout << searchValue << "가(이) 트리에 존재합니다." << std::endl;
} else {
std::cout << searchValue << "가(이) 트리에 존재하지 않습니다." << std::endl;
}
return 0;
}
작성자의 분석
TreeNode
노드
노드안에 값이 있고
또 자식 노드 2개 가 있습니다.
BinaryTree
트리
트리는 노드를 담을 수 있습니다.,
최상위 노드를 가지고 자식의 자식의 ... 노드들을 찾을 수 있습니다.
void BinaryTree::insert(int value)
현재 트리에 노드가 없으면 최상위 노드를 만들고
있을 경우 그 루트노드에 새로운 노드를생성하는 조건을 가지고 있음
void insertRecursive(TreeNode* node, int value)
비교할 노드와 값을 가지고
노드의 값과 매개변수 값을 비교후
노드 값보다 작으면 왼쪽 크면 오른쪽으로
또 조건 왼쪽이나 오른쪽 노드가 비었다면 그자리에 새로운 노드
만약있다면 그 노드에 또 다시 값 비교 하는 과정
// 탐색 함수
TreeNode* search(int value) {
return searchRecursive(root, value);
}
최상위 루트부터 탐색 시작
TreeNode* searchRecursive(TreeNode* node, int value)
1. 노드가 없거나 같으면 그대로 루트 노드
2. 값이 현재 노드보다 낮으면 왼쪽 루트 로 탐색
3. 값이 클 경우 오른쪽 노드 탐색
예시
15
/ \
10 20
/ \ / \
8 12 17 25
// 전위 순회
void preorderTraversal(TreeNode* node)
노드가 없을 때까지
왼쪽 노드 오른쪽 노드 순회
루트, 왼쪽, 오른쪽
이 순회 방식은 트리의 구조를 그대로 유지하면서 루트 노드를 먼저 처리하고, 그 다음에 자식 노드를 처리하기 때문에, 주로 트리의 복사나 트리의 구조를 출력하는 데 유용
15, 10, 8, 12, 20, 17, 25
// 중위 순회
void inorderTraversal(TreeNode* node)
왼쪽 루트 오른쪽으로 순회
8, 10, 12, 15, 17, 20, 25
오름 차순 처럼
이진 탐색 트리에서 모든 노드를 오름차순으로 방문
// 후위 순회
void postorderTraversal(TreeNode* node)
왼쪽, 오른쪽, 루트 순으로 순
8, 12, 10, 17, 25, 20, 15
서브트리를 먼저 모두 방문한 후에 루트 노드를 방문하는 방식입니다. 후위 순회는 주로 트리의 모든 자식 노드를 먼저 처리한 후 부모 노드를 처리할 때 유용
BinaryTree bt;
bt.insert(15);
bt.insert(10);
bt.insert(20);
bt.insert(8);
bt.insert(12);
bt.insert(17);
bt.insert(25);
15 넣고 10 과 비교후 왼쪽 20 과 비교후 오른쪽 이과정 반복
여기서 궁금했던 노드 삭제 와 초기화
// 삭제 함수
TreeNode* deleteNode(TreeNode* root, int value) {
if (root == nullptr) {
return root; // 노드가 없으면 그대로 반환
}
if (value < root->value) {
root->left = deleteNode(root->left, value); // 왼쪽 서브트리로 이동
} else if (value > root->value) {
root->right = deleteNode(root->right, value); // 오른쪽 서브트리로 이동
} else {
// 노드가 발견됨
// 1. 자식이 없는 경우
if (root->left == nullptr && root->right == nullptr) {
delete root;
return nullptr;
}
// 2. 하나의 자식만 있는 경우
else if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
// 3. 두 개의 자식이 있는 경우
else {
// 직접 후계자를 찾기
TreeNode* temp = root->right;
while (temp && temp->left != nullptr) {
temp = temp->left;
}
root->value = temp->value; // 값을 대체
root->right = deleteNode(root->right, temp->value); // 후계자를 삭제
}
}
return root; // 수정된 루트 노드를 반환
}
리프 노드를 삭제할 때: 자식이 없는 노드를 삭제합니다.
하나의 자식을 가진 노드를 삭제할 때: 노드의 자식이 하나만 있을 경우 그 자식을 가져옵니다.
해당 노드가발견되었고
left가 비었다면 right가 있다는거고
temp에 right 값 저장해주고 right 의 부모 즉 현재 삭제할 노드 삭제후 삭제 한 노드에 가지고 있던
노드를 넣어주어서 노드를 높혀서 노드가 끊기지 않게하는 것
두 개의 자식을 가진 노드를 삭제할 때: 이 경우는 조금 복잡합니다. 일반적으로 다음 두 가지 방법 중 하나로 처리합니다:
직접 후계자(Right Child의 가장 왼쪽 자식)를 찾고, 노드를 삭제하고 그 값을 대체합니다.
직접 선행자(Left Child의 가장 오른쪽 자식)를 찾고, 노드를 삭제하고 그 값을 대체합니다.
right중 가장 작은 값이니 루트가 20이라면 루트보다 크면서 다른 루트보다 작은 예로들면
21노드로 현재노드를 21노드로 바꿔주고 어려우니 다시 분
삭제할 노드 발견:
현재 삭제할 노드(20)를 찾습니다
직접 후계자 찾기:
오른쪽 서브트리에서 가장 작은 값을 가진 노드(21)를 찾습니다.
이 노드는 20보다 크고, 오른쪽 서브트리에서 가장 왼쪽에 위치한 노드입니다.
값 대체:
20의 값을 21로 바꿉니다. 이때 20은 여전히 트리에 존재하지만, 값이 21로 바뀌었기 때문에 이제 20의 값은 21이 됩니다.
직접 후계자 삭제:
이제 원래의 21 노드를 삭제해야 합니다. 21은 더 이상 트리에서 필요하지 않으므로 삭제합니다.
21은 왼쪽 자식이 없기 때문에 부모 노드에서 21을 삭제하고, 21의 오른쪽 자식이 있다면 그 자식을 부모의 자식으로 연결합니다.
흐음 이렇게 하면 삭제보다는 대체라는 느낌이 강합니다.
노드의 자식도 옮기지않고 그저 20의 값을 21로 변경하고 원래 21번 위치를 제거한 것 뿐이
만약 해당 노드 값뿐만 아니라 다른것도 삭제해야된다면이란
조건을 예로들면 이게 ai노드였다면 순서 정하는 거였을텐데
그냥 값 20의 감지 노드를 값을 21로바꾸고
원래 21의 공격 노드를 삭제한거라 생각하면 좀 그렇습니다
그것에 대해 알아본결과
가장 간단하게 다른트리를 사용하면 됩니다..
이게 무슨 회피냐.. 가 아닌
해당 기능에 필요한트리 혹은 코드를 사용하는것으로 이해하면 됩니다.
그렇지 않으면 적합 하지않은 자료구조로 기능을 바꾸고 하면 오히려 효율은 안좋을겁니다
예로들면 검을 들고 원거리 공격 하겠다는 행동으로 생각합니다.
검을 길게 만들다던가 검을 던진다던가 하는 행동을 하면 이상하지 않을가요?
너무 길면 사용자가 힘들거고 던진다면 다시 사용하기 번거럽고
물론 검기가 안나간다는 조건이 있어야합니다.검기가 날라가면 예외죠
이렇게 이번에는 이진 탐색 노드를 알아봤습니다.