1. Tree
- 트리는 노드로 구성된 자료구조이다.
트리의 기본 조건은 다음과 같다.
- 시작점을 나타내는 유일한 시작 노드인 'Root Node'를 가진다.
- Root Node는 0개 이상의 Child Node를 가진다.
- 해당 Child Node는 Parent Node로써 0개 이상의 Child Node를 가지고 있고, 이는 반복적으로 정의된다.
- 트리는 기본적으로, 사이클이 존재하지 않는다. 이는 Graph와의 차이점이다.
- 트리의 구성 요소
- Root: 트리의 unique한 시작 노드
- Node: 트리를 구성하는 단위
- Parent Node: 1개 이상의 Child Node를 갖는 선행 노드
- Child Node: 하나의 Parent Node를 갖는 후행 노드
- Level: Root Node를 기준으로 Tree의 Depth를 나타내는 척도
- Siblings: 동일 Level에 존재하는 노드사이의 관계
- Sub-Tree: 하나의 트리를 구성하는, Tree 내부에 Parent-Child 관계를 가진 작은 트리 구조
- Leaf Node: Child Node가 없는 노드
- Edge: Tree 사이를 연결하는 간선
2. Binary Tree
- 이진트리, 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
자식 노드를 각각 Left Child, Right Child라고 한다.
class Node
{
public:
int data;
Node* leftNode;
Node* rightNode;
Node(int val) : data(val)
{
leftNode = NULL;
rightNode = NULL;
}
};
3. Binary Search Tree
- Binary Search와 Linked list를 결합한 자료구조이다. 이는 이진탐색의 효율(O(logN)의 시간복잡도)와 연결리스트의 자료 입출력 연산(O(1)의 시간 복잡도)의 이점을 모두 살리는 것이 해당 자료구조의 특성이다.
- Binary Search Tree의 특징은 이진탐색의 특징인 '중복되는 원소가 없다'와 '원소가 정렬되어 있다'의 특징을 가진다.
- ADT
- MakeEmpty
- Boolean IsEmpty
- Boolean IsFull
- int Lengths
- RetrieveItem(ItemType& item, Boolean& found)
- InsertItem(ItemType item)
- DeleteItem(ItemType item)
- Print(ofstream& outFile)
- ResetTree(OrderType order)
- GetNextItem(ItemType& item, OrderType order, Boolean& finished)
- BST의 작동원리
- 노드 삽입
- 루트 노드가 비어있다면, 삽입 노드를 루트 노드로 채운다.
- 루트 노드가 존재한다면, 삽입 노드의 값과 비교하여 삽입 노드의 값이 작으면 루트 노드의 오른쪽, 크다면 왼쪽으로 보낸다.
- 이동 후, 해당 노드 자리가 비어있다면, 삽입 노드를 삽입한다.
- 이동 후, 해당 노드 자리가 비어있지 않다면, 상기 과정(2-3)을 반복한다.
- 노드 삭제
Case01.
- 삭제할 노드가 Leaf Node인 경우
- 해당 노드 삭제
- 삭제할 노드의 Child Node가 1개인 경우
- 해당 노드 삭제
- 삭제할 노드의 Child Node가 2개인 경우
- 삭제할 노드의 자리에 대신 채울 노드를 탐색해야 한다.
- 삭제할 노드의 왼쪽 서브 트리에서 최대 값 노드
- 삭제할 노드의 오른쪽 서브 트리에서 최소 값 노드
- 노드 검색
- Root 노드에서 시작한다.
- 값을 비교 후, 해당 노드의 값보다 작으면 왼쪽으로, 크면 오른쪽으로 이동한다.
- 일치하면 return 한다.
- 위의 과정을 참고하여, C++의 STL을 이용하여 구현한 것은 다음과 같다.
class Node
{
public:
int data;
Node* leftNode;
Node* rightNode;
Node(const int& data) : data(data) {}
};
class BinarySearchTree
{
private:
Node* root;
Node* _find(Node* location, const int& value)
{
if(!location)
return nullptr;
if(location->value == value)
return location;
else
{
if(location->value > value)
return _find(location->left, value);
else
return _find(location->right, value);
}
}
Node* _insert(Node* location, const int* value)
{
Node* parent;
while(location)
{
parent = location;
if(parent->value > value)
location = location->left;
else
location = location->right;
}
if(parent->value > value)
parent->left = new Node(value);
else if(parent->value < value)
parent->right = new Node(value);
else
std::cout << "Already Exist" << std::endl;
}
void _postorderTraversal(Node* location)
{
if(!location)
return;
this->_postorderTraversal(location->left);
this->_postorderTraversal(location->right);
}
public:
void insertNode(const int& value)
{
if(!this->root)
{
this->root = new Node(value);
return;
}
this->_insert(this->root, value);
}
Node* searchNode(const int& value)
{
Node* location = this->root;
if(!location)
return nullptr;
return this->_find(location, value);
}
void removeNode(const int& value)
{
Node* parent;
Node* targetToDelete;
Node* location = this->root;
while(location)
{
/*
* 노드를 삭제하기 위해 parent를 저장한다.
* 만일 노드를 삭제하면, parent의 ptr이 삭제 다음 노드를 가리킨다.
*/
if(location->left)
if(location->left->value == value)
parent = location;
else if(location->right)
if(location->right->value == value)
parent = location;
// parent를 찾은 뒤, 삭제할 노드를 찾아 저장한다.
if(location->value == value)
{
targetToDelete = location;
break;
}
// 만일, 현재 노드가 해당하지 않는다면 '탐색'한다.
else if(location->value > value)
location = location->left;
else
location = location->right;
}
// 만일, 삭제할 노드의 자식노드가 '왼쪽 하나'에만 존재한다면
if(targetToDelete->right == nullptr && targetToDelete->left != nullptr)
{
// parent가 존재하지 않는다면, 즉 해당 노드가 root라면
if(!parent)
{
// root노드의 다음 노드를 옮긴다.
this->root = targetToDelete->left;
delete targetToDelete;
}
// 만일, 해당 노드가 root가 아니라면,
else
{
// 만일, left 노드가 삭제할 노드라면
if(parent->left == targetToDelete)
// 삭제할 노드의 left의 left로 옮긴다.
parent->left = parent->left->left;
// 만일, right 노드가 삭제할 노드라면
else if(parent->right == targetToDelete)
// 삭제할 노드의 right의 left로 옮긴다.
parent->right = parent->right->left;
delete targetToDelete;
}
return;
}
// 만일, 삭제할 노드의 자식노드가 '오른쪽 하나'에만 존재한다면
else if(targetToDelete->right != nullptr && targetToDelete->left == nullptr)
{
if(!parent)
{
this->root = targetToDelete->right;
delete targetToDelete;
}
else
{
if(parent->left == targetToDelete)
parent->left = parent->left->right;
else if(parent->right == targetToDelete)
parent->right = parent->right->right;
delete targetToDelete;
}
return;
}
// 만일, 삭제할 노드의 자식 노드가 '양쪽 모두'에 존재한다면
// 2가지 방법을 선택한다.
// 1. 삭제할 노드의 왼쪽 서브트리에서 최대 값 노드를 대신 채운다.
// 2. 삭제할 노드의 오른쪽 서브트리에서 최소 값 노드를 대신 채운다.
else
{
// sol1. left sub tree, max value
Node *tmp;
location = targetToDelete->left;
if(location->right)
{
while(location->right)
{
tmp = location;
location = location->right;
}
int tmpValue = tmp->right->value;
tmp->right->value = targetToDelete->value;
targetToDelete->value = tmpValue;
}
else if(location->left)
{
while(location->left)
{
tmp = location;
location = location->left;
}
int tmpValue = tmp->left->value;
tmp->left->value = targetToDelete->value;
targetToDelete->value = tmpValue;
delete tmp->left;
tmp->left = nullptr;
}
return;
// sol2. right sub tree, min value
Node *tmp;
location = targetToDelete->right;
if(location->left)
{
while(location->left)
{
tmp = location;
location = location->left;
}
int tmpValue = tmp->left->value;
tmp->left->value = targetToDelete->value;
targetToDelete->value = tmpValue;
}
else if(location->right)
{
while(location->right)
{
tmp = location;
location = location->right);
}
int tmpValue = tmp->right->value;
tmp->right->value = targetToDelete->value;
targetToDelete->value = tmpValue;
delete tmp->right;
tmp->right = nullptr;
}
return;
}
}
}
