이진 탐색 트리(Binary Search Tree) - c++

 

▶️이진탐색트리 

• 자식 노드의 수가 2개까지 추가가 가능한 트리입니다.

 

• 자식의 추가가 순서대로 입력되는 트리와 다르게
  • 부모보다 작으면 왼쪽, 부모보다 크면 오른쪽으로 추가되며 '정렬' 됩니다. 

• 10, 5, 15, 7, 3, 1순서로 추가한 이진 탐색트리 예시 입니다.
  • 숫자의 크기에 따라 좌, 우 정렬이 된것을 확인하실 수 있습니다. 

 

• 위 예시에서 3을 검색시 값을 확인하여 비교할 수가 절반씩 줄어 듭니다
  • 검색속도가 매우 빠릅니다. 

 

 

 

▶️ 편향트리 

• 기본적인 방식으로 정렬시 특정 상황에서 한쪽으로 치우친 트리가 만들어지는데, 이것을 편향트리라고 합니다.
• 기본 이진탐색트리의 단점중 하나입니다.

이진 탐색트리의 입력 순서대로 1,2,3,4,5를 입력한 상태입니다. 

기본적인 입력순서대로 입력시 한쪽으로 치우쳐서 '편향트리'가 되었음을 알 수 있습니다. 

 

 

 

▶️ 완전 이진 트리

위와 같이 균형을 이루고 있는 형태의 트리를 완전 이진트리라고 합니다. 

 

 

▶️ 포화 이진트리

리프노드전까지 모든 트리가 자식을 모두 2개씩 가진 트리를 포화이진트리라고 합니다. 

 

 

▶️자가 균형 이진 탐색 트리

편향트리를 막아주는 자가균형이진트리 (AVL이진트리, red-black 이진트리)를 사용하여 방지가 가능합니다. 

데이터가 들어오면 완전 이진트리의 형태를 유지시켜 줍니다. 

 

 

▶️이진 탐색 트리의 구현 예시

BinarySearchTree.h

// BinarySearchTree.h

#pragma once
#include <iostream>

template <typename Key, typename Value>
class CBiniarySearchTreeNode
{
	template <typename Key, typename Value>
	friend class CBinarySearchTree;

	template <typename Key, typename Value>
	friend class CBiniarySearchTreeIterator;

private:
	CBiniarySearchTreeNode () {}
	~CBiniarySearchTreeNode () {}

// data만 open
public :
	Key mKey;
	Value mData;

private :
	CBiniarySearchTreeNode<Key, Value>* mParent	= nullptr;
	CBiniarySearchTreeNode<Key, Value>* mLeft	= nullptr;
	CBiniarySearchTreeNode<Key, Value>* mRight	= nullptr;
	CBiniarySearchTreeNode<Key, Value>* mNext	= nullptr;
	CBiniarySearchTreeNode<Key, Value>* mPrev	= nullptr;
};

// next와 prev가 없으면 iterator 쓰기 힘들어짐.
// stl에서도 동일한 방식으로 구현되어있음.
template <typename Key, typename Value>
class CBiniarySearchTreeIterator
{
	template <typename Key, typename Value>
	friend class CBinarySearchTree;

	typedef CBiniarySearchTreeIterator<Key, Value> iterator;

public : 
	CBiniarySearchTreeIterator () {}
	~CBiniarySearchTreeIterator () {}

private :
	CBiniarySearchTreeNode<Key, Value>* mNode = nullptr;

public :
	bool operator == ( const CBiniarySearchTreeIterator<Key, Value>& iter )
	{
		return mNode == iter.mNode;
	}

	bool operator != ( const CBiniarySearchTreeIterator<Key, Value>& iter )
	{
		return mNode != iter.mNode;
	}

	const CBiniarySearchTreeIterator<Key, Value>& operator ++ ()
	{
		mNode = mNode->mNext;
		return *this;
	}

	const CBiniarySearchTreeIterator<Key, Value>& operator ++ (int)
	{
		mNode = mNode->mNext;
		return *this;
	}

