루트 노드부터 나무처럼 분할되는 형태의 자료구조를 트리라한다.이중 이진 트리는 분할이 2개씩 되는 트리를 의미하며 노드가 가진 데이터가 대소관계의 따라 탐색의 유리하도록 정렬된경우에는 이진 탐색 트리라한다.( 작으면 왼쪽, 크면 오른쪽으로 정렬 ) 이름에 걸맞게 이진 트리는 탐색시 트리의 레벨이 깊어질수록, 자식 노드들이 균등하다는 가정하에, 많은 양을 한번에 제할수있어 속도가 굉장히 빠르다.
■ 구현 ( 설계 )
InsertNode( key, data )
DeleteNode( key )
SearchData( key )
ClearTree( )
키와 데이터 값을 통해 삽입, 검색, 삭제 가 가능한 트리를 만들것이다. DeleteNode( .. ), ClearTree( .. ) 둘다 삭제하는 함수이기는 하지만 ClearTree( .. )의 경우는 후위 순회 방식으로 단순히 모든 노드를 삭제하는 식으로 구현할 것이고, DeleteNode( .. ) 의 경우는 삭제하려는 노드가 가진 자식 노드의 갯수 여부에 따라 별도의 노드간 교환 처리 작업이 들어가는 식으로 구현할것이다.
■ 구현 ( 헤더 )
[BSTreeNode.h ]
#pragma once
typedef int KEY;
typedef int DATA;
struct BSTreeNode
{
KEY key;
DATA data;
BSTreeNode* parentNode;
BSTreeNode* leftNode;
BSTreeNode* rightNode;
};
|
구현 편의를 위해 노드가 부모의 노드포인터를 가지도록 구성했다.
[BSTree.h]
#pragma once
#include "BSTreeNode.h"
typedef int SIZE;
class BSTree
{
private:
BSTreeNode* rootNode = nullptr;
SIZE nodeCnt = 0;
private:
BSTreeNode* CreateNode(const KEY& key, const DATA& data,
BSTreeNode* parentNode, BSTreeNode* left, BSTreeNode* right);
void FreeNode(BSTreeNode*& node);
private:
void ClearTree(BSTreeNode * rootNode);
public:
bool InsertNode(const KEY& key, const DATA& data);
bool DeleteNode(const KEY& key);
bool SearchData(const KEY& key, DATA* data);
void ClearTree();
public:
inline const SIZE& GetSize() const { return this->nodeCnt; }
private:
BSTree();
public:
~BSTree();
public:
static BSTree* Create(const KEY& key, const DATA& data);
};
|
■ 구현 ( 코드 )
[BSTree.cpp]
#include "BSTree.h"
BSTreeNode * BSTree::CreateNode(const KEY & key, const DATA & data,
BSTreeNode* parentNode, BSTreeNode * left, BSTreeNode * right)
{
BSTreeNode* node = new BSTreeNode;
node->key = key;
node->data = data;
node->parentNode = parentNode;
node->leftNode = left;
node->rightNode = right;
this->nodeCnt++;
return node;
}
void BSTree::FreeNode(BSTreeNode*& node)
{
delete node;
node = nullptr;
this->nodeCnt--;
}
void BSTree::ClearTree(BSTreeNode * rootNode)
{
if (!rootNode)
return;
ClearTree(rootNode->leftNode);
ClearTree(rootNode->rightNode);
FreeNode(rootNode);
}
bool BSTree::InsertNode(const KEY & key, const DATA & data)
{
BSTreeNode* curNode = this->rootNode;
while (true)
{
if (curNode->key > key)
{
if (!curNode->leftNode)
{
curNode->leftNode = CreateNode(key, data, curNode, nullptr, nullptr);
}
curNode = curNode->leftNode;
}
else if(curNode->key < key)
{
if (!curNode->rightNode)
{
curNode->rightNode = CreateNode(key, data, curNode, nullptr, nullptr);
}
curNode = curNode->rightNode;
}
else
{
return false;
}
}
return true;
}
bool BSTree::DeleteNode(const KEY & key)
{
BSTreeNode* curNode = this->rootNode;
while (curNode)
{
if (curNode->key > key)
{
curNode = curNode->leftNode;
}
else if(curNode->key < key)
{
curNode = curNode->rightNode;
}
else
{
if (curNode->leftNode && curNode->rightNode)
{
/* 현재 노드가 보유하는 왼쪽의 모든
자식 노드들중 가장 큰 키값을 가진
노드를 현재 노드로 대체함*/
BSTreeNode* bigNode = curNode->leftNode;
while (bigNode->rightNode)
{
bigNode = bigNode->rightNode;
}
if (bigNode->parentNode != curNode)
{
bigNode->parentNode->rightNode = bigNode->leftNode;
/* curNode가 삭제 대상일경우 curNode->leftNode가
곧 bigNode가 되서 예외처리 함 */
bigNode->leftNode = curNode->leftNode;
}
bigNode->parentNode = curNode->parentNode;
bigNode->rightNode = curNode->rightNode;
if (curNode->parentNode)
{
if (curNode->parentNode->leftNode == curNode)
{
curNode->parentNode->leftNode = bigNode;
}
else
{
curNode->parentNode->rightNode = bigNode;
}
}
FreeNode(curNode);
}
else if (curNode->leftNode)
{
if (curNode->parentNode)
{
if (curNode->parentNode->leftNode == curNode)
{
curNode->parentNode->leftNode = curNode->leftNode;
}
else
{
curNode->parentNode->rightNode = curNode->leftNode;
}
}
FreeNode(curNode);
}
else if (curNode->rightNode)
{
if (curNode->parentNode)
{
if (curNode->parentNode->leftNode == curNode)
{
curNode->parentNode->leftNode = curNode->rightNode;
}
else
{
curNode->parentNode->rightNode = curNode->rightNode;
}
}
FreeNode(curNode);
}
else
{
if (curNode->parentNode)
{
if (curNode->parentNode->leftNode == curNode)
{
curNode->parentNode->leftNode = nullptr;
}
else
{
curNode->parentNode->rightNode = nullptr;
}
}
FreeNode(curNode);
}
}
}
return false;
}
bool BSTree::SearchData(const KEY & key, DATA * data)
{
BSTreeNode* curNode = this->rootNode;
while (curNode)
{
if (curNode->key > key)
{
curNode = curNode->leftNode;
}
else if (curNode->key < key)
{
curNode = curNode->rightNode;
}
else
{
*data = curNode->data;
return true;
}
}
return false;
}
void BSTree::ClearTree()
{
ClearTree(this->rootNode);
}
BSTree::BSTree()
{
}
BSTree::~BSTree()
{
}
BSTree * BSTree::Create(const KEY & key, const DATA& data)
{
BSTree* tree = new BSTree;
tree->rootNode = tree->CreateNode(key, data, nullptr, nullptr, nullptr);
return tree;
}
|
재귀 형식이 아니라 반복문 식으로 구현했더니 좀 난잡한 감이있다. 하지만 어려운 로직은 아니기 때문에 천천히 읽으면 쉽게 이해가 갈것이다.
■ 실행 결과
[Main.cpp]
#include <iostream>
#include "BSTree.h"
using namespace std;
int main()
{
BSTree* tree = BSTree::Create(30, 30);
tree->InsertNode(20, 20);
tree->InsertNode(15, 15);
tree->InsertNode(13, 13);
tree->InsertNode(17, 27);
tree->InsertNode(25, 25);
tree->InsertNode(40, 40);
tree->InsertNode(35, 35);
tree->InsertNode(45, 45);
cout << " Current tree size : " << tree->GetSize() << endl;
tree->DeleteNode(20);
tree->DeleteNode(40);
cout << " Current tree size : " << tree->GetSize() << endl;
DATA out = 0;
tree->SearchData(15, &out);
cout << " 15 treeNode data : " << out << endl;
tree->SearchData(35, &out);
cout << " 35 treeNode data : " << out << endl;
tree->SearchData(45, &out);
cout << " 35 treeNode data : " << out << endl;
tree->ClearTree();
cout << " Current tree size : " << tree->GetSize() << endl;
delete tree;
tree = nullptr;
return 0;
}
|
■ 소스코드
Downloading_BSTree_vs2015_project
댓글 없음:
댓글 쓰기