C++로 쉽게 풀어쓴 자료구조 : 9장, 이진 탐색 트리

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 9장. 이진 탐색 트리

이진 탐색 트리는 이진트리 기반의 탐색을 위한 자료구조로 효율적인 탐색 작업을 위한 구조이다.

 

1) 모든 노드는 유일한 키를 갖는다.

2) 왼쪽 서브트리의 키들은 루트의 키보다 작다.

3) 오른쪽 서브트리의 키들은 루트의 티보다 크다.

4) 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

정의 9.1 245페이지

Binary Search Tree ADT

데이터: Binary Search Tree의 특성을 만족하는 이진트리: 어떤 node x의 왼쪽 서브트리의 key들은 x의 key보다 작고, 오른쪽의 서브트리의 key들은 x의 key보다 크다. 이때 왼쪽과 오른쪽 서브트리도 모두 이진 탐색 트리이다.

 

연산:

- insert(n): 이진탐색트리의 특성을 유지하면서 새로운 노드 n을 이진 탐색 트리에 삽입한다.

- remove(n): 이진 탐색 트리의 특성을 유지하면서 노드 n을 트리에서 삭제한다.

- search(key): 키 값이 key인 노드를 찾아 반환한다.

 

삽입 연산

insert (root, n)

if KEY(n) = KEY(root)
    then return;
else if KEY(n) < KEY(root) then
    if LEFT(root) = NULL
        then LEFT(root) <- n;
        else insert(LEFT(root), n);
    else
        if RIGHT(root) = NULL
        then RIGHT(root) <- n;
        else insert(RIGHT(root), n);

 

 

삭제 연산

노드 삭제를 위해서 먼저 노드를 탐색해야되는 점은 삽입과 동일하다. 삭제할 노드를 먼저 찾아야한다. 노드의 삭제는 3가지 경우를 고려해야 한다.

 

1) 삭제하려는 노드가 leaf node인 경우.

2) 삭제하려는 노드가 왼쪽이나 오른쪽 서브트리 중 하나만 갖고있는 경우.

3) 삭제하려는 노드가 양쪽 두개의 서브트리를 갖고있는 경우.

 

◆ case1: 삭제하려는 노드가 단말 노드인 경우

이 경우는 단말노드 아래 다른 노드가 없으니 그냥 단말노드만 지우면 끝난다. 단말 노드를 지운다는 것은 단말 노드의 부모를 찾아 부모 노드의 link_field를 nullptr로 만들면된다. 이후 연결이 끊어진 단말노드는 메모리를 반환시키면 제거된다.

 

◆ case2: 삭제하려는 노드가 하나의 서브트리만 갖고있는 경우

이 경우는 삭제하려는 노드를 삭제후 삭제된 노드의 남겨진 서브트리를 부모 노드에 연결해주면 된다.

          30                                30
         /  \         Delete 60            /   \
       20     60      --------->         20     80 
     /    \     \                      /    \  
    10     22     80                  10     22
   /  \   /  \                       /  \   /  \  
  3   11 21  25                     3   11 21  25

 

삭제를 위해서 부모노드와 자식노드를 알아야 한다.

 

◆ case3: 삭제하려는 노드가 두개의 서브트리를 갖고있는 경우

가장 복잡한 경우이다. 문제점은 서브트리에 있는 어떤 노드를 삭제한 위치로 가지고 오는가? 이다. 위의 경우에서 20을 제거한 후 10이나 22를 그냥 연결해버리면 이진탐색트리가 파괴된다. 따라서 삭제된 노드와 가장 값이 비슷한 노드 가 와야한다.

 

이는 삭제할 원소(예를들어 20)의 왼쪽 서브트리에서 가장 큰 값(11) 이나, 오른쪽 서브트리에서 가장 작은 값(21)이 삭제되는 노드와 가장 가깝다는 것을 알수있다. 그럼 둘중 어떤 노드를 선택해야 할까? 이는 상관이 없다. 책에서는 오른쪽 서브트리에서 가장 작은 값을 후계자로 선택하였다. 이를 찾는 방법은 삭제되는 노드의 오른쪽 서브트리의 root를 중심으로 왼쪽 link만 타고 nullptr을 만날때까지 계속 진행하면 된다.

 

