이진 탐색 트리 - 11장

탐색

의미는 '데이터를 찾는 방법' 여기서 얘기할 탐색은 선형 탐색, 이진 탐색 등이 아닌 이진 트리에 관련된 탐색이다.

 

효율적인 탐색을 위해서는 어떻게 찾을까만을 고민해서는 안되고,

그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 우선 고민해야한다.(자료구조)

 

이진 탐색 트리

이진트리의 구조를 보면 최대 자식 노드를 2개까지 가질 수 있는 구조로, 1024개의 데이터를 저장한다 할지라도,

트리의 높이는 10을 넘지 않고 레벨을 내려가면서 값의 비교를 통해 비교 연산을 레벨당 한 번씩 하면 될 테니깐.

물론 값의 비교를 위해 이진트리의 저장 규칙이 있어야 한다. 그것이 지금 배울 이진 탐색 트리.

 

이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는 데 사용 가능하다.

 

이진 탐색 트리가 되기 위한 조건.

 

1. 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다. (value는 아님)

2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

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

 

이해하기 쉽게 그림을 통해 확인해본다.

 

트리의 최상위 노드인 루트 노드 12를 기준으로 왼쪽 서브 트리의 모든 노드는 12보다 작고

오른쪽 서브트리의 노드들은 루트 노드보다 모두 크다.

 

또 서브 트리마다 규칙들이 적용해지는 모습도 알 수 있다.

 

여기서 10이라는 Key를 가진 노드를 이 이진 탐색 트리안에 집어넣는다고 가정해보자.

 

1. 12보다 작으니 왼쪽 서브 트리로 이동.

2. 8보다 크니 오른쪽 서브 트리로 이동.

3. 9보다 크니 오른쪽 서브 트리로 이동.

4. 그 밑에 아무것도 존재하지 않으므로 그 위치에 저장.

 

이진 탐색 트리의 구현은 앞서 구현한 이진트리를 조금 활용한다.

이진 탐색 트리의 구현 : 삽입과 탐색

이진 탐색 트리의 삽입 과정과 탐색과정은 앞서 설명했다.

Key(혹은 Key-Value쌍)가 담긴 노드가 이진 탐색 트리의 최상위 노드인 루트 노드부터 비교를 하면서 자기 자리를 찾아간다.

탐색도 똑같다.

루트 노드부터 시작하여 왼쪽 서브 트리로 내려갈지 오른쪽 서브 트리로 내려갈지 비교 연산을 통해 내려간다.

 

 

 

삽입과 탐색의 코드를 보기 전에 헤더 파일을 먼저 살펴보자.

#pragma once

//////////////////////////////////Node.h///////////////////////////////////////

#define NULL 0

template <typename T>
class BinarySearchTree;


template <typename T>
class Node
{
public:
	Node();
	Node(const T& data);
	~Node() = default;
	T GetData() const;
	Node<T>* GetLeftSubTreeOrNull();
	Node<T>* GetRightSubTreeOrNull();
	void MakeLeftSubTree(Node<T>* leftNode);
	void MakeRightSubTree(Node<T>* rightNode);
private:
	Node* m_left;
	Node* m_right;
	T     m_key;
};
template <typename T>
Node<T>::Node() : m_left(nullptr), m_right(nullptr), m_key(NULL)
{

}
template <typename T>
Node<T>::Node(const T& data) : m_left(nullptr), m_right(nullptr), m_key(data)
{

}
template <typename T>
T Node<T>::GetData() const
{
	return m_key;
}

template <typename T>
Node<T>* Node<T>::GetLeftSubTreeOrNull()
{
	if (this->m_left != nullptr)
		return this->m_left;
	else
		return nullptr;
}
template <typename T>
Node<T>* Node<T>::GetRightSubTreeOrNull()
{
	if (this->m_right != nullptr)
		return this->m_right;
	else
		return nullptr;
}
template <typename T>
void Node<T>::MakeLeftSubTree(Node<T>* leftNode)
{
	if (this->m_left == nullptr)
		this->m_left = leftNode;
	else
	{
		BinarySearchTree<T>::DeleteTree(this->m_left);
		this->m_left = leftNode;
	}
}
template <typename T>
void Node<T>::MakeRightSubTree(Node<T>* rightNode)
{
	if (this->m_right == nullptr)
		this->m_right = rightNode;
	else
	{
		BinarySearchTree<T>::DeleteTree(this->m_right);
		this->m_right = rightNode;
	}
}

그리고 이진 탐색 트리

#pragma once

//////////////////////////////BinarySearchTree////////////////////////////////
#include "Node.h"

