Binary Tree

개요

지금까지 배웠던 Linked lisk, Array, Stack, Queue는 다 선형적인 자료구조이다.

이번에 다룰 트리는 대표적인 비선형적인 자료구조

• 트리의 특징

  	- 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재
  	- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 
  	- 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다. 
  	- 트리에서 임의의 2 노드를 이어주는 경로는 유일하다. 

• 트리의 종류

  	- 이진트리 : child의 개수가 최대 2개
  	- 쿼드트리  : child의 개수가 최대 4개
  	- 옥트리 : child의 개수가 최대 8개

Unreal Engine에서는 트리가 어떻게 사용될까?

1. 평면을 쪼갤때 쿼드트리가 많이 사용된다. 처음 root의 노드는 쪼개기 전의 원본 사각형이다. 3차원 공간을 분할할때 옥트리를 사용한다.
2. Skeletal Mesh에도 Tree 구조 사용.

구현할 Binary Tree

이번 예제에서는 Iter를 사용하기 위해 Double linked List의 개념까지 넣어서 구현할 것이다. 실재로 STL의 map이 이렇게 구성되어 있다고 한다. 더 정확하게는 Red Black Tree로 만들어졌다고 하는데 이 내용은 추후에 다루어보자.

또한 우리가 앞서 다루었던 linked list, array, stack, queue처럼 template class이들이지만 Key와 Value를 담기 위해서 2개의 typename을 받는다.

BST의 insert/delete

BST(Binary Search Tree)란 Binary Tree에서 원소 탐색시간을 logN으로 늘리기 위해서 부모 노드와 자식 노드간의 대소 관계에서 규칙을 만든 자료구조이다. 부모 노드를 기준으로 작은 원소는 왼쪽, 큰 원소는 오른쪽에 있어야 한다.

이번 section은 BT이지만, 삽입과 삭제에 대해 BST의 기능을 구현해 본다. Insert는 생각보다 구현이 쉽지만, delete의 난이도가 높다. 일차적으로 생각을 해보면, leaf node들은 쉽게 지울 수 있지만, 자식이 있는 노드들을 지우려고 하면 경우의 수를 나누어서 생각해 보아야 한다.

Child node가 없을때, 1개일때, 2개일때로 경우의 수를 나누어 보자. Child node가 없으면 leaf node라는 말이고, 이는 그냥 지워주면 된다. Child node가 1개이면 이 또한 지우고 Child node와 지운 노드의 부모 노드를 그냥 연결해주면 된다.

Child node가 2개일때가 문제인데, 이때는 둘 중 하나를 실행하면 된다. 왼쪽 subtree에서 가장 큰수 혹은 오른쪽 subtree에서 가장 작은 수를 찾아서 일단 그 노드와 자리를 바꿔치기 한다.

#pragma once

// KEY : 탐색을 위한 값
// VALUE : 실제 저장되는 값
// Key, Value의 값을 저장하기 위해 2개의 인자를 받는다.
template <typename KEY, typename VALUE>
class CBinaryTreeNode
{
	template <typename KEY, typename VALUE>
	friend class CBinaryTree;

	template <typename KEY, typename VALUE>
	friend class CBinaryTreeIterator;

private:
	CBinaryTreeNode()
	{
	}

	~CBinaryTreeNode()
	{
	}

public:
	KEY		mKey;
	VALUE	mValue;

private:
	// Tree Node의 위, 아래 노드 포인터 값 저장
	CBinaryTreeNode<KEY, VALUE>* mLeft = nullptr;
	CBinaryTreeNode<KEY, VALUE>* mRight = nullptr;
	CBinaryTreeNode<KEY, VALUE>* mParent = nullptr;
    
    // Node들의 정보를 LinkedList에도 저장하여야 함으로 LinkedList의 앞, 뒤 노드 포인터 저장.
	CBinaryTreeNode<KEY, VALUE>* mPrev = nullptr;
	CBinaryTreeNode<KEY, VALUE>* mNext = nullptr;
};

 
template <typename KEY, typename VALUE>
class CBinaryTreeIterator
{
	template <typename KEY, typename VALUE>
	friend class CBinaryTree;

public:
	CBinaryTreeIterator()
	{
	}

