cblockavltree.h

本人自己的作品

	_data[C].node.Left(X);
	_data[C].node.LeftHei(_data[C].node.Height());

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

	_data[C].node.Right(B);
	_data[C].node.RightHei(_data[B].node.Height());

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

CBLOCKAVLTREE_TEMPLATE
void CBLOCKAVLTREE::BalanceTree(CThisStack& node_stack)
{
	long child = node_stack.top().link;
	ATLASSERT(_data[child].node.LeftHei() < 2 && _data[child].node.LeftHei() > -2);
	ATLASSERT(_data[child].node.RightHei() < 2 && _data[child].node.RightHei() > -2);
	node_stack.pop();
	IterNode iternode;
	bool isturn(false);
	long sb;
	while(child > ZEROLINK)
	{
		isturn = false;
		if(_data[child].node.balance() >= 2)
		{
			sb = _data[child].node.Left();
			if(_data[sb].node.balance() > ZEROLINK)
				LLTurn(child);
			else
				LRTurn(child);
			isturn = true;
		}
		else if(_data[child].node.balance() <= -2)
		{
			sb = _data[child].node.Right();
			if(_data[sb].node.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(_data[iternode.link].node.Right() == child);
				else
					_data[iternode.link].node.Right(child);
				_data[iternode.link].node.RightHei(_data[child].node.Height());
			}
			else
			{
				if(!isturn)
					ATLASSERT(_data[iternode.link].node.Left() == child);
				else
					_data[iternode.link].node.Left(child);
				_data[iternode.link].node.LeftHei(_data[child].node.Height());
			}
			child = iternode.link;
		}
	}
}
//修改已存在数据的非索引的值
CBLOCKAVLTREE_TEMPLATE
bool CBLOCKAVLTREE::modify(const T& data)
{
	long tmp = _head;
	while(tmp > ZEROLINK)
	{
		if(_data[tmp].node == data)
		{
			_data[tmp].node.Data(data);
			return true;
		}
		if(_data[tmp].node < data)
			tmp = _data[tmp].node.Right();
		else
			tmp = _data[tmp].node.Left();
	}
	return false;
}
CBLOCKAVLTREE_TEMPLATE
bool CBLOCKAVLTREE::insert(const T& data)
{
	if(_head < 0)
	{
		_head = New();
		_data[_head].node.Data(data);
		_size = 1;
		return true;
	}
	CThisStack node_stack;
	long tmp = _head;
	IterNode iternode;
	while(tmp > ZEROLINK)
	{
		if(_data[tmp].node == data)
		{
			_data[tmp].node.Data(data);
			return true;
		}
		iternode.link = tmp;
		if(_data[tmp].node < data)
		{
			iternode.where = iterator::avl_right;
			tmp = _data[tmp].node.Right();
		}
		else
		{
			tmp = _data[tmp].node.Left();
			iternode.where = iterator::avl_left;
		}
		node_stack.push(iternode);
	}
	long ins = New();
	_data[ins].node.Data(data);
	_data[ins].node.Left(ZEROLINK);
	_data[ins].node.Right(ZEROLINK);
	_data[ins].node.LeftHei(0);
	_data[ins].node.RightHei(0);

	iternode = node_stack.top();
	if(iternode.where)
	{
		_data[iternode.link].node.Right(ins);
		_data[iternode.link].node.RightHei(1);
		ATLASSERT(_data[iternode.link].node.LeftHei() <= 1);
	}
	else
	{
		_data[iternode.link].node.Left(ins);
		_data[iternode.link].node.LeftHei(1);
		ATLASSERT(_data[iternode.link].node.RightHei() <= 1);
	}
	_size++;
	BalanceTree(node_stack);
	return true;
}
//插入;
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::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;
}