	const CBiniarySearchTreeIterator<Key, Value>& operator -- ()
	{
		mNode = mNode->mPrev;
		return *this;
	}

	const CBiniarySearchTreeIterator<Key, Value>& operator -- ( int )
	{
		mNode = mNode->mPrev;
		return *this;
	}

	// 키나 값을 변경할 경우 정렬이 깨지기 때문에 const 추가
	// iter-> 하면 node에 접근. key와 value에 접근가능 (key와 value는 public)
	const CBiniarySearchTreeNode<Key, Value>* operator -> () const
	{
		return mNode;
	}
};

template <typename Key, typename Value>
class CBinarySearchTree
{
public :
	CBinarySearchTree () 
	{
		mBegin = new NODE;
		mEnd = new NODE;

		mBegin->mNext = mEnd;
		mEnd->mPrev = mBegin;
	}
	~CBinarySearchTree () 
	{
		clear ();
		delete mBegin;
		delete mEnd;
	}

private :
	typedef CBiniarySearchTreeNode<Key, Value> NODE;

public :
	typedef CBiniarySearchTreeIterator<Key, Value> iterator;

private:
	NODE*	mRoot	= nullptr;
	NODE*	mBegin	;
	NODE*	mEnd	;
	int		mSize	= 0;

public :
	void insert ( const Key& key, const Value& data )
	{
		if (!mRoot)
		{
			mRoot = new NODE;
			mRoot->mKey = key;
			mRoot->mData = data;

			mBegin->mNext = mRoot;
			mRoot->mPrev = mBegin;

			mRoot->mNext = mEnd;
			mEnd->mPrev = mRoot;
		}

		else
			insert ( key, data, mRoot );

		++mSize;
	}

	bool empty () const { return mSize == 0; }

	int size () const { return mSize; }	

	void clear ()
	{
		NODE * node = mBegin->mNext;

		while (node != mEnd)
		{
			NODE* next = node->mNext;
			delete node;
			node = next;
		}

		mBegin->mNext = mEnd;
		mEnd->mPrev = mBegin;

		mSize = 0;
	}

	iterator begin ()	const
	{
		iterator	iter;
		iter.mNode = mBegin->mNext;
		return iter;
	}

	iterator end ()	const
	{
		iterator	iter;
		iter.mNode = mEnd;
		return iter;
	}

	iterator find ( const Key& key ) const
	{
		return find ( key, mRoot );
	}

	iterator erase ( const Key& key )
	{
		iterator iter = find ( key );

		return erase ( iter );
	}

