carrayavltree.h

本人自己的作品

			tree.erase(era[i]);
			insert(era[i]);
		}
	}
	delete[] era;
	return ca;
}
//////////////////////////////////////////////////////////////////
/////////////////////////////插入与删除///////////////////////////
//旋转
CARRAYAVLTREE_TEMPLATE
short CARRAYAVLTREE::LLTurn(short& X)
{
	ATLASSERT(_node[X].balance() == 2);
	short B = _node[X].Left();

	_node[X].Left(_node[B].Right());
	if(_node[B].Right() == ZEROLINK)
		_node[X].LeftHei(0);
	else
		_node[X].LeftHei(_node[_node[B].Right()].Height());

	_node[B].Right(X);
	_node[B].RightHei(_node[X].Height());
	X = B;//实际指向我
	ATLASSERT(_node[X].balance() < 2);
	return B;
}
CARRAYAVLTREE_TEMPLATE
short CARRAYAVLTREE::LRTurn(short& X)
{
	ATLASSERT(_node[X].balance() == 2);
	short B = _node[X].Left();
	short C = _node[B].Right();

	_node[X].Left(_node[C].Right());
	if(_node[C].Right() == ZEROLINK)
		_node[X].LeftHei(0);
	else
		_node[X].LeftHei(_node[_node[C].Right()].Height());

	_node[C].Right(X);
	_node[C].RightHei(_node[X].Height());

	_node[B].Right(_node[C].Left());
	if(_node[C].Left() == ZEROLINK)
		_node[B].RightHei(0);
	else
		_node[B].RightHei(_node[_node[C].Left()].Height());

	_node[C].Left(B);
	_node[C].LeftHei(_node[B].Height());
	X = C;//实际指向我
	ATLASSERT(_node[X].balance() < 2);
	return C;
}
CARRAYAVLTREE_TEMPLATE
short CARRAYAVLTREE::RRTurn(short& X)
{
	ATLASSERT(_node[X].balance() == -2);
	short B = _node[X].Right();

	_node[X].Right(_node[B].Left());
	_node[X].RightHei(_node[B].Left() > ZEROLINK ?
		_node[_node[B].Left()].Height() : 0);

	_node[B].Left(X);
	_node[B].LeftHei(_node[X].Height());
	X = B;//实际指向我
	ATLASSERT(_node[X].balance() > -2);
	return B;
}
CARRAYAVLTREE_TEMPLATE
short CARRAYAVLTREE::RLTurn(short& X)
{
	short sb;//其实不怕，不会变了
	ATLASSERT(_node[X].balance() == -2);
	short B = _node[X].Right();
	short C = _node[B].Left();

	sb = _node[C].Left();
	_node[X].Right(sb);
	_node[X].RightHei(_node[C].Left() > ZEROLINK ? _node[sb].Height() : 0);

	_node[C].Left(X);
	_node[C].LeftHei(_node[C].Height());

	sb = _node[C].Right();
	_node[B].Left(sb);
	_node[B].LeftHei(_node[C].Right() > ZEROLINK ? _node[sb].Height() : 0);

	_node[C].Right(B);
	_node[C].RightHei(_node[B].Height());

	X = C;//实际指向我
	ATLASSERT(_node[X].balance() > -2);
	return X;
}