template <typename T>
class BinarySearchTree
{
public:
	BinarySearchTree();
	~BinarySearchTree();

	void BSTInsert(const T& data); // 추가	
	Node<T>* BSTSearch(const T& target); // 추가
	static void DeleteTree(Node<T>* bt);
private:

private:
	Node<T>* m_root;
};

template <typename T>
BinarySearchTree<T>::BinarySearchTree() : m_root(nullptr)
{

}
template <typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
	DeleteTree(m_root);
}

template <typename T>
void BinarySearchTree<T>::DeleteTree(Node<T>* bt)
{
	if (bt == nullptr)
		return;

	DeleteTree(bt->GetLeftSubTreeOrNull());
	DeleteTree(bt->GetRightSubTreeOrNull());
	cout << bt->GetData() << "삭제!" << endl;
	delete bt;
}

 

전 포스팅의 이진트리는 소멸할 때 자동으로 노드를 제거해주지는 않았다. 

그걸 위해 노드와 이진 탐색 트리의 헤더를 별도로 분리.

 

돌아와서.

먼저 삽입의 코드를 살펴본다.

template <typename T>
void BinarySearchTree<T>::BSTInsert(const T& data)
{
	if (m_root == nullptr) // 첫 노드생성이라면.
	{
		m_root = new Node<T>(data);
		return;
	}
	Node<T>* pNode = nullptr; // 부모노드
	Node<T>* cNode = m_root; // 현재노드
	Node<T>* nNode = nullptr; // 새로 생성되는 노드.
	
	while (cNode != nullptr)
	{
		if (data == cNode->GetData()) // 키 중복허용 금지.
			return;

		pNode = cNode; // 찾을 위치 탐색.

		if (cNode->GetData() > data) // 루트노드보다(서브트리포함) 작다면 왼쪽.
			cNode = cNode->GetLeftSubTreeOrNull();
		else // 반대라면 오른쪽.
			cNode = cNode->GetRightSubTreeOrNull();
	}


	// pNode의 자식노드로 추가할 새 노드의 생성
	// pNode는 cNode가 들어갈 자리를 찾고 그 위치의 부모노드.
	nNode = new Node<T>(data);
	if (pNode != nullptr)
	{
		if (data < pNode->GetData())
			pNode->MakeLeftSubTree(nNode);
		else
			pNode->MakeRightSubTree(nNode);
	}

}

먼저 루트 노드가 없다면 생성해준다.

 

그 이후 pNode, cNode, nNode변수의 역할이 중요한데

 

우선 루트 노드부터 시작하여 키가 들어갈 위치를 찾는다.

그 과정에서 부모 노드의 위치를 저장하는데 그 이유는 부모 위치를 기준으로 왼쪽 혹은 오른쪽에 저장할 건지를 밑에서 찾기 위함.

 

while문은 말 그대로 자리 찾기. (키 중복금지 체크도 필수)

 

그런 다음 노드를 생성하고 현재 부모 노드(pNode)와 비교를 하여 왼쪽/오른쪽을 선택해 자리에 안착한다.

 

 

그다음은 탐색의 코드를 본다.

template <typename T>
Node<T>* BinarySearchTree<T>::BSTSearch(const T& target)
{
	if (m_root == nullptr)
		return nullptr;

	Node<T>* cNode = m_root;
	T cData;

	while (cNode != nullptr)
	{
		cData = cNode->GetData();
		if (cData == target)
			return cNode;
		else if (cData < target)
			cNode = cNode->GetRightSubTreeOrNull();
		else
			cNode = cNode->GetLeftSubTreeOrNull();
	}

	return nullptr;
}

간단하다. 

 

cNode변수에 루트 노드의 주소를 넘긴 후. 매번 현재 노드의 데이터를 저장하면서 탐색할 Key와 값을 비교한다.

(크면 오른쪽, 작으면 왼쪽으로 이동)

 

이진 탐색 트리의 삭제 구현

 

이진 탐색 트리에서 8이란 Key가 저장된 노드를 어떻게 삭제할까?

 

단순히 삭제만 한다고 끝나는 게 아니라, 저 노드가 삭제가 되어도 이진 탐색 트리가 유지가 되어야 한다.

즉 8이 없어진다면 저 왼쪽 서브 트리의 루트 노드는 9가 올라와야 한다.

 

물론 대상이 단말(리프) 노드라면 간단하겠지만 그게 아니라면 무엇으로 대신해야 할지 결정해야 한다는 것.

그렇기에 삭제에 대한 경우의 수를 살펴보자.

 

1. 삭제할 노드가 단말 노드인 경우

2. 삭제할 노드가 하나의 자식 노드를(+하나의 서브 트리) 갖는 경우

