트리(Tree) - c++

 

 

▶️ 트리(Tree)

• 트리는 비선형구조 자료구조입니다.
  • 일자로 표현되지 않습니다.
• 캐릭터 본을 표현할때 사용한다고 합니다.
• 계층구조를 표현할때 사용합니다.

 

• 트리는 위 그림처럼 표현됩니다.

 

• 동그라미 하나를 노드라고 부릅니다.

 

• 아래에 다른 노드들이 달려있다면 위에있는 노드를 '부모 노드'라고 부르며 아래 노드들을 '자식 노드'라고  부릅니다.

 

• 빨간색박스 또는 파란색 박스에 있는 트리들을 '서브 트리'라고 부릅니다. 하나의 트리에는 여러 서브트리를 가질 수 있습니다. 

 

• 맨위에 있는 노드를 '루트 노드'라고 합니다.

 

• 맨아래에 자식이 없는 노드들을 '리프 노드'라고 합니다.

 

• 높이 (깊이, 차수) :
  • 루트 노드(맨 위에 있는 노드)의 차수는 0
  • 루트 노드의 자식들은 차수가 1
  • 루트 노드의 자식의 자식들은 차수가 2 

 

▶️ 트리의 종류 : 크게 이진트리와 비이진트리로 나뉩니다.

 

▶️이진트리 : 

• 이진트리는 이진 탐색트리와 레드 블랙 트리 등이 있습니다
• 이진 트리의 경우 최대 자식 노드의 갯수는 2개 입니다.
• 일반 이진 트리의 입력 순서는 입력된 순서대로 노드의 순서가 결정됩니다.
• 이진 탐색 트리의 입력 순서는 부모 노드를 기준으로 값이 작으면 왼쪽, 부모노드보다 값이 크면 오른족에 들어갑니다.
  • 검색이 가능해집니다. 
  • 탐색에 최적화된 트리입니다.
  • 데이터가 많을수록 빠릅니다.
• 이진 탐색 트리의 문제점 : 편향트리 - 한쪽으로 치우쳐진 트리. 
  • 편향트리를 막아주는 AVL알고리즘을 이용하여 편향트리를 방지할 수 있습니다. 
• 이진 탐색 트리의 경우 잦은 정렬로 추가 삭제가 느리기 때문에, 빈번한 추가 삭제가 있는 경우 사용하면 비효율적입니다.
  • 미리 데이터를 넣어놓고 탐색해서 사용하는 용도로 사용하길 추천합니다. 

 

 

▶️비이진트리

• 비이진트리에는 쿼드트리와 옥트리 등이 있습니다.
• 쿼드트리 :
  • 최대 자식 노드의 갯수는 4개 입니다. 
  • 평면에 적합하며, 공간분할 최적화에 주로 사용합니다. 
  •  

• 옥 트리 :
  • 최대 자식 노드의 갯수는 8개 입니다.
  • 3차원 공간 분할 최적화에 주로 사용합니다.
  • 충돌 알고리즘을 구현할때 사용합니다.  

 

 

 

▶️ 리스트를 이용한 트리 (기본트리) 구현

tree.h

// tree.h

#pragma once
// 직접 구현한 Array를 사용 
#include "Array.h"
#include <assert.h>

template <typename Key, typename Value>
class CTreeNode
{
	template <typename Key, typename Value>
	friend class CTree;

public : 
	CTreeNode() {}
	~CTreeNode() {}

private : 
	Key mKey;
	Value mData;
	// 자식 노드들을 가지고 있는 배열 
	CArray <CTreeNode<Key, Value>* > mChildArray;
	CTreeNode <Key, Value>* mParent = nullptr;
};

template <typename Key, typename Value>
class CTree
{
	typedef CTreeNode<Key, Value> NODE;
public : 
	CTree() {};
	~CTree() 
	{
		clear();
	};

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

public :
	void insert( const Key& key, const Value& data, const Key& parentKey )
	{
		NODE* node = new NODE;
		node->mData = data;
		node->mKey = key;

		NODE* parent = FindNode( mRoot, parentKey );

		if ( parent )
		{
			parent->mChildArray.push_back( node );
			node->mParent = parent;
		}
		else
		{
			if ( mRoot )
			{
				mRoot->mParent = node;
				node->mChildArray.push_back( mRoot );
			}

			mRoot = node;
		}
		
		++mSize;
	}

