/*
이진탐색트리, Binary Search Tree
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
template <typename K, typename E>
class Dictionary
{
public:
virtual bool IsEmpty() const = 0;
virtual pair<K, E> *Get(const K&) const = 0; //특정 키를 반환
virtual void Insert(const pair<K, E>&) = 0;
virtual void Delete(const K&) = 0;
};
template <typename T>
class TreeNode
{
public:
T data;
TreeNode<T> *leftChild;
TreeNode<T> *rightChild;
TreeNode(T temp) :data(temp), leftChild(NULL), rightChild(NULL)
{
}
};
template <typename K, typename E>
class BST :public Dictionary<K, E>
{
private:
TreeNode<pair<K, E>> *root;
public:
BST() :root(NULL)
{
}
bool IsEmpty() const
{
return (root == NULL);
}
pair<K, E> *Get(const K &k) const
{
return Get(root, k);
}
pair<K, E> *Get(TreeNode<pair<K, E>> *p, const K &k) const//재귀 버전
{
if (!p) //노드가 없을 경우
{
cout << "없는 노드입니다" << endl;
return 0;
}
if (k < p->data.first) //키 값이 더 작을 경우 왼쪽
return Get(p->leftChild, k);
if (k > p->data.first) //키 값이 클 경우 오른쪽
return Get(p->rightChild, k);
return &p->data;
}
//위와 동일한 역할을 하는 비재귀 함수
/*
pair<K, E> *Get(const K &k)
{
TreeNode<pair<K, E>> *currentNode = root;
while (currentNode)
{
if (k < currentNode->data.first)
currentNode = currentNode->leftChild;
else if (k > currentNode->data.first)
currentNode = currentNode->rightChild;
else
return ¤tNode->data;
}
//no matching pair
return 0;
}
*/
pair<K, E> *RankGet(int r) //r번째로 작은 pair를 반환
{
TreeNode<pair<K, E>> *currentNode = root;
while (currentNode)
{
if (r < getLeftSize()) //leftSize를 구하는 방법을 생각해봐야겠습니다. currentNode를 순회하는 함수를 만들어서 count++를 해야하나
currentNode = currentNode->leftChild;
else if (r > getLeftSize())
{
r -= getLeftSize();
currentNode = currentNode->rightChild;
}
else
return ¤tNode->data;
}
return NULL;
}
void Insert(const pair<K, E> &thePair)
{
TreeNode<pair<K, E>> *p = root, *pp = 0; //p 초기노드, pp 부모노드
while (p)
{
pp = p;
if (thePair.first < p->data.first)
p = p->leftChild;
else if (thePair.first > p->data.first)
p = p->rightChild;
else //일치할경우 해당 노드의 쌍의 원소항 갱신
{
p->data.second = thePair.second;
return;
}
}
p = new TreeNode<pair<K, E>>(thePair);
if (root)
{
// 현재 부모노드와 비교
if (thePair.first < pp->data.first)
pp->leftChild = p;
else
pp->rightChild = p;
}
else
root = p;
}
void Delete(const K &k) //consist.tistory.com/16 참고
{
TreeNode<pair<K, E>> *currentNode = root;
TreeNode<pair<K, E>> *deleteNode = NULL;
TreeNode<pair<K, E>> *parentNode = NULL;
int lastLocation = NULL; //왼쪽, 오른쪽 자식도 없는 경우 부모노드의 왼쪽 자식인지 오른쪽 자식인지 판별
//삭제할 노드를 찾는다
while (currentNode)
{
if (currentNode->data.first > k)
{
parentNode = currentNode;
currentNode = currentNode->leftChild;
lastLocation = 1;
}
else if (currentNode->data.first < k)
{
parentNode = currentNode;
currentNode = currentNode->rightChild;
lastLocation = 2;
}
else
{
deleteNode = currentNode;
break;
}
}
if (deleteNode == NULL)
{
cout << "삭제할 노드가 없습니다" << endl;
exit(1);
}
//말단노드에 도달할 때까지 삭제할 노드를 찾고 복사
while (currentNode)
{
if (deleteNode->leftChild)
{
currentNode = deleteNode->leftChild;
//왼쪽 자식에서 가장 큰 키 값은 오른쪽 자식
while (currentNode->rightChild)
{
parentNode = currentNode;
lastLocation = 2;
currentNode = currentNode->rightChild;
}
deleteNode->data = currentNode->data;
deleteNode = currentNode;
continue;
}
else if (deleteNode->rightChild)
{
currentNode = deleteNode->rightChild;
//오른쪽 자식에서 가장 작은 값은 왼쪽 자식
while (currentNode->leftChild)
{
parentNode = currentNode;
lastLocation = 1;
currentNode = currentNode->leftChild;
}
deleteNode->data = currentNode->data;
deleteNode = currentNode;
continue;
}
else //말단노드인 경우
{
switch (lastLocation)
{
case 1:
parentNode->leftChild = NULL;
deleteNode->~TreeNode();
delete deleteNode;
break;
case 2:
parentNode->rightChild = NULL;
deleteNode->~TreeNode();
delete deleteNode;
break;
}
}
cout << "삭제 완료" << endl;
return;
}
}
void Inorder(TreeNode<pair<K, E>> *tree) //중위 순회
{
if (tree != NULL)
{
Inorder(tree->leftChild);
cout << tree->data << " ";
Inorder(tree->rightChild);
}
}
void InorderTraversal()
{
Inorder(root);
cout << endl;
}
int getLeftSize()
{
int count = 1;
TreeNode<pair<K, E>> *currentNode = root;
if (currentNode != NULL)
{
currentNode = currentNode->leftChild;
count++;
}
return count;
}
template <typename K, typename E>
friend ostream &operator<<(ostream &os, const pair<K, E> &p); //pair<K, E> 출력 위해
};
template <typename K, typename E>
ostream &operator<<(ostream &os, const pair<K, E> &p)
{
os << "(" << p.first << ", " << p.second << ") ";
return os;
}
int main(void)
{
BST<int, char> intCharTree;
intCharTree.Insert(pair<int, char>(1, 'a'));
intCharTree.Insert(pair<int, char>(6, 'c'));
intCharTree.Insert(pair<int, char>(4, 'b'));
intCharTree.Insert(pair<int, char>(8, 'd'));
cout << "2번째 랭크: ";
cout << intCharTree.RankGet(2)->first << ", " << intCharTree.RankGet(2)->second << endl;
cout << "중위 순회 출력: ";
intCharTree.InorderTraversal();
cout << endl << "4, 'b' 삭제" << endl;
intCharTree.Delete(4);
cout << endl << "중위 순회 출력: ";
intCharTree.InorderTraversal();
cout << "4, 'b' 찾기: ";
if(!intCharTree.Get(4)==0)
cout << intCharTree.Get(4)->first << ", " << intCharTree.Get(4)->second << endl;
cout << "6, 'c' 찾기: ";
if (!intCharTree.Get(6) == 0)
cout << intCharTree.Get(6)->first << ", " << intCharTree.Get(6)->second << endl;
cout << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://stackoverflow.com/questions/2164942/how-can-i-store-a-pair-of-numbers-in-c, http://consist.tistory.com/16, https://social.msdn.microsoft.com/Forums/vstudio/en-US/59a7c476-ec12-4cca-b899-4fcdb4bcc0ee/error-c2143-missing-before-?forum=vcgeneral
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*RankGet 함수를 어떤식으로 사용해야할지 아직 잘 모르겠습니다. 댓글로 알려주시면 정말 감사하겠습니다!
*pair<class, class> 라는 개념을 처음 접했기 때문에 https://stackoverflow.com/questions/2164942/how-can-i-store-a-pair-of-numbers-in-c에서 개념을 익혔습니다.
*Delete 함수는 http://consist.tistory.com/16 블로그를 참고했습니다.
*pair<class, class> << 연산자 오버로딩은 https://social.msdn.microsoft.com/Forums/vstudio/en-US/59a7c476-ec12-4cca-b899-4fcdb4bcc0ee/error-c2143-missing-before-?forum=vcgeneral 여기를 참고했습니다