230101 Trial Algorithm

검색 알고리즘으로 사용되는 Trail 알고리즘을 구현해보았다.

 

#include <unordered_map>
#include <iostream>
#include <string>
#include <crtdbg.h>

class Trial
{
	class Node;
public:

	Trial()
	{
		Root = new Node();
	}

	~Trial()
	{
		if (nullptr != Root)
		{
			delete Root;
			Root = nullptr;
		}
	}
	void insert(std::string _word)
	{
		Node* curIter = Root;
		for (char _ch : _word)
		{
			if (curIter->child.end() == curIter->child.find(_ch))
			{
				curIter->child[_ch] = new Node();
			}
			curIter = curIter->child[_ch];
		}
		curIter->is_end = true;
	}

	bool Search(std::string _word)
	{
		Node* curIter = Root;
		for (char _ch : _word)
		{
			if (curIter->child.end() == curIter->child.find(_ch))
			{
				return false;
			}
			curIter = curIter->child[_ch];
		}
		if (true == curIter->is_end)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	bool SearchWith(std::string _word)
	{
		Node* curIter = Root;
		for (char _ch : _word)
		{
			if (curIter->child.end() == curIter->child.find(_ch))
			{
				return false;
			}
			curIter = curIter->child[_ch];
		}
		return true;
	}
private:
	class Node
	{
	public:
		Node()
		:is_end(false)
		{
		};

		~Node()
		{
			std::unordered_map<char, Node*>::iterator startit = child.begin();
			std::unordered_map<char, Node*>::iterator endit = child.end();
			for (;startit != endit; ++startit)
			{
				if (nullptr != startit->second)
				{
					delete startit->second;
					startit->second = nullptr;
				}
			}
			child.clear();
		}
		bool is_end;
		std::unordered_map<char, Node*> child;
	};

	Node* Root;
};

 

상위노드는 다음 단어를 가질 수 있도록 unordered_map으로 이를 관리한다.

 

근데 영어라면,,, 26자기 때문에 해당하는 단어를 hash로 바꾸는것보다 map을 사용하는게 빠를지도??라는 생각이 들었다.

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	Trial* struc_trial = new Trial();

	struc_trial->insert("apple");


	bool check;
	check = struc_trial->Search("app");
	check = struc_trial->SearchWith("app");

	struc_trial->insert("app");
	check = struc_trial->SearchWith("abce");

	delete struc_trial;
}

 

입력, 검색 테스트를 해보았다.