	void clear()
	{
		clear( mRoot );

		mSize = 0;
	}

	void Print()
	{
		Print( mRoot );
	}

private : 

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

		std::cout << "node : " << node->mKey << std::endl;
		std::cout << "parent : ";

		if ( node->mParent )
			std::cout << node->mParent->mKey << std::endl;
		else
			std::cout << "none" << std::endl;

		int childSize = node->mChildArray.size();

		for ( int i = 0; i < childSize; i++ )
		{
			std::cout << "child" << i << " : " << node->mChildArray[i]->mKey << std::endl;
		}

		std::cout << std::endl;

		for ( int i = 0; i < childSize; i++ )
		{
			Print( node->mChildArray[i] );
		}
	}

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

		int childSize = node->mChildArray.size();

		for ( int i = 0; i < childSize; i++ )
		{
			clear( node->mChildArray[i] );
		}
	}

	NODE* FindNode( NODE* node, const Key& key )
	{
		if ( !node )
			return nullptr;

		else if ( node->mKey == key )
			return node;

		else
		{
			int childSize = node->mChildArray.size();

			for ( int i = 0; i < childSize; i++ )
			{
				NODE* find = FindNode( node->mChildArray[i], key );

				if ( find )
					return find;
			}

			return nullptr;
		}
	}
};

main.cpp

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

int main()
{
	CTree <std::string, int> tree;

	tree.insert( "node1", 10, "none" );
	tree.insert( "node2", 20, "node1" );
	tree.insert( "node3", 30, "node1" );
	tree.insert( "node4", 40, "node2" );
	tree.insert( "node5", 50, "node2" );
	tree.insert( "node6", 60, "node2" );
	tree.insert( "node7", 70, "node3" );
	tree.insert( "node8", 80, "none" );

	tree.Print();

	return 0;
 }

Array.h

#pragma once

#include <memory.h>
#include <assert.h>

template <typename T>
class CArrayIterator
{
	template <typename T>
	friend class CArray;

public:
	CArrayIterator()
	{}

	~CArrayIterator()
	{}

public:
	T& operator * ()
	{
		return mArray->mArray[mIndex];
	}

	void operator ++ ()
	{
		++mIndex;
		assert( ( mIndex <= mArray->mSize + 1 &&
			mIndex >= 1 ) );
	}

	void operator ++ ( int )
	{
		++mIndex;
		assert( ( mIndex <= mArray->mSize + 1 &&
			mIndex >= 1 ) );
	}

	void operator -- ()
	{
		--mIndex;
		assert( ( mIndex <= mArray->mSize + 1 &&
			mIndex >= 1 ) );
	}

	void operator -- ( int )
	{
		--mIndex;
		assert( ( mIndex <= mArray->mSize + 1 &&
			mIndex >= 1 ) );
	}

	CArrayIterator<T> operator + ( int Num )	const
	{
		CArrayIterator<T>	iter;
		iter.mArray = mArray;
		iter.mIndex = mIndex + Num;
		assert( ( iter.mIndex <= mArray->mSize + 1 &&
			iter.mIndex >= 1 ) );

		return iter;
	}

	CArrayIterator<T> operator - ( int Num )	const
	{
		CArrayIterator<T>	iter;
		iter.mArray = mArray;
		iter.mIndex = mIndex - Num;
		assert( ( iter.mIndex <= mArray->mSize + 1 &&
			iter.mIndex >= 1 ) );

		return iter;
	}

	const CArrayIterator<T>& operator += ( int Num )
	{
		mIndex += Num;
		assert( ( mIndex <= mArray->mSize + 1 &&
			mIndex >= 1 ) );

		return *this;
	}

	const CArrayIterator<T>& operator -= ( int Num )
	{
		mIndex -= Num;
		assert( ( mIndex <= mArray->mSize + 1 &&
			mIndex >= 1 ) );

		return *this;
	}

	// =, ->
	bool operator == ( const CArrayIterator<T>& iter )	const
	{
		return mIndex == iter.mIndex;
	}