3. 삭제할 노드가 두 개의 자식 노드를(+두 개의 서브 트리) 갖는 경우

 

여기서 추가로 삭제 대상이 루트 노드인 경우와 그렇지 않은 경우를 나눠야 하기에 경우의 수는 최대 여섯 가지.

 

우선 상황 1의 경우를 보자.

위와 같은 경우는 단말 노드인 7을 삭제하는 것만으로도 이진 탐색 트리가 그대로 유지가 되기에 

대상의 노드를 지우고 바로 삭제의 과정이 완료된다.

 

그다음은 상황 2

 

 

위 그림에서는 9라는 Key가 저장된 노드를 삭제하려고 한다. 

 

위 그림의 트리에서 10이 저장된 노드가 왼쪽 자식 노드이건 오른쪽 자식 노드이건 상관없이

10이 저장된 노드는 8이 저장된 노드의 오른쪽 자식 노드가 되어야 한다.

 

그 이유는 9가 저장된 자리를 대신하기 위함.

여기서는

8 - 삭제 대상의 부모 노드를 가리키는 포인터 변수(pNode)

9- 현재 삭제할 드를 가리키는 포인터 변수(dNode)

10 - 삭제 대상의 자식 노드를 가리키는 포인터 변수가 필요하다.(dcNode)

 

마지막으로 상황 3

두 개의 자식 노드(서브 트리)를 갖고 있는 경우이며 앞선 상황보다는 조금 더 까다롭다.

 

우선 8을 삭제할 경우. 대신할 노드를 8의 왼쪽 서브 트리 중 가장 큰 값(7)으로 대체할지.

아니면 오른쪽 서브 트리의 가장 작은 값(8)으로 대체할지를 고민해봐야 한다.

 

대입해보면 알겠지만 둘 다 대체해봐도 이진 탐색 트리가 그대로 유지가 된다.

이렇듯 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값이나, 오른쪽 서브 트리에서 가장 작은 값을 저장한 노드로 대체하면 된다.

(참고로 이진 탐색 트리에서 가장 작은 값은 null을 만날 때까지 계속 왼쪽으로 이동. 가장 큰 값은 반대로)

 

어느 것으로 대체해도 상관없지만 그래도 좀 더 간단해 보이는 오른쪽 서브 트리의 가장 작은 값을 지니는 노드를 찾아서 삭제할 노드를 대체한다.

 

 

삭제가 되는 8이 저장된 노드를 9가 저장된 노드로 대체하고 9가 저장된 노드(빈자리)는 9가 저장된 노드의 자식 노드로 대체한다.

 

이를 위해 다음의 방법을 적용한다.

 

 

중요하게 봐야 할 것은 삭제 대상의 노드에 대체 노드의 Key를 '대입' 한다는 것이다.

 

왜냐하면 실제 코드레 벨에서 9라는 노드는 삭제 대상과 대체되면 저 빈자리는 실제로는 delete가 되어야 하기에.

실제 노드의 주소를 넘겨준다던가 할 필요는 없다.

 

다만 대체 노드의 자식노드(10)는 이야기가 다르다. 자식노드가 단말노드라면 괜찮겠지만 서브트리를 형성하는 자식노드의 경우에는 그 서브 트리까지 연결되어 있는 상태로 대체노드의 자식 노드로 다시 연결해주어야 하기에 주소를 넘겨 재연결을 해줘야 한다.

 

예로 들어 위 그림에서 4를 삭제한다고 보자.

이진 탐색 트리(왼쪽 서브 트리 4 노드의 왼쪽에 연결되어있다고 가정)에서 오른쪽 서브 트리의 가장 작은 값은 5.

 

5라는 Key값은 4의 노드에 대입. 그리고 8의 왼쪽 자식 노드에 6을 다시 재연결 해준다.

(대체 노드가 왼쪽 자식 노드인 경우)

 

다음의 예를 보자.

 

대체 노드가 오른쪽 자식 노드인 경우. 9를 4에 대입하고 10을 다시 재연결 하면 끝.

 

왜 두 가지 예를 들었냐면, 대체 노드가 왼쪽 자식 노드인지, 오른쪽 자식 노드인지에 대한 구분(if)이 필요하다.

 

그리고 두 가지 예를 보았을 때 항상 대체 노드의 자식 노드는 오른쪽 서브 트리를 연결한다는 것을 알아야 한다.

(삭제 노드의 오른쪽 서브 트리를 대상으로 가장 작은 값을 찾으므로, 가장 작은 값을 찾았다는 것은 그 노드의 왼쪽 자식은 더 이상 존재하지 않으므로.)

 

