void AM_Tree::insert(const map<int, double, item_cmp> &transaction)
{
    int depth = 0;
	double _util = 0;
	double _clo_util = 0;
	map<int, double, item_cmp> _util_list;
	map<int, double, item_cmp>::const_iterator Tit = transaction.begin(); //iterator開始insert node
	map<int, shared_ptr<Node>, item_cmp>::iterator Cit; //iterator指到root children
	shared_ptr<Node> Nptr = root;
	
	//handle item which is include in root->itemset
	if(root->itemset.size() != 0)
	{	
		map<int, double, item_cmp>::const_iterator Rit = transaction.find(root->itemset.back()); //指到目前root最大的item
		while(Rit != transaction.end())
		{
			_util_list.insert(make_pair(Rit->first,Rit->second));
			_util += Rit->second;
			_clo_util += Rit->second;
			Rit++;
		}
	}
	//handle others
	while(depth != transaction.size()-root->itemset.size())//here
	{
		if((Cit = Nptr->children.find(Tit->first)) != Nptr->children.end()) //node exist
			Nptr = Cit->second;
		else //node didn't exist
		{
			Nptr->children.insert(make_pair(Tit->first, make_shared<Node>(Node(Tit->first))));
			Nptr = Nptr->children[Tit->first];
			if(depth) //新node才有可能連到HeaderTable
				HeaderTable[Tit->first].push_back(Nptr);
		}
		_util_list.insert(make_pair(Tit->first, Tit->second));
		_clo_util += Tit->second; //plus IUTable clo_util

		vector<int> index = root->itemset;
		index.push_back(Tit->first);
		IUTable[index].util += Tit->second + _util; //plus IUTable util
		if(depth) {//第二個node以後才需要加clo_util
			IUTable[index].clo_util += _clo_util;
			map<int, double, item_cmp>::iterator It = _util_list.begin();
			for(;It != _util_list.end();++It)
				Nptr->util_list[It->first] += It->second;
		}
		++Tit;
		++depth;
	}
}