//查找替代者
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::GetDt(CThisStack& node_stack,long sb)
{
	//查找替代者，要求：一定是无子树的叶
	IterNode iternode;
	ATLASSERT(sb > ZEROLINK && sb < _maxsize);
	if(_data[sb].node.Left() > ZEROLINK)//找最大的左子树值来
	{
		iternode.where = iterator::avl_left;
		iternode.link  = sb;
		node_stack.push(iternode);
		iternode.link = _data[sb].node.Left();
		iternode.where = iterator::avl_right;
		while(_data[iternode.link].node.Right() > ZEROLINK)
		{
			node_stack.push(iternode);
			iternode.link = _data[iternode.link].node.Right();
		}
		_data[sb].node.Data(_data[iternode.link].node.Data());//还要向下删除data
		return GetDt(node_stack,iternode.link);
	}
	else if(_data[sb].node.Right() > ZEROLINK)//找最小的左子树值来
	{
		iternode.where = iterator::avl_right;
		iternode.link = sb;
		node_stack.push(iternode);
		iternode.link = _data[sb].node.Right();
		iternode.where = iterator::avl_left;
		while(_data[iternode.link].node.Left() > ZEROLINK)
		{
			node_stack.push(iternode);
			iternode.link = _data[iternode.link].node.Left();
		}
		_data[sb].node.Data(_data[iternode.link].node.Data());//还要向下删除data
		return GetDt(node_stack,iternode.link);
	}
	else
	{
		return sb;
	}
}
//删除
CBLOCKAVLTREE_TEMPLATE
bool CBLOCKAVLTREE::erase(T& data)
{
	if(_head < 0)
	{
		return false;
	}
	CThisStack node_stack;
	long tmp = _head;
	IterNode iternode;
	while(tmp > ZEROLINK)
	{
		if(_data[tmp].node == data)
		{
			data = _data[tmp].node.Data();
			break;
		}
		iternode.link = tmp;
		if(_data[tmp].node < data)
		{
			tmp = _data[tmp].node.Right();
			iternode.where = iterator::avl_right;
		}
		else
		{
			tmp = _data[tmp].node.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(_data[iternode.link].node.Left() == tmp || _data[iternode.link].node.Right() == tmp);
	ATLASSERT(_data[iternode.link].node.LeftHei() <= 2 && _data[iternode.link].node.RightHei() <= 2);
	if(iternode.where == iterator::avl_left)
	{
		_data[iternode.link].node.Left(ZEROLINK);
		_data[iternode.link].node.LeftHei(0);
		if(_data[iternode.link].node.Right() > ZEROLINK)
		{
			iternode.where = iterator::avl_right;
			node_stack.push(iternode);
			iternode.link = _data[iternode.link].node.Right();
		}
	}
	else
	{
		_data[iternode.link].node.Right(ZEROLINK);
		_data[iternode.link].node.RightHei(0);
		if(_data[iternode.link].node.Left() > ZEROLINK)
		{
			iternode.where = iterator::avl_left;
			node_stack.push(iternode);
			iternode.link = _data[iternode.link].node.Left();
		}
	}
	node_stack.push(iternode);
	//
	Delete(tmp);
	_size--;
	if(_size)
		BalanceTree(node_stack);
	else
		_head = NULL;
	return true;
}
//删除一区
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::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;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::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;
}
//改变
CBLOCKAVLTREE_TEMPLATE
bool CBLOCKAVLTREE::modify(const T& old,const T& now)
{
	T old2 = old;
	if(erase(old2))
	{
		if(!insert(now))
			ATLASSERT(0);
		return true;
	}
	return false;
}
//////////////////////////////////////////////////////////////////
///////////////////////////测试//////////////////////////
CBLOCKAVLTREE_TEMPLATE
void CBLOCKAVLTREE::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(_data[iter.nowsb()].node.balance() > -2 && _data[iter.nowsb()].node.balance() < 2);
		pre = *iter;
		sz++;
	}
	ATLASSERT(sz == _size);
	iter--;
	while(iter)
	{
		sz--;
		iter--;
	}
	ATLASSERT(sz == 0);
}
//////////////////////////////////////////////////////////////////
/////////////////////////////迭代器////////////////////////////

//最头一个
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::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 = _data[iternode.link].node.Left();
	}
	if(iter._nodes->size())
	{
		iternode = iter._nodes->top();
		iter._nodes->pop();
		iternode.where = iterator::avl_now;
		iter._nodes->push(iternode);
	}
	return iter;
}
//最后一个
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::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 = _data[iternode.link].node.Right();
	}
	if(iter._nodes->size())
	{
		iternode = iter._nodes->top();
		iter._nodes->pop();
		iternode.where = iterator::avl_now;
		iter._nodes->push(iternode);
	}
	return iter;
}
//最后
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::end() const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	iter._bof = false;
	iter._eof = true;
	iter._ptree = this;
	return iter;
}
//最前
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::bof() const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	iter._bof = true;
	iter._eof = false;
	iter._ptree = this;
	return iter;
}