이제 삭제의 코드를 확인해본다.

 

#pragma once
#define NULL 0

template <typename T>
class BinarySearchTree;

template <typename T>
class Node
{
public:

	Node<T>* RemoveLeftSubTreeNoDelete(); // 추가
	Node<T>* RemoveRightSubTreeNoDelete(); // 추가
	void ChangeLeftSubTree(Node<T>* sub); // 추가
	void ChangeRightSubTree(Node<T>* sub); // 추가

private:
	Node<T>* m_left;
	Node<T>* m_right;
	T     m_key;
};


// 메모리의 해제는 함수를 호출한쪽에게 맡김.
template <typename T>
Node<T>* Node<T>::RemoveLeftSubTreeNoDelete()
{
	// 왼쪽 자식 노드를 제거. 제거된 노드의 주소값을 반환.
	Node<T>* delNode;

	if (this != nullptr)
	{
		delNode = this->m_left;
		this->m_left = nullptr;
	}
	else
		return nullptr;

	return delNode;
}

template <typename T>
Node<T>* Node<T>::RemoveRightSubTreeNoDelete()
{
	// 오른쪽 자식 노드를 제거. 제거된 노드의 주소값을 반환.

	Node<T>* delNode;

	if (this != nullptr)
	{
		delNode = this->m_right;
		this->m_right = nullptr;
	}
	else
		return nullptr;

	return delNode;
}

template <typename T>
void Node<T>::ChangeLeftSubTree(Node<T>* sub)
{
	// main의 왼쪽 자식 노드를 변경한다.
	this->m_left = sub;
}

template <typename T>
void Node<T>::ChangeRightSubTree(Node<T>* sub)
{
	// main의 오른쪽 자식 노드를 변경한다.
	this->m_right = sub;
}

(추가한 부분 이외의 것은 코드에서 제거하였습니다.)

 

그리고 이진 탐색 트리의 코드.

#pragma once
#include "Node.h"

template <typename T>
class BinarySearchTree
{
public:
	void BSTPrintAllData(Node<T>* bt) const; // 추가
	T BSTGetNodeData() const; // 추가
	Node<T>* BSTSearch(const T& target); 
	Node<T>* BSTRemove(const T& target); // 추가
	Node<T>* GetRoot() const; // 추가
private:

private:
	Node<T>* m_root;
	Node<T>* m_currentPos;
	int		 m_size;
};

template <typename T>
Node<T>* BinarySearchTree<T>::GetRoot() const
{
	return m_root;
}

template <typename T>
void BinarySearchTree<T>::BSTPrintAllData(Node<T>* bt) const // 전위순회(루트노드를 중간에 방문)
{
	if (bt == nullptr)
		return;

	BSTPrintAllData(bt->GetLeftSubTreeOrNull());
	cout << bt->GetData() << " ";
	BSTPrintAllData(bt->GetRightSubTreeOrNull());
}