이를 그림에 적용하면 20이 삭제된 후 21이 그자리를 대체하게 된다.

          30                                30
         /  \         Delete 20            /   \
       20     60      --------->         21     60 
     /    \     \                      /    \     \
    10     22     80                  10     22    80
   /  \   /  \                       /  \      \  
  3   11 21  25                     3   11     25

 

case3 의 코드를 보면서 이해하기 힘들었던 부분을 설명해 보겠다. 교제에 보면 다음과 같은 코드가 나온다.

else { // case3
    BinaryNode* succp = node; // 후계노드의 부모
    BinaryNode* succ = node->getRight(); // 후계노드
    while (succ->getLeft() != nullptr) {
        succp = succ;
        succ = succ->getLeft();
    }
    // 후계 노드의 부모와 후계 노드의 오른쪽 자식을 연결
    if (succp->getLeft() == succ)
        succp->setLeft(succ->getRight());
    else
        succp->setRight(succ->getRight());

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

 

여기서 다음 코드에 대한 설명이 너무 부족하게 책에 적혀있다. 말로 표현하기는 복잡해서 간단히 설명하고 넘어가신 것 같은데, 읽는 입장에서는 이 4줄만 1시간 넘개 생각하고 또 생각해야했다....

if (succp->getLeft() == succ)
    succp->setLeft(succ->getRight());
else
    succp->setRight(succ->getRight());

 

위의 코드를 명확이 이해할면 이전까지의 tree 모형이 아닌 다음과 같은 tree 또한 생각 해줘야 한다. 이전까지 책에서는 하나의 모델만 보여주면서 설명해주었는데 이러한 상황에서 위의 코드를 보면 말이되지 않는다. succ의 오른쪽 노드는 nullptr인데 뭘 연결한단 말인가?

23이 22의 오른쪽 node가 되는 경우를 생각해야 했다. 따라서 while 문이 left가 nullptr일때까지 반복하게 되면 succ가 22 node가 되고, succp가 26 node가 된다. 이상태 에서

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

 

을 진행하면 참이 되고 22와 26의 연결을 끊고, 동시에 26과 23을 연결시켜줘야 한다. 따라서

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

 

위의 코드까지 실행되면 23은 26과 연결된다. 이후의 else 부분의 코드는 후계 코드가 삭제할 node의 바로 오른쪽 자식인 경우에만 해당된다.

 

전체 코드는 다음과 같으며 이전시간에 사용했던 BinaryNode.h와 BinaryTree.h를 포함시켜줘야 한다.

 

BInSrchTree.h

#pragma once
#include "BinaryTree.h"

class BinSrchTree : public BinaryTree {
public:
	BinSrchTree(void) {}
	~BinSrchTree(void) {}

	BinaryNode* search(int key);
	BinaryNode* searchIter(BinaryNode* n, int key); // 반복문을 사용하는 방법
	//BinaryNode* searchRecur(BinaryNode* n, int key); // 재귀를 사용하는 방법

	void insert(BinaryNode* n);
	void insertRecur(BinaryNode* r, BinaryNode* n);

	void remove(int key);
	void remove(BinaryNode* parent, BinaryNode* node);
};

BinaryNode* BinSrchTree::search(int key)
{
	BinaryNode* node = searchIter(root, key);
	if (node != nullptr)
		std::cout << "탐색 성공: 키값이 " << node->getData() << "인 노드 = " << node << std::endl;
	else
		std::cout << "탐색 실패!" << std::endl;
	return node;
}

BinaryNode* BinSrchTree::searchIter(BinaryNode* n, int key) {
	while (n != nullptr) {
		if (key == n->getData())
			return n;
		else if (key < n->getData())
			n = n->getLeft();
		else
			n = n->getRight();
	}
	return NULL;
}

//BinaryNode* BinSrchTree::searchRecur(BinaryNode* n, int key) {
//	if (n == nullptr) return NULL;
//	if (key == n->getData()) return n;
//	else if (key < n->getData())
//		return searchRecur(n->getLeft(), key);
//	else
//		return searchRecur(n->getRight(), key);
//}

void BinSrchTree::insertRecur(BinaryNode* r, BinaryNode* n)
{
	if (n->getData() == r->getData()) return;
	else if (n->getData() < r->getData()) {
		if (r->getLeft() == nullptr)
			r->setLeft(n);
		else
			insertRecur(r->getLeft(), n);
	}
	else {
		if (r->getRight() == nullptr)
			r->setRight(n);
		else
			insertRecur(r->getRight(), n);
	}
}

void BinSrchTree::insert(BinaryNode* n)
{
	if (n == nullptr) return;
	if (isEmpty()) root = n;
	else insertRecur(root, n);
}

void BinSrchTree::remove(BinaryNode* parent, BinaryNode* node)
{
	if (node->isLeaf()) { // case1
		if (parent == nullptr) // 삭제할 노드가 root이면 부모는 null이다.
			node->setData(NULL); // 삭제할 노드를 null값으로
		else { // 아닐경우 부모의 자식을 null로
			if (parent->getLeft() == node)
				parent->setLeft(nullptr);
			else
				parent->setRight(nullptr);
		}
	}
	else if (node->getLeft() == nullptr || node->getRight() == nullptr){ // case2
		BinaryNode* child = (node->getLeft() == nullptr) ? node->getRight() : node->getLeft();
		if (node == BinSrchTree::root)
			root = child;
		else {
			if (parent->getLeft() == node)
				parent->setLeft(child);
			else
				parent->setRight(child);
		}
	}
	else { // case3
		BinaryNode* succp = node; // 후계노드의 부모
		BinaryNode* succ = node->getRight(); // 후계노드
		while (succ->getLeft() != nullptr) {
			succp = succ;
			succ = succ->getLeft();
		}
		// 후계 노드의 부모와 후계 노드의 오른쪽 자식을 연결
		if (succp->getLeft() == succ)
			succp->setLeft(succ->getRight());
		else
			succp->setRight(succ->getRight());

		node->setData(succ->getData());
		node = succ;
	}
	delete node;
}

void BinSrchTree::remove(int key)
{
	if (isEmpty()) return;
	// 우선 삭제할 노드와 그 부모 노드를 찾는다.
	BinaryNode* parent = nullptr;
	BinaryNode* node = root;

	while (node != nullptr && node->getData() != key) {
		parent = node;
		node = (key < node->getData()) ? node->getLeft() : node->getRight();
	}

	if (node == nullptr) {
		std::cout << "Error: key is not in the tree!\n";
		return;
	}
	else remove(parent, node);
}

 

 

main.cpp

#include "BinSrchTree.h"

using namespace std;

int main()
{
    BinSrchTree tree;
    
    tree.insert(new BinaryNode(35));
    tree.insert(new BinaryNode(18));
    tree.insert(new BinaryNode(7));
    tree.insert(new BinaryNode(26));
    tree.insert(new BinaryNode(12));
    tree.insert(new BinaryNode(3));
    tree.insert(new BinaryNode(68));
    tree.insert(new BinaryNode(22));
    tree.insert(new BinaryNode(30));
    tree.insert(new BinaryNode(99));

    tree.levelorder();
    cout << endl;
    tree.search(26);
    tree.search(25);
    cout << endl;
    cout << "case1 : 노드 3 삭제";
    tree.remove(3);
    tree.levelorder();
    cout << endl;
    cout << "case2 : 노드 68 삭제";
    tree.remove(68);
    tree.levelorder();
    cout << endl;
    cout << "case3 : 노드 18 삭제";
    tree.remove(18);
    tree.levelorder();
}

 

결과는 다음과 같다.

.

 

---

2) 나의 현황

◆ 와 Effective C++를 2쳅터 읽었는데 와... 초반부라 막 어렵지 않아서 그런지 너무 재미있다. 와 C++이 너무 좋다. 진짜 뇌를 가격하면서 머리 뽑히듯 생각하는걸 좋아하는데, 이에 걸맞는 언어가 C++인것 같다. 하루에 2쳅터 정도씩만 해서 느긋하게 읽을 생각이다.