	~CBinaryTreeIterator()
	{
	}

private:
	CBinaryTreeNode<KEY, VALUE>* mNode = nullptr;

public:
	bool operator == (const CBinaryTreeIterator<KEY, VALUE>& iter)	const
	{
		return mNode == iter.mNode;
	}

	bool operator != (const CBinaryTreeIterator<KEY, VALUE>& iter)	const
	{
		return mNode != iter.mNode;
	}

	void operator ++ ()
	{
		mNode = mNode->mNext;
	}

	void operator ++ (int)
	{
		mNode = mNode->mNext;
	}

	void operator -- ()
	{
		mNode = mNode->mPrev;
	}

	void operator -- (int)
	{
		mNode = mNode->mPrev;
	}

	// iter->를 하게 되면 mNode-> 를 한것과 같다.
    // Q. Tree에서는 list 역참조 operator overloading과 다른 점은 key와 value 2개를 return해야 하는 문제가 있다. 
// 이의 해결 방법으로는 -> operator를 overloading하여 Node 자체를 반환하는 방법이 있을 수 있다. 

	CBinaryTreeNode<KEY, VALUE>* operator -> ()
	{
		return mNode;
	}
};

template <typename KEY, typename VALUE>
class CBinaryTree
{
public:
	CBinaryTree()
	{
		mBegin = new Node;
		mEnd = new Node;

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

	~CBinaryTree()
	{
		Node* DeleteNode = mBegin;

		while (DeleteNode != nullptr)
		{
			Node* Next = DeleteNode->mNext;
			delete DeleteNode;
			DeleteNode = Next;
		}
	}

private:
	typedef CBinaryTreeNode<KEY, VALUE>	Node;

public:
	typedef CBinaryTreeIterator<KEY, VALUE>	iterator;

private:
	Node* mRoot = nullptr;
    // Linked List에서 순회를 편하기 하기 위해 mBegin, mEnd를 설정한다.   
	Node* mBegin;
	Node* mEnd;
	int	mSize = 0;

public:
	void Insert(const KEY& Key, const VALUE& Value)
	{
		if (!mRoot)
		{
			mRoot = new Node;
			mRoot->mKey = Key;
			mRoot->mValue = Value;

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

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

			++mSize;
		}

		else
		{
			Insert(Key, Value, mRoot);
		}
	}

	// Insert 함수를 반복문으로 구현
	void InsertWhile(const KEY& Key, const VALUE& Value)
	{
		if (!mRoot)
		{
			mRoot = new Node;
			mRoot->mKey = Key;
			mRoot->mValue = Value;

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

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

			++mSize;
		}

		else
		{
			Node* CurrentNode = mRoot;

			while (CurrentNode != nullptr)
			{
				if (Key <= CurrentNode->mKey)
				{
					if (!CurrentNode->mLeft)
					{
						Node* NewNode = new Node;
						NewNode->mKey = Key;
						NewNode->mValue = Value;

						// 현재 노드의 왼쪽 자식노드로 붙여준다.
						CurrentNode->mLeft = NewNode;
						NewNode->mParent = CurrentNode;

						// CurrentNode와 CurrentNode의 이전노드 사이에
						// 새로 생성한 노드를 붙여준다.
						Node* Prev = CurrentNode->mPrev;

						Prev->mNext = NewNode;
						NewNode->mPrev = Prev;

						NewNode->mNext = CurrentNode;
						CurrentNode->mPrev = NewNode;

						++mSize;

						break;
					}

					else
					{
						CurrentNode = CurrentNode->mLeft;
					}
				}

				else
				{
					if (!CurrentNode->mRight)
					{
						Node* NewNode = new Node;
						NewNode->mKey = Key;
						NewNode->mValue = Value;

						// 현재 노드의 오른쪽 자식노드로 붙여준다.
						CurrentNode->mRight = NewNode;
						NewNode->mParent = CurrentNode;

						// CurrentNode와 CurrentNode의 다음노드 사이에
						// 새로 생성한 노드를 붙여준다.
						Node* Next = CurrentNode->mNext;

						CurrentNode->mNext = NewNode;
						NewNode->mPrev = CurrentNode;

						NewNode->mNext = Next;
						Next->mPrev = NewNode;

						++mSize;

						break;
					}

					else
					{
						CurrentNode = CurrentNode->mRight;
					}
				}
			}
		}
	}
    // Insert를 반복적, 재귀적으로 각각 구현해보기
    // 먼저 붙일 노드를 생성하고 그 노드를 트리에 insert->그 노드를 다시 linkedlist에 insert하는 과정을 거친다. 
    // Linked list에 넣을때에는 단순히 붙여지는 순서로 뒤에다가 붙이는 것이 아닌 Tree에서 붙여지는 parent node와의 대소를 비교해서 linkedlist에 삽입한다. 
    
    // Insert 함수를 재귀적으로 구현
    void Insert(const KEY& Key, const VALUE& Value, Node* CurrentNode)
	{
		if (!CurrentNode)
			return;

		// 왼쪽
		if (Key <= CurrentNode->mKey)
		{
			// 왼쪽에 노드가 없을 경우 왼쪽 노드로 붙여준다.
			if (!CurrentNode->mLeft)
			{
				Node* NewNode = new Node;
				NewNode->mKey = Key;
				NewNode->mValue = Value;

				// 현재 노드의 왼쪽 자식노드로 붙여준다.
				CurrentNode->mLeft = NewNode;
				NewNode->mParent = CurrentNode;

				// CurrentNode와 CurrentNode의 이전노드 사이에
				// 새로 생성한 노드를 붙여준다.
				Node* Prev = CurrentNode->mPrev;

				Prev->mNext = NewNode;
				NewNode->mPrev = Prev;

				NewNode->mNext = CurrentNode;
				CurrentNode->mPrev = NewNode;

				++mSize;

				return;
			}

			// 왼쪽에 노드가 있을 경우 왼쪽노드를 CurrentNode로 넣어주면서
			// 검사를 다시 시작한다.
			else
			{
				Insert(Key, Value, CurrentNode->mLeft);
			}
		}

		// 오른쪽
		else
		{
			// 오른쪽에 노드가 없을 경우 오른쪽 노드로 붙여준다.
			if (!CurrentNode->mRight)
			{
				Node* NewNode = new Node;
				NewNode->mKey = Key;
				NewNode->mValue = Value;

				// 현재 노드의 오른쪽 자식노드로 붙여준다.
				CurrentNode->mRight = NewNode;
				NewNode->mParent = CurrentNode;

				// CurrentNode와 CurrentNode의 다음노드 사이에
				// 새로 생성한 노드를 붙여준다.
				Node* Next = CurrentNode->mNext;

				CurrentNode->mNext = NewNode;
				NewNode->mPrev = CurrentNode;

				NewNode->mNext = Next;
				Next->mPrev = NewNode;

				++mSize;

				return;
			}

			// 오른쪽에 노드가 있을 경우 오른쪽노드를 
			// CurrentNode로 넣어주면서
			// 검사를 다시 시작한다.
			else
			{
				Insert(Key, Value, CurrentNode->mRight);
			}
		}
	}

	int Size()	const
	{
		return mSize;
	}

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

	void Clear()
	{
		Node* DeleteNode = mBegin->mNext;

		while (DeleteNode != mEnd)
		{
			Node* Next = DeleteNode->mNext;
			delete DeleteNode;
			DeleteNode = Next;
		}

		mBegin->mNext = mEnd;
		mEnd->mPrev = mBegin;
		mSize = 0;
	}

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

	iterator& End()	const
	{
		static iterator	iter;
		iter.mNode = mEnd;
		return iter;
	}

	iterator Find(const KEY& Key)	const
	{
		if (mSize == 0)
			return End();

		return Find(Key, mRoot);
	}

	iterator erase(const KEY& Key)
	{
		iterator	iter = Find(Key);

		if (iter == End())
			return iter;

		return erase(iter);
	}

	iterator erase(const iterator& iter)
	{
		if (iter == End())
			return iter;

		// 리프노드인지 판단한다.
		if (!iter.mNode->mLeft && !iter.mNode->mRight)
		{
			// 지울노드의 부모노드가 없을 수도 있다.
			// 이 경우 루트노드인데 이 if문 안은 이미 리프노드일 경우
			// 들어오는 조건이므로 루트인데 리프노드라면 마지막 1개남은
			// 노드를 제거하는것이 된다.
			if (!iter.mNode->mParent)
				mRoot = nullptr;

			// 지울 노드가 부모노드의 왼쪽 자식인지 오른쪽 자식인지를
			// 판단하여 해당 주소를 nullptr로 변경한다.
			else if (iter.mNode->mParent->mLeft == iter.mNode)
				iter.mNode->mParent->mLeft = nullptr;

			else
				iter.mNode->mParent->mRight = nullptr;

			Node* Prev = iter.mNode->mPrev;
			Node* Next = iter.mNode->mNext;

			Prev->mNext = Next;
			Next->mPrev = Prev;

			delete iter.mNode;
			--mSize;

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

		else if (iter.mNode->mLeft)
		{
			Node* DeleteNode = FindMax(iter.mNode->mLeft);

			// 노드의 Key와 Valud를 지울노드의 Key와 Value로 대체한다.
			iter.mNode->mKey = DeleteNode->mKey;
			iter.mNode->mValue = DeleteNode->mValue;

			// 찾아준 노드의 왼쪽 자식이 있을 경우 왼쪽 자식노드를
			// 지울 노드의 자리로 옮겨준다.
			if (DeleteNode->mLeft)
			{
				if (DeleteNode->mParent->mLeft == DeleteNode)
					DeleteNode->mParent->mLeft = DeleteNode->mLeft;

				else
					DeleteNode->mParent->mRight = DeleteNode->mLeft;

				DeleteNode->mLeft->mParent = DeleteNode->mParent;
			}

			else
			{
				if (DeleteNode->mParent->mLeft == DeleteNode)
					DeleteNode->mParent->mLeft = nullptr;

				else
					DeleteNode->mParent->mRight = nullptr;
			}

			Node* Prev = iter.mNode->mPrev;
			Node* Next = iter.mNode->mNext;

			Prev->mNext = Next;
			Next->mPrev = Prev;

			delete iter.mNode;
			--mSize;

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

		else
		{
			Node* DeleteNode = FindMin(iter.mNode->mRight);

			// 노드의 Key와 Valud를 지울노드의 Key와 Value로 대체한다.
			iter.mNode->mKey = DeleteNode->mKey;
			iter.mNode->mValue = DeleteNode->mValue;

			// 찾아준 노드의 오른쪽 자식이 있을 경우 오른쪽 자식노드를
			// 지울 노드의 자리로 옮겨준다.
			if (DeleteNode->mRight)
			{
				if (DeleteNode->mParent->mLeft == DeleteNode)
					DeleteNode->mParent->mLeft = DeleteNode->mRight;

				else
					DeleteNode->mParent->mRight = DeleteNode->mRight;

				DeleteNode->mRight->mParent = DeleteNode->mParent;
			}

			else
			{
				if (DeleteNode->mParent->mLeft == DeleteNode)
					DeleteNode->mParent->mLeft = nullptr;

				else
					DeleteNode->mParent->mRight = nullptr;
			}

			Node* Prev = iter.mNode->mPrev;
			Node* Next = iter.mNode->mNext;

			Prev->mNext = Next;
			Next->mPrev = Prev;

			delete iter.mNode;
			--mSize;

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

	/*T& operator [] (const KEY& Key)	const
	{
		iterator	iter = Find(Key);

		if (iter == End())
	}*/

private:
	

	iterator& Find(const KEY& Key, Node* CurrentNode)	const
	{
		if (!CurrentNode)
			return End();

		if (Key == CurrentNode->mKey)
		{
			static iterator	iter;
			iter.mNode = CurrentNode;
			return iter;
		}

		else if (Key < CurrentNode->mKey)
			return Find(Key, CurrentNode->mLeft);

		return Find(Key, CurrentNode->mRight);
	}

	Node* FindMax(Node* CurrentNode)	const
	{
		while (CurrentNode->mRight)
		{
			CurrentNode = CurrentNode->mRight;
		}

		return CurrentNode;
	}

	Node* FindMin(Node* CurrentNode)	const
	{
		while (CurrentNode->mLeft)
		{
			CurrentNode = CurrentNode->mLeft;
		}

		return CurrentNode;
	}
};

Reference

좋은 알고리즘 사이트 링크