template <typename T>
Node<T>* BinarySearchTree<T>::BSTRemove(const T& target)
{
	Node<T>* pVRoot = new Node<T>(); // 가상 루트노드 -> 루트노드를 없앨시 필요한 노드
	Node<T>* pNode = pVRoot;
	Node<T>* cNode = m_root;
	Node<T>* dNode = nullptr; // 삭제노드.
	 

	//가상 루트 노드의 오른쪽 자식노드로 루트 노드를 가리킴. 
	pVRoot->ChangeRightSubTree(m_root);


	// 삭제대상 탐색.
	while (cNode != nullptr && cNode->GetData() != target)
	{
		pNode = cNode;

		if (target < cNode->GetData())
			cNode = cNode->GetLeftSubTreeOrNull();
		else
			cNode = cNode->GetRightSubTreeOrNull();
	}

	if (cNode == nullptr) // 삭제할 대상을 못찾았다.
		return nullptr;

	dNode = cNode; // 삭제 대상을 dNode에 대입.

	// 상황 1. 삭제 노드가 단말 노드인경우
	if (dNode->GetLeftSubTreeOrNull() == nullptr && dNode->GetRightSubTreeOrNull() == nullptr)
	{
		if (pNode->GetLeftSubTreeOrNull() == dNode) // 삭제대상이 부모노드의 왼쪽 단말 노드다.
		{
			pNode->RemoveLeftSubTreeNoDelete();
		}
		else // 삭제대상이 부모노드의 오른쪽 단말 노드다.
		{
			pNode->RemoveRightSubTreeNoDelete();
		}

	}

	// 상황 2. 삭제 노드가 왼쪽 혹은 오른쪽에 하나의 자식노드(서브트리)를 가지는 경우.
	else if (dNode->GetLeftSubTreeOrNull() == nullptr || dNode->GetRightSubTreeOrNull() == nullptr)
	{
		Node<T>* dcNode; // 삭제 대상의 자식 노드를 가리킴.

		// 삭제대상의 자식노드 하나가 왼쪽자식인지 오른쪽자식인지.
		if (dNode->GetLeftSubTreeOrNull() != nullptr)
		{
			dcNode = dNode->GetLeftSubTreeOrNull();
		}
		else
		{
			dcNode = dNode->GetRightSubTreeOrNull();
		}

		// 삭제대상은 부모노드의 왼쪽 자식인지 오른쪽 자식인지.
		if (pNode->GetLeftSubTreeOrNull() == dNode)
		{
			pNode->ChangeLeftSubTree(dcNode);
		}
		else
		{
			pNode->ChangeRightSubTree(dcNode);
		}
	}

	// 상황 3. 삭제노드의 자식 노드(서브트리)가 두 개 인경우.
	else
	{
		Node<T>* mNode = dNode->GetRightSubTreeOrNull(); // 대체노드.
		Node<T>* mpNode = dNode; // 대체노드의 부모.
		T copyData;

		// 삭제노드의 오른쪽 서브트리에서 가장 작은 값 탐색.
		while (mNode->GetLeftSubTreeOrNull() != nullptr)
		{
			mpNode = mNode;
			mNode = mNode->GetLeftSubTreeOrNull();
		}

		// 대체노드의 Key값을 삭제노드에 대입.
		copyData = dNode->GetData(); // 백업.
		dNode->SetData(mNode->GetData()); // 대체노드의 값 대입.

		// 대체 노드의 부모 노드와 자식 노드를 연결한다.
		if (mpNode->GetLeftSubTreeOrNull() == mNode) // 대체노드가 왼쪽 자식 노드인 경우.
		{
			mpNode->ChangeLeftSubTree(mNode->GetRightSubTreeOrNull());
		}
		else // 대체노드가 오른쪽 자식 노드인 경우.
		{
			mpNode->ChangeRightSubTree(mNode->GetRightSubTreeOrNull());
		}
		dNode = mNode; // 삭제할 노드는 대체노드.
		dNode->SetData(copyData); // 반환했을 때 그 값을 알기 위해. 원본 데이터(실제 삭제노드는 대입된 상태이기 때문)대입.
	}

	// 삭제된 노드가 루트 노드인 경우. 루트노드가 삭제되는 경우는 단말노드,자식노드가 하나일경우.
	if (pVRoot->GetRightSubTreeOrNull() != m_root)
		m_root = pVRoot->GetRightSubTreeOrNull();

	delete pVRoot;
	return dNode; // 삭제대상의 반환

}

(추가한 부분 이외의 것은 코드에서 제거하였습니다.)

상황 1과 상황 2는 어렵지 않다.

 

상황 3에서 

4의 왼쪽에는 자식노드(서브트리)가 존재한다고 가정.

이 그림의 4라는 Key값을 지닌 노드를 없앤다고 하면 삭제 노드의 오른쪽 서브 트리에서 가장 작은 값을 탐색한다.

 

처음에는 mNode는 9. mpNode는 4. while문을 통해 mNode가 왼쪽으로 계속 내려가면서 nullptr을 만날 때까지 탐색.

 

가장 작은 값 5를 만나 mNode는 5를 저장한 노드의 주소를,

mpNode는 8을 저장한 노드의 주소(mNode의 부모)를 저장.

 

이제 4가 저장된 노드의 주소(dNode)에 대체 노드(mNode)의 Key값을 대입.

그리고 대체 노드는 없어져야 하므로 mNode가 mpNode의 왼쪽 자식인지 오른쪽 자식인지 체크 후

왼쪽 자식이므로 mNode의 오른쪽 자식 노드(mNode->GetRight)를 mpNode의 왼쪽 자식 노드를 가리키는 포인터 변수에 저장한다.

 

그리고 dNode(4를 저장한 노드)는 대체 노드의 Key값을 받았으므로 지울 필요가 없고 dNode에 mNode를 대입한다.

(mNode(대체 노드)의 삭제를 위해)

그리고 위에서 백업해둔 4라는 Key값을 dNode에 저장해주고(개념상으로는 삭제해야 할 노드는 4이므로) 그 주소를 반환한다.

 

 

여기까지가 이진 탐색 트리의 삽입/삭제/탐색의 과정. 하지만 아직 이 이진 탐색 트리는 문제점이 하나 존재한다.

그 문제점은 다음 장에 이어서..