	bool operator != ( const CArrayIterator<T>& iter )	const
	{
		return mIndex != iter.mIndex;
	}

private:
	int	mIndex = -1;
	CArray<T>* mArray;
	//T* mValue = nullptr;
};

template <typename T>
class CArray
{
	template <typename T>
	friend class CArrayIterator;

public:
	typedef CArrayIterator<T>	iterator;

public:
	CArray()
	{}

	CArray( const CArray<T>& Arr )
	{}

	CArray( CArray<T>&& Arr )
	{}

	~CArray()
	{
		if ( nullptr != mArray )
			delete[] mArray;
	}

private:
	T* mArray = nullptr;
	int	mSize = 0;
	int	mCapacity = 0;

public:
	void push_back( const T& Data )
	{
		// 배열이 꽉 찼는지 판단한다.
		if ( mCapacity == mSize )
		{
			if ( nullptr == mArray )
			{
				ReAlloc( 1 );
			}

			else
			{
				int	NewCapacity = ( int )( mCapacity * 1.5f );

				if ( NewCapacity == 1 )
					NewCapacity = 2;

				ReAlloc( NewCapacity );
			}
		}

		mArray[mSize + 1] = Data;
		++mSize;
	}

	void push_back( T&& Data )
	{
		// 배열이 꽉 찼는지 판단한다.
		if ( mCapacity == mSize )
		{
			if ( nullptr == mArray )
			{
				ReAlloc( 1 );
			}

			else
			{
				int	NewCapacity = ( int )( mCapacity * 1.5f );

				if ( NewCapacity == 1 )
					NewCapacity = 2;

				ReAlloc( NewCapacity );
			}
		}

		mArray[mSize + 1] = Data;
		++mSize;
	}

	void pop_back()
	{
		assert( mSize != 0 );

		--mSize;
	}

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

	int size()	const
	{
		return mSize;
	}

	int capacity()	const
	{
		return mCapacity;
	}

	void clear()
	{
		mSize = 0;
	}

	// reserve는 기존 capacity보다 작게
	// 설정될 경우 아무런 일도 없다.
	// 클 경우 기존 사이즈는 그대로 유지하며
	// capacity만 지정된 크기로 늘어나서
	// 배열 크기만 이만큼 만들게 된다.
	// 기존의 값은 그대로 유지된다.
	void reserve( int NewCapacity )
	{
		if ( NewCapacity > mCapacity )
		{
			ReAlloc( NewCapacity );
		}
	}

	// resize는 기존 capacity보다 작게
	// 설정될 경우 capacity는 유지하며
	// size만 감소시킨다.
	// 클 경우에는 capacity만 늘려준다.
	// 기존에 들어가있는 값이 있다면 유지한다.
	void resize( int NewCapacity )
	{
		/*if (NewCapacity < mCapacity)
		{
			mSize = NewCapacity;
		}*/

		if ( NewCapacity > mCapacity )
		{
			ReAlloc( NewCapacity );
		}

		mSize = NewCapacity;
	}

	T& operator [] ( int Index )
	{
		assert( 0 <= Index && Index < mSize );

		return mArray[Index + 1];
	}

	iterator begin()
	{
		iterator	iter;
		iter.mArray = this;
		iter.mIndex = 1;
		return iter;
	}

	iterator end()
	{
		iterator	iter;
		iter.mArray = this;
		iter.mIndex = mSize + 1;
		return iter;
	}

	iterator erase( const iterator& iter )
	{
		assert( ( iter.mIndex < mSize + 1 &&
			iter.mIndex >= 1 ) );

		for ( int i = iter.mIndex; i < mSize; ++i )
		{
			mArray[i] = mArray[i + 1];
		}

		--mSize;

		return iter;
	}

private:
	void ReAlloc( int NewCapacity )
	{
		mCapacity = NewCapacity;
		// Begin과 End를 표현하기 위한
		// 여유공간 2개가 더 필요하다.
		T* Array = new T[mCapacity + 2];

		// 기존 데이터가 있을 경우 유지
		if ( nullptr != mArray )
		{
			// 기존 데이터를 복제할 때 1번부터
			// 개수만큼 복제
			memcpy( Array + 1, mArray + 1,
				sizeof( T ) * mSize );
			delete[] mArray;
		}

		mArray = Array;
	}
};