개념/자료구조
이진 트리 (Binary Tree)
웅드
2023. 11. 29. 19:32
- 모든 Internal node가 두개 이하의 자식을 갖는 트리를 의미한다.
- Left child와 Right child 두개의 자식을 가질 수 있다.
Full Binary Tree
- 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있다.
레벨과 노드의 수 관계
- 레벨이 d일 때, 트리의 노드 수 N은 다음과 같다.
- N개의 노드를 가진 이진트리의 레벨 d는 다음과 같다.
Complete Binary Tree
- 모든 레벨에 노드가 꽉 차있음
- 힙은 완전이진트리 기반 자료구조이며 최댓값 혹인 최솟값을 빠르게 찾을 수 있는 자료구조이다.
이진트리 구현하기
- node 구조체
struct Node {
int data;
Node* parent; // 부모 노드
Node* leftChild; // 왼쪽 자식 노드
Node* rightChild; // 오른쪽 자식 노드
};
- BinarySearchTree class
class binarySearchTree {
public:
binarySearchTree() {
root = nullptr;
}
void insert(int elem);
Node* find(int elem);
void swap(Node* a, Node* b);
void erase(int elem);
void erase(Node* node);
void print(Node* node);
Node* getRoot();
private:
Node* root;
};
- BinarySearchTree::Insert 함수
void BinarySearchTree::insert(int elem){
Node* addNode = new Node; // 새로 삽입할 노드
// 맨 처음 삽입이라면 root에 넣어주기
if( root == nullprt ){
addNode -> data = elem;
addNode -> parent = nullptr;
addNode -> leftChild = nullptr;
addNode -> rightChild = nullptr;
root = addNode;
return;
}
// 현재 node를 가리키는 노드
Node* curNode = root;
while(1){
// input값이 현재 curNode가 가리키는 노드의 데이터값보다 작다면
while(curNode -> data > elem){
//curNode의 왼쪽 자식이 없다면
if(curNode -> leftChild == nullprt){
//curNode의 왼쪽 자식 노드값 설정해주고 부모 자식값 다시 설정하기
addNode -> data = elem
addNode -> parent = curNode;
addNode -> leftChild = nullptr;
addNode -> rightChild = nullptr;
curNode -> leftChild = addNode;
return;
}
// curNode의 왼쪽 자식이 존재하면
else {
//curNode가 자신의 왼쪽노드를 참조하게 한다.
curNode = curNode -> leftChild;
}
//input 값이 curNode가 가리키는 노드의 데이터값보다 같거나 크면
while(curNode -> data <= elem){
//오른쪽 자식값이 없다면 해당 자식 노드에 추가
if(curNode -> rightChild == nullptr){
addNode -> data = elem;
addNode -> parent = curNode;
addNode -> leftChild = nullptr;
addNode -> rightChild = nullptr;
curNode -> rightChild = addNode;
return;
}
//curNode의 오른쪽 자식이 존재하면 오른쪽 자식 노드를 참조하게 한다.
else {
curNode = curNode -> rightchild;
}
}
}
}
BinarySearchTree::find 함수
Node* BinarySearchTree::find(int elem){
// 트리가 비어있다면 nullptr 반환
if( curNode == nullptr ) {
return nullptr;
}
while(1){
//현재 찾는 값이 curNode가 가리키는 데이터 값보다 작으면
while ( curNode -> data > elem ){
//왼쪽 자식 노드로
curNode = curNode -> leftChild;
}
// 찾는 값이 curNode가 가리키는 데이터값보다 크거나 같으면
while ( curNode -> data <= elem ){
//elem값을 찾았다면
if ( curNode -> data == elem ) {
return curNode;
}
//찾지 못했다면 오른쪽 노드로
curNode = curNode -> rightChild;
}
// 만약 curNode가 nullptr이라면 elem 값은 존재하지 않는다.
if ( curNode == nullptr ) return nullptr;
}
}
BinarySearchTree::swap 함수
void binarySeachTree::swap(Node* a, Node* b) {
Node* temp = new Node;
temp -> data = b -> data;
b-> data = a -> data;
a -> data = temp -> data;
temp -> parent = b -> parent;
b -> parent = a -> parent;
a -> parent = temp -> parent;
temp -> leftChild = b -> leftChild;
b -> leftChild = a -> leftChild;
a -> leftChild = temp -> leftChild;
temp -> rightChild = b -> rightChild;
b -> rightChild = a -> rightChild;
a -> rightChild = temp -> rightChild;
delete(temp);
}
BinarySearchTree::erase 함수
제거할 때의 경우의 수가 4가지 존재한다.
- 노드가 leaf node일 때 -> 부모노드의 자식 노드값을 nullptr로 변경한다.
- 노드가 왼쪽 자식만 가지고 있을 때 -> 부모노드의 자식 노드값을 지우려는 노드에서 노드의 왼쪽자식 노드로 변경해준다.
- 노드가 오른쪽 자식만 가지고 있을 때
- 노드가 두개의 자식을 모두 가지고 있을 때 -> 노드의 왼쪽서브트리에서 제일 큰 값과 자신을 교체, 노드의 오른쪽 서브트리에서 제일 작은 값과 자신을 교체
void binarySearchTree::erase(int elem){
Node* delNode = find(elem);
if( delNode == nullptr ) return;
// 해당 원소가 leaf node라면
if(delNode -> leftNode == nullptr && delNode -> rightChild == nullptr){
if(delNode -> parent ->leftChild == delnode)
delNode -> parent -> leftChild = nullptr;
else
delNode -> parent -> rightChild = nullptr;
}
//해당 원소가 오른쪽 자식만 있을 경우
else if(delNode -> leftChild == nullptr) {
//만약 delNode가 del의 부모 노드의 왼쪽 자식이라면
if(delNode -> parent -> leftChild == delNode){
delNode -> parent -> leftChild = delNode -> rightChild;
}
//del노드가 부모노드의 오른쪽 자식이라면
else {
delNode -> parent -> rightChild = delNode -> rightChild;
}
//해당 원소의 오른쪽 자식의 부모노드를 해당 원소의 부모노드로 설정
delNode -> rightChild -> parent = delNode -> parent;
}
//해당 원소가 왼쪽 자식만 있는 경우
else if(delNode -> rightChild == nullptr) {
//만약 delNode가 del의 부모 노드의 왼쪽 자식이라면
if(delNode -> parent -> leftChild == delNode){
//부모노드의 왼쪽 자식을 해당 원소의 왼쪽 자식으로 설정
delNode -> parent -> leftChild = delNode -> leftChild;
}
else {
delNode -> parent -> rightChild = delNode -> leftChild;
}
//해당 원소의 왼쪽 자식의 부모노드를 해당 원소의 부모노드로 설정
delNode -> leftChild -> parent = delNode -> parent;
}
//해당 원소가 두 자식 다 있을 경우 오른쪽 서브트리에서 제일 작은 값과 교체
else {
//오른쪽 서브트리의 루트노드부터 시작
Node* curNode = delNode -> rightChild;
//오른쪽 서브트리의 제일 작은 노드까지
while (curNode -> leftChild != nullptr){
curNode = curNode -> leftChild;
}
//두 노드를 바꿔준다.
swap(curNode, delNode);
//해당 원소의 부모노드에서 해당 원소 제거
if( delNode -> parent -> leftChild == delNode)
delNode -> parent -> leftChild = nullptr;
else
delNode -> parent -> rightChild = nullptr;
}
delete(delNode);
}
매개변수가 int형이 아닌 노드 포인터 형으로 지우기
void binarySearchTree::erase(Node* node) {
//해당 원소가 leaf node 라면
if (node->leftChild == nullptr && node->rightChild == nullptr) {
//해당 원소의 부모노드에서 해당 원소 제거
if (node->parent->leftChild == node) node->parent->leftChild = nullptr;
else node->parent->rightChild = nullptr;
}
//해당원소가 오른쪽 자식만 있을 때
else if (node->leftChild == nullptr) {
//만약 del노드가 del의 부모노드의 왼쪽자식이라면
if (node->parent->leftChild == node) {
node->parent->leftChild = node->rightChild;
}
//del노드가 부모노드의 오른쪽자식이라면
else {
node->parent->rightChild = node->rightChild;
}
//해당원소의 오른쪽자식의 부모노드를 해당원소의 부모노드로 설정
node->rightChild->parent = node->parent;
}
//해당원소가 왼쪽 자식만 있을 때
else if (node->rightChild == nullptr) {
//del노드가 부모 노드의 왼쪽자식이라면
if (node->parent->leftChild == node) {
//부모노드의 왼쪽 자식을 해당원소의 왼쪽 자식으로 설정
node->parent->leftChild = node->leftChild;
}
else {
node->parent->rightChild = node->leftChild;
}
//해당원소의 왼쪽자식의 부모노드를 해당원소의 부모노드로 설정
node->leftChild->parent = node->parent;
}
//해당 원소가 두 자식 다 있을 때 오른쪽 서브트리에서 제일 작은값과 교체
else {
//오른쪽 서브트리의 루르노드부터 시작해서
Node* curNode = node->rightChild;
//오른쪽 서브트리의 제일 작은 노드까지
while (curNode->leftChild != nullptr) {
curNode = curNode->leftChild;
}
//두 노드를 바꿔주고
swap(curNode, node);
//해당 원소의 부모노드에서 해당 원소 제거
if (node->parent->leftChild == node) node->parent->leftChild = nullptr;
else node->parent->rightChild = nullptr;
}
delete(node);
}
binarySearchTree::print 함수
root 노드값보다 작은값이 왼쪽 서브트리, 큰 값이 오른쪽 서브트리에 저장되기 때문에 중위 순회를 하면 순서대로 출력된다.
void binarySearchTree::print(Node* node){
if( node == nullptr ) return;
print(node -> leftChild);
cout << node -> data;
print(node -> rightChild;
}
binarySearchTree::getRoot 함수
Node* binarySearchTree::getRoot(){
return root;
}
Test
int main() {
binarySearchTree* bst=new binarySearchTree();
bst->insert(5);
bst->insert(2);
bst->insert(3);
bst->insert(4);
bst->insert(1);
bst->insert(6);
bst->insert(7);
//출력
bst->print(bst->getRoot());
cout << '\n';
//3 지우기
bst->erase(3);
bst->print(bst->getRoot());
cout << endl;
//3 다시 추가
bst->insert(3);
bst->print(bst->getRoot());
cout << endl;
//3 하나 더 추가
bst->insert(3);
bst->print(bst->getRoot());
cout << endl;
//3노드를 매개변수로 줘서 3값 지우기
bst->erase(bst->find(3));
bst->print(bst->getRoot());
cout << endl;
//3노드 찾아서 데이터값 출력
cout<<bst->find(3)->data;
}
이진 트리의 용도
- Parse Tree : 수식 계산에 사용
- Heap : 정렬에 사용
- Binary Search Tree : 검색에 사용
반응형