	iterator erase ( iterator& iter ) 
	{
		if (iter.mNode == mEnd)
			return iter;

		NODE* deleteNode = nullptr;
		NODE* resultNode = nullptr;

		// 지올 노드가 리프노드일 경우 
		if (!iter.mNode->mLeft && !iter.mNode->mRight)
		{
			// 지울 노드가 부모노드의 왼쪽인지, 오른쪽인지 판단하여 링크제거
			// 부모 노드 있는지 판단
			NODE* parent = iter.mNode->mParent;

			// 부모존재. 일반적인 리프노드
			if (parent)
			{
				if (iter.mNode == parent->mLeft)
					parent->mLeft = nullptr;

				else
					parent->mRight = nullptr;
			}
			// 부모없음. 루트노드
			else
				mRoot = nullptr;

			deleteNode = iter.mNode;
			resultNode = deleteNode->mNext;
		}
		else
		{
			NODE* childNode = nullptr;

			// 왼쪽, 오른쪽 하나라도 있거나 둘다 있거나 한 상태. 그냥 왼쪽에서 찾아오겠음 (편의상)
			if (iter.mNode->mLeft)
			{
				// 왼쪽 노드가 있을 경우 왼쪽 노드에서 
				// 가장 큰 노드를 찾아서 삭제할 노드로 사용한다.
				deleteNode = FindMax ( iter.mNode->mLeft );
				// 왼쪽 자식있을 가능성이 있음.
				childNode = deleteNode->mLeft;
				resultNode = iter.mNode->mNext;
			}
			else
			{
				// 오른쪽 노드가 있을 경우 오른쪽 노드에서 
				// 가장 작은 노드를 찾아서 삭제할 노드로 사용한다.
				deleteNode = FindMin ( iter.mNode->mRight );
				// 오른쪽 자식있을 가능성이 있음.
				childNode = deleteNode->mRight;
				resultNode = iter.mNode;
			}

			// 위에서 찾아준 노드의 값으로 iterator가 가지고 있는 노드의 값을 대체한다. 
			iter.mNode->mKey = deleteNode->mKey;
			iter.mNode->mData = deleteNode->mData;

			// 1. 부모로부터 어느방향에 붙어있는지 확인
			// 2. 자식이 붙어있는지 확인 

			NODE* parent = deleteNode->mParent;

			if (parent)
			{
				if (deleteNode == parent->mLeft)
					parent->mLeft = childNode;

				else
					parent->mRight = childNode;
			}

			if (childNode)
				childNode->mParent = parent;
		}

		NODE* prev = deleteNode->mPrev;
		NODE* next = deleteNode->mNext;

		prev->mNext = next;
		next->mPrev = prev;

		delete deleteNode;

		--mSize;

		iterator result ;
		result.mNode = resultNode;
		return result;
	}

	// 이진트리 순회엔 전위, 중위, 후위 순회 3가지가 있다.
	// 전위 : 루트 -> 왼쪽 -> 오른쪽
	void PreOrder ()
	{
		PreOrder ( mRoot );
	}

	// 중위 : 왼쪽 -> 루트 -> 오른쪽
	void InOrder ()
	{
		InOrder ( mRoot );
	}

	// 후위 : 왼쪽 -> 오른쪽 -> 루트
	void PostOrder ()
	{
		PostOrder ( mRoot );
	}

private :
	void insert ( const Key& key, const Value& data, NODE * node )
	{
		if (!node)
			return ;

		// 인자로 들어온 키와 노드의 키를 비교하여 
		// 왼쪽인지 오른쪽인지 판단한다.
		// class를 이용하여 key를 사용할 경우 operator 를 이용해 재정의해줘야한다.
		if (key < node->mKey)
		{
			// 왼쪽에 추가해야 하는데 왼쪽 노드가 없을 경우
			if (!node->mLeft)
			{
				NODE* newNode = new NODE;

				newNode->mKey = key;
				newNode->mData = data;
				
				// 부모노드의 왼쪽으로 추가한다.
				node->mLeft = newNode;

				// 새로 생성한 노드의 부모로 추가한다.
				newNode->mParent = node;

				//왼쪽에 추가될 때는 부모 노드와 부모노드의 이전 노드 사이에 추가.
				NODE* prev = node->mPrev;

				prev->mNext = newNode; // <========== 여기 확인하기 
				newNode->mPrev = prev;

				newNode->mNext = node;
				node->mPrev = newNode;
			}
			// 왼쪽에 추가해야 하는데 왼쪽 노드가 있을 경우
			else
				insert ( key, data, node->mLeft )	;
		}
		// key가 크거나 같을 경우
		else
		{
			// 오른쪽에 추가해야 할 경우
			if (!node->mRight)
			{
				NODE* newNode = new NODE;

				newNode->mKey = key;
				newNode->mData = data;

				// 부모노드의 오른쪽으로 추가한다.
				node->mRight = newNode;

				// 새로 생성한 노드의 부모로 추가한다.
				newNode->mParent = node;

				//오른쪽에 추가될 때는 부모 노드와 부모노드의 이전 노드 사이에 추가.
				NODE* next = node->mNext;

				node->mNext = newNode;
				newNode->mPrev = node;

				newNode->mNext = next;
				next->mPrev = newNode;
			}
			else
				insert ( key, data, node->mRight );
		}
	}