CARRAYAVLTREE_TEMPLATE
void CARRAYAVLTREE::BalanceTree(CThisStack& node_stack)
{
	short child = node_stack.top().link;
	ATLASSERT(_node[child].LeftHei() < 2 && _node[child].LeftHei() > -2);
	ATLASSERT(_node[child].RightHei() < 2 && _node[child].RightHei() > -2);
	node_stack.pop();
	IterNode iternode;
	bool isturn(false);
	short sb;
	while(child > ZEROLINK)
	{
		isturn = false;
		if(_node[child].balance() >= 2)
		{
			sb = _node[child].Left();
			if(_node[sb].balance() > ZEROLINK)
				LLTurn(child);
			else
				LRTurn(child);
			isturn = true;
		}
		else if(_node[child].balance() <= -2)
		{
			sb = _node[child].Right();
			if(_node[sb].balance() <= 0)
				RRTurn(child);
			else
				RLTurn(child);
			isturn = true;
		}
		if(node_stack.empty())
		{
			if(!isturn)
				ATLASSERT(_head == child);
			else
				_head = child;
			break;
		}
		else
		{
			iternode = node_stack.top();
			node_stack.pop();
			if(iternode.where == iterator::avl_right)
			{
				if(!isturn)
					ATLASSERT(_node[iternode.link].Right() == child);
				else
					_node[iternode.link].Right(child);
				_node[iternode.link].RightHei(_node[child].Height());
			}
			else
			{
				if(!isturn)
					ATLASSERT(_node[iternode.link].Left() == child);
				else
					_node[iternode.link].Left(child);
				_node[iternode.link].LeftHei(_node[child].Height());
			}
			child = iternode.link;
		}
	}
}
//修改已存在数据的非索引的值
CARRAYAVLTREE_TEMPLATE
bool CARRAYAVLTREE::modify(const T& data)
{
	short tmp = _head;
	while(tmp > ZEROLINK)
	{
		if(_node[tmp] == data)
		{
			_node[tmp].Data(data);
			return true;
		}
		if(_node[tmp] < data)
			tmp = _node[tmp].Right();
		else
			tmp = _node[tmp].Left();
	}
	return false;
}
CARRAYAVLTREE_TEMPLATE
bool CARRAYAVLTREE::insert(const T& data)
{
	if(_head < 0)
	{
		_head = New();
		_node[_head].Data(data);
		_size = 1;
		return true;
	}
	if(_size >= ARRAYSIZE)
	{
		throw _T("已达到最大存储位置,无法加入任何数据!");
		return false;
	}
	CThisStack node_stack;
	short tmp = _head;
	IterNode iternode;
	while(tmp > ZEROLINK)
	{
		if(_node[tmp] == data)
		{
			_node[tmp].Data(data);
			return true;
		}
		iternode.link = tmp;
		if(_node[tmp] < data)
		{
			iternode.where = iterator::avl_right;
			tmp = _node[tmp].Right();
		}
		else
		{
			tmp = _node[tmp].Left();
			iternode.where = iterator::avl_left;
		}
		node_stack.push(iternode);
	}
	short ins	= New();
	_node[ins].Data(data);
	_node[ins].Left(ZEROLINK);
	_node[ins].Right(ZEROLINK);
	_node[ins].LeftHei(0);
	_node[ins].RightHei(0);

	iternode = node_stack.top();
	if(iternode.where)
	{
		_node[iternode.link].Right(ins);
		_node[iternode.link].RightHei(1);
		ATLASSERT(_node[iternode.link].LeftHei() <= 1);
	}
	else
	{
		_node[iternode.link].Left(ins);
		_node[iternode.link].LeftHei(1);
		ATLASSERT(_node[iternode.link].RightHei() <= 1);
	}
	_size++;
	BalanceTree(node_stack);
	return true;
}
//插入;
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::insertrange(T* first,long size)
{
	if(!first || !size)
		return 0;
	long sz = 0;
	for(long i = 0;i < size;i++)
		if(insert(first[i]))
			sz++;
	return sz;
}

