BinSrchTree.h : 이진 탐색 트리 클래스

#ifndef ___BinSrchTree

#define ___BinSrchTree

//BinSrchTree.h : 이진 탐색 트리 클래스

#include "BinaryTree.h"

class BinSrchTree : public BinaryTree{

public:

BinSrchTree(void){}

~BinSrchTree(void){}

//이진 탐색 트리의 탐색 연산

BinaryNode* search(int key) {

BinaryNode* node = searchRecur(root, key);

if (node != NULL)

printf("탐색 성공 : 키값이 %2d인 노드 = 0x%x\n",

node->getData(), node);

else

printf("탐색 실패 : 키값이 %2d인 노드 없음\n", key);

return node;

}

//키 값으로 노드를 탐색하는 함수 (순환적인 방법)

//n을 루트로 갖는 서브트리에서 key를 키값으로 갖는 노드 탐색 함수

BinaryNode* searchRecur(BinaryNode *n, int key){

if (n == NULL)return NULL; //n이 NULL

if (key == n->getData()) //key == 현재노드의 data

return n;

else if (key < n->getData()) //key < 현재노드의 data

return searchRecur(n->getLeft(), key);

else

return searchRecur(n->getRight(), key); //key > 현재노드의 data

}

//키 값으로 노드를 탐색하는 함수 (반복적인 함수) : 효율성을 따지면 반복적인 함수가 훨씬 우수하다.

BinaryNode* searchIter(BinaryNode* n, int key) {

while (n != NULL) {

if (key == n->getData()) //key == 현재노드의 data

return n;

else if (key < n->getData()) //data < key

n = n->getLeft();

else                                    //data > key

n = n->getRight();

}

return NULL;

}

//이진 탐색 트리의 삽입 연산

void insert(BinaryNode* n) {

if (n == NULL) return;

if (isEmpty()) root = n;

else insertRecur(root, n);

}

//일반 함수로 구현(순환적인 방법)

//r을  루트로 갖는 서브트리에 새로운 노드 n을 삽입하는 함수

void insertRecur(BinaryNode* r, BinaryNode* n){

if (n->getData() == r->getData())

return;

else if (n->getData() < r->getData()) {

if (r->getLeft() == NULL)

r->setLeft(n);

else

insertRecur(r->getLeft(), n);

}

else {

if (r->getRight() == NULL)

r->setRight(n);

else

insertRecur(r->getRight(), n);

}

}

//이진 탐색 트리의 삭제 연산

void remove(int key){

if (isEmpty()) return; //빈 트리이면 return

//없앨 노드와 그 노드의 부모 노드를 찾는다.

BinaryNode* parent = NULL; //없앨 노드의 부모

BinaryNode* node = root; //없앨 노드

while (node != NULL && node->getData() != key) {

parent = node;

node = (key < node->getData())

? node->getLeft() : node->getRight();

}

//없앨 노드가 트리에 없음

if (node == NULL) {

printf(" Error : key is not in the tree!\n");

}

//없앨 노드가 트리에 있음

else remove(parent, node);

}

//parent를 부모로 갖는 노드 node를 이진 탐색 트리에서 삭제하는 함수

void remove(BinaryNode* parent, BinaryNode* node) {

//case 1: 삭제하려는 노드가 단말 노드일 경우

if (node->isLeaf()) {

if (parent == NULL) // node == root인 경우 => 공백상태가 됨

root = NULL;

else {

if (parent->getLeft() == node)

parent->setLeft(NULL);

else parent->setRight(NULL);

}

}

//case 2: 삭제하려는 노드가 왼쪽이나 오른쪽 자식만 갖는 경우

else if (node->getLeft() == NULL || node->getRight() == NULL) {

//삭제할 노드의 유일한 자식 노드 =>child

BinaryNode* child = (node->getLeft() != NULL)

? node->getLeft() : node->getRight();

//삭제할 노드가 루트이면 ==> child가 새로운 root가 됨

if (node == root) root = child;

//아니면 ==> 부모 노드의 자식 노드 child를 직접 연결

else {

if (parent->getLeft() == node)

parent->setLeft(child);

else

parent->setRight(child);

}

}

//case 3: 삭제하려는 노드가 두개의 자식이 모두 있는 경우

else {

//삭제하려는 노드의 오른쪽 서브트리에서 가장 작은 노드를 탐색

//succ => 후계 노드: 오른쪽 서브트리에서 가장 key가 작은 노드

//succp => 후계 노드의 부모 노드

BinaryNode* succp = node;

BinaryNode* succ = node->getRight();

while (succ->getLeft() != NULL) { //후계 노드 탐색

succp = succ; //후계 노드의 부모 노드

succ = succ->getLeft(); //후계 노드

}

//후계 노드의 부모와 후계 노드의 오른쪽 자식을 직접 연결

if (succp->getLeft() == succ)

succp->setLeft(succ->getRight());

else                                //후계 노드가 삭제할 노드의 바로 오른쪽 자식인 경우

succp->setRight(succ->getLeft());

//후계 노드 정보를 삭제할 노드에 복사

node->setData(succ->getData());

//삭제할 노드를 후계 노드로 변경 : 실제로는 후계 노드가 제거됨

node = succ;

}

delete node; //메모리 동적 해제

}

};

#endif // !___BinSrchTree