	iterator find ( const Key& key, NODE* node ) const
	{
		if (!node)
			return end ();

		if (key == node->mKey)
		{
			iterator iter;
			iter.mNode = node;
			return iter;
		}

		else if (key < node->mKey)
			return find ( key, node->mLeft );

		return find ( key, node->mRight );
	}

	// 제일 작은거 찾아서 반환
	NODE* FindMin ( NODE* node )
	{
		//---- [ while 사용 ] ----
		while (node -> mLeft)
		{
			node = node->mLeft;
		}

		return node;


		// -----[ 재귀 사용 ] -----
	//	// 해당 노드가 제일 작음
	//	if (!node->mLeft)
	//		return node;

	//	// 더 작은 자식노드가 있음
	//	return FindMin ( node->mLeft );
	}

	NODE* FindMax ( NODE * node )
	{
		//---- [ while 사용 ] ----
		while (node->mRight)
		{
			node = node->mRight;
		}

		return node;

		// -----[ 재귀 사용 ] -----
		//if (!node->mRight)
		//	return node;

		//return FindMax ( node->mRight );
	}

	void PreOrder ( NODE* node )
	{
		if (!node)
			return;

		std::cout << "Key : " << node->mKey << ", Value : " << node->mData << std::endl;

		PreOrder ( node->mLeft );
		PreOrder ( node->mRight );
	}

	void InOrder ( NODE* node )
	{
		if (!node)
			return;

		InOrder ( node->mLeft );
		std::cout << "Key : " << node->mKey << ", Value : " << node->mData << std::endl;
		InOrder ( node->mRight );
	}

	void PostOrder ( NODE* node )
	{
		if (!node)
			return;

		PostOrder ( node->mLeft );
		PostOrder ( node->mRight );
		std::cout << "Key : " << node->mKey << ", Value : " << node->mData << std::endl;
	}
};

 

main.cpp

#include <iostream>
#include "BinarySearchTree.h"

int main ()
{
	CBinarySearchTree<std::string, int> intMap;

	intMap.insert ( "R", 100 );
	intMap.insert ( "F", 200 );
	intMap.insert ( "V", 300 );
	intMap.insert ( "D", 400 );
	intMap.insert ( "T", 500 );

	CBinarySearchTree<std::string, int>::iterator	iter;
	CBinarySearchTree<std::string, int>::iterator	iterEnd = intMap.end ();

	for (iter = intMap.begin (); iter != iterEnd; ++iter)
	{
		std::cout << "Key : " << iter->mKey << " Value : " <<
			iter->mData << std::endl;
	}

	iter = intMap.find ( "T" );

	if (iter != intMap.end ())
	{
		std::cout << "Find Key : " << iter->mKey << " Value : " <<
			iter->mData << std::endl;
	}

	else
		std::cout << "키가 없습니다." << std::endl;

	return 0;
}

 

▶️ 코드에서 포인트

 

✅자식 노드가 추가될 때 부모 노드보다 작아서 왼쪽 자식에 추가될 경우 

부모의 이전노드와 부모노드 사이에 추가됩니다 

1. 10이 있을 때 5가 추가된다면 트리상에선 10의 왼쪽자식에 추가되고
2. 5는 부모(10)의 이전노드인 Begin과 부모 10 사이에 추가되어
3. Begin -> 5 -> 10 -> End 순으로 정렬됩니다.

 

 

✅자식 노드가 추가될 때 부모 노드보다 커서 오른쪽 자식에 추가될 경우 

부모와 부모 다음노드 사이에 추가됩니다 

1. 10과 5가 있는 트리에서 15가 추가될 경우, 15는 트리상에서 10의 오른쪽에 추가됩니다.
2. 15는 부모보다 크기 때문에 부모(10)와 부모 다음노드(End) 사이에 추가됩니다.
3. Begin -> 5 -> 10 -> 15 -> End 순으로 정렬됩니다.