//查找替代者
CARRAYAVLTREE_TEMPLATE
short CARRAYAVLTREE::GetDt(CThisStack& node_stack,short sb)
{
	//查找替代者，要求：一定是无子树的叶
	IterNode iternode;
	ATLASSERT(sb > ZEROLINK && sb < ARRAYSIZE);
	if(_node[sb].Left() > ZEROLINK)//找最大的左子树值来
	{
		iternode.where = iterator::avl_left;
		iternode.link  = sb;
		node_stack.push(iternode);
		iternode.link = _node[sb].Left();
		iternode.where = iterator::avl_right;
		while(_node[iternode.link].Right() > ZEROLINK)
		{
			node_stack.push(iternode);
			iternode.link = _node[iternode.link].Right();
		}
		_node[sb].Data(_node[iternode.link].Data());//还要向下删除data
		return GetDt(node_stack,iternode.link);
	}
	else if(_node[sb].Right() > ZEROLINK)//找最小的左子树值来
	{
		iternode.where = iterator::avl_right;
		iternode.link = sb;
		node_stack.push(iternode);
		iternode.link = _node[sb].Right();
		iternode.where = iterator::avl_left;
		while(_node[iternode.link].Left() > ZEROLINK)
		{
			node_stack.push(iternode);
			iternode.link = _node[iternode.link].Left();
		}
		_node[sb].Data(_node[iternode.link].Data());//还要向下删除data
		return GetDt(node_stack,iternode.link);
	}
	else
	{
		return sb;
	}
}
//删除
CARRAYAVLTREE_TEMPLATE
bool CARRAYAVLTREE::erase(T& data)
{
	if(_head < 0)
	{
		return false;
	}
	CThisStack node_stack;
	short tmp = _head;
	IterNode iternode;
	while(tmp > ZEROLINK)
	{
		if(_node[tmp] == data)
		{
			data = _node[tmp].Data();
			break;
		}
		iternode.link = tmp;
		if(_node[tmp] < data)
		{
			tmp = _node[tmp].Right();
			iternode.where = iterator::avl_right;
		}
		else
		{
			tmp = _node[tmp].Left();
			iternode.where = iterator::avl_left;
		}
		node_stack.push(iternode);
	}
	if(tmp < 0)
		return false;
	tmp = GetDt(node_stack,tmp);
	if(_head == tmp)
	{
		Delete(tmp);
		_size = 0;
		_head = ZEROLINK;
		return true;
	}
	iternode = node_stack.top();
	node_stack.pop();

	ATLASSERT(_node[iternode.link].Left() == tmp || _node[iternode.link].Right() == tmp);
	ATLASSERT(_node[iternode.link].LeftHei() <= 2 && _node[iternode.link].RightHei() <= 2);
	if(iternode.where == iterator::avl_left)
	{
		_node[iternode.link].Left(ZEROLINK);
		_node[iternode.link].LeftHei(0);
		if(_node[iternode.link].Right() > ZEROLINK)
		{
			iternode.where = iterator::avl_right;
			node_stack.push(iternode);
			iternode.link = _node[iternode.link].Right();
		}
	}
	else
	{
		_node[iternode.link].Right(ZEROLINK);
		_node[iternode.link].RightHei(0);
		if(_node[iternode.link].Left() > ZEROLINK)
		{
			iternode.where = iterator::avl_left;
			node_stack.push(iternode);
			iternode.link = _node[iternode.link].Left();
		}
	}
	node_stack.push(iternode);
	//
	Delete(tmp);
	_size--;
	if(_size)
		BalanceTree(node_stack);
	else
		_head = NULL;
	return true;
}
//删除一区
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::eraserange(T& first,T& last)
{
	std::vector<T> era;
	iterator f = find_lower(first);
	iterator l = find_lower(last);
	for(;f != l;f++)
		era.push_back(*f);
	long sz = era.size();
	for(long i = 0;i < sz;i++)
		erase(era[i]);
	return sz;
}
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::eraserange(T* first,long size)
{
	if(!first || !size)
		return 0;
	long sz = 0;
	for(long i = 0;i < size;i++)
		if(erase(first[i]))
			sz++;
	return sz;
}
//改变
CARRAYAVLTREE_TEMPLATE
bool CARRAYAVLTREE::modify(const T& old,const T& now)
{
	T old2 = old;
	if(erase(old2))
	{
		if(!insert(now))
			ATLASSERT(0);
		return true;
	}
	return false;
}
//////////////////////////////////////////////////////////////////
///////////////////////////测试//////////////////////////
CARRAYAVLTREE_TEMPLATE
void CARRAYAVLTREE::Iterator() const
{
	if(_head < 0)
		return;
	T pre;
	bool once(true);
	long sz(0);
	for(iterator iter = begin();iter;iter++)
	{
		if(!once)
		{
			ATLASSERT(pre < *iter);
			once = false;
		}
		ATLASSERT(_node[iter.nowsb()].balance() > -2 && _node[iter.nowsb()].balance() < 2);
		pre = *iter;
		sz++;
	}
	ATLASSERT(sz == _size);
	iter--;
	while(iter)
	{
		sz--;
		iter--;
	}
	ATLASSERT(sz == 0);
}
//////////////////////////////////////////////////////////////////
/////////////////////////////迭代器////////////////////////////

//最头一个
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::begin() const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	if(!iter._nodes.New())
		return iter;
	iter._ptree = this;
	IterNode iternode;
	iternode.link = _head;
	iternode.where = iterator::avl_left;
	while(iternode.link > ZEROLINK)
	{
		iter._nodes->push(iternode);
		iternode.link = _node[iternode.link].Left();
	}
	if(iter._nodes->size())
	{
		iternode = iter._nodes->top();
		iter._nodes->pop();
		iternode.where = iterator::avl_now;
		iter._nodes->push(iternode);
	}
	return iter;
}
//最后一个
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::last() const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	if(!iter._nodes.New())
		return iter;
	iter._ptree = this;
	IterNode iternode;
	iternode.link = _head;
	iternode.where = iterator::avl_right;
	while(iternode.link > ZEROLINK)
	{
		iter._nodes->push(iternode);
		iternode.link = _node[iternode.link].Right();
	}
	if(iter._nodes->size())
	{
		iternode = iter._nodes->top();
		iter._nodes->pop();
		iternode.where = iterator::avl_now;
		iter._nodes->push(iternode);
	}
	return iter;
}
//最后
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::end() const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	iter._bof = false;
	iter._eof = true;
	iter._ptree = this;
	return iter;
}
//最前
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::bof() const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	iter._bof = true;
	iter._eof = false;
	iter._ptree = this;
	return iter;
}