avltree.h

本人自己的作品

//////////////////////两树操作/////////////////////////
//分裂--自己留大的,别人给小的
template<class T,class MEM> inline
long CAVLTree<T,MEM>::onetotwo(CAVLTree<T,MEM>& tree)
{
	ATLASSERT(_head);
	T t   = _head->Data();
	_head = _head->Right();
	tree._head = _head->Left();
	insert(t);
	iterator iter = tree.begin();
	for(;iter;iter++)
		_size--,tree._size++;
	return _size;
}
//合并
template<class T,class MEM> inline
long CAVLTree<T,MEM>::marge(CAVLTree<T,MEM>& tree)
{
	iterator iter = tree.begin();
	for(;iter; iter++)
	{
		insert(*iter);
	}
	return _size;
}
//平衡
template<class T,class MEM> inline
long CAVLTree<T,MEM>::balance(CAVLTree<T,MEM>& tree)
{
	//一定保证此小tree大
	if(_node[_head] > tree._node[tree._head])
		return tree.balance(*this);

	long ca = abs((_size - tree._size)) / 2;
	iterator iter;
	long i;
	T* era = new T[ca];
	if(_size > tree._size)
	{
		iter = last();
		for(i = 0;i < ca;i++,iter--)
		{
			era[i] = *iter;
		}
		for(i = 0;i < ca;i++)
		{
			erase(era[i]);
			tree.insert(era[i]);
		}
	}
	else
	{
		iter = tree.begin();
		for(i = 1;i < ca;i++,iter++)
		{
			era[i] = *iter;
		}
		for(i = 0;i < ca;i++)
		{
			tree.erase(era[i]);
			insert(era[i]);
		}
	}
	delete[] era;
	return ca;
}
//////////////////////////////////////////////////////////////////
/////////////////////////////插入与删除///////////////////////////
//旋转
template<class T,class MEM> inline
CAVLTree<T,MEM>::CNode* CAVLTree<T,MEM>::LLTurn(CNode*& X)
{
	//ATLTRACE("LLTurn\n"));
	ATLASSERT(X->balance() == 2);
	CNode* B = X->Left();

	X->Left(B->Right());
	if(X->Left())
		X->LeftHei(X->Left()->Height());
	else
		X->LeftHei(0);

	B->Right(X);
	B->RightHei(X->Height());
	X = B;//实际指向我
	ATLASSERT(X->balance() < 2);
	return B;
}
template<class T,class MEM> inline
CAVLTree<T,MEM>::CNode* CAVLTree<T,MEM>::LRTurn(CNode*& X)
{
	//ATLTRACE("LRTurn\n"));
	ATLASSERT(X->balance() == 2);
	CNode* B = X->Left();
	CNode* C = B->Right();

	X->Left(C->Right());
	if(X->Left())
		X->LeftHei(X->Left()->Height());
	else
		X->LeftHei(0);

	C->Right(X);
	C->RightHei(X->Height());

	B->Right(C->Left());
	if(B->Right())
		B->RightHei(B->Right()->Height());
	else
		B->RightHei(0);

	C->Left(B);
	C->LeftHei(B->Height());
	X = C;//实际指向我
	ATLASSERT(X->balance() < 2);
	return C;
}
template<class T,class MEM> inline
CAVLTree<T,MEM>::CNode* CAVLTree<T,MEM>::RRTurn(CNode*& X)
{
	//ATLTRACE("RRTurn\n"));
	ATLASSERT(X->balance() == -2);
	CNode* B = X->Right();

	X->Right(B->Left());
	X->RightHei(X->Right() ? X->Right()->Height() : 0);

	B->Left(X);
	B->LeftHei(X->Height());
	X = B;//实际指向我
	ATLASSERT(X->balance() > -2);
	return B;
}
template<class T,class MEM> inline
CAVLTree<T,MEM>::CNode* CAVLTree<T,MEM>::RLTurn(CAVLTree<T,MEM>::CNode*& X)
{
	//ATLTRACE("RLTurn\n"));
	ATLASSERT(X->balance() == -2);
	CNode* B = X->Right();
	CNode* C = B->Left();

	X->Right(C->Left());
	X->RightHei(C->Left() ? C->Left()->Height() : 0);

	C->Left(X);
	C->LeftHei(C->Height());

	B->Left(C->Right());
	B->LeftHei(C->Right() ? C->Right()->Height() : 0);

	C->Right(B);
	C->RightHei(B->Height());

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

template<class T,class MEM> inline
void CAVLTree<T,MEM>::BalanceTree(CThisStack& node_stack)
{
	CNode* child = node_stack.top().link;
	ATLASSERT(child->LeftHei() < 2 && child->LeftHei() > -2);
	ATLASSERT(child->RightHei() < 2 && child->RightHei() > -2);
	node_stack.pop();
	IterNode iternode;
	bool isturn(false);
	CNode* node;
	while(child)
	{
		isturn = false;
		if(child->balance() >= 2)
		{
			node = child->Left();
			if(node->balance() >= 0)
				LLTurn(child);
			else
				LRTurn(child);
			isturn = true;
		}
		else if(child->balance() <= -2)
		{
			node = child->Right();
			if(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(iternode.link->Right() == child);
				else
					iternode.link->Right(child);
				iternode.link->RightHei(child->Height());
			}
			else
			{
				if(!isturn)
					ATLASSERT(iternode.link->Left() == child);
				else
					iternode.link->Left(child);
				iternode.link->LeftHei(child->Height());
			}
			child = iternode.link;
		}
	}
}
//修改已存在数据的非索引的值
template<class T,class MEM> inline
bool CAVLTree<T,MEM>::modify(const T& data)
{
	CNode* tmp = _head;
	while(tmp)
	{
		if(*tmp == data)
		{
			tmp->Data(data);
			return true;
		}
		if(*tmp < data)
			tmp = tmp->Right();
		else
			tmp = tmp->Left();
	}
	return false;
}
template<class T,class MEM> inline
bool CAVLTree<T,MEM>::insert(const T& data)
{
	if(!_head)
	{
		_head = _mem.Alloc();
		_head->Data(data);
		_size = 1;
		return true;
	}
	CThisStack node_stack;
	CNode* tmp = _head;
	IterNode iternode;
	while(tmp)
	{
		if(*tmp == data)
		{
			tmp->Data(data);
			return true;
		}
		iternode.link = tmp;
		if(*tmp < data)
		{
			iternode.where = iterator::avl_right;
			tmp = tmp->Right();
		}
		else
		{
			tmp = tmp->Left();
			iternode.where = iterator::avl_left;
		}
		node_stack.push(iternode);
	}
	tmp	= _mem.Alloc();
	tmp->Data(data);

	iternode = node_stack.top();
	if(iternode.where)
	{
		iternode.link->Right(tmp);
		iternode.link->RightHei(1);
		ATLASSERT(iternode.link->LeftHei() <= 1);
	}
	else
	{
		iternode.link->Left(tmp);
		iternode.link->LeftHei(1);
		ATLASSERT(iternode.link->RightHei() <= 1);
	}
	_size++;
	BalanceTree(node_stack);
	return true;
}
//插入;
template<class T,class MEM> inline
long CAVLTree<T,MEM>::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;
}

//查找替代者
template<class T,class MEM> inline
CAVLTree<T,MEM>::CNode* CAVLTree<T,MEM>::GetDt(CThisStack& node_stack,CNode* node)
{
	//查找替代者，要求：一定是无子树的叶
	IterNode iternode;
	ATLASSERT(node);
	if(node->Left())//找最大的左子树值来
	{
		//ATLTRACE("GetDt Left\n");
		iternode.where = iterator::avl_left;
		iternode.link  = node;
		node_stack.push(iternode);
		iternode.link = node->Left();
		iternode.where = iterator::avl_right;
		while(iternode.link->Right())
		{
			node_stack.push(iternode);
			iternode.link = iternode.link->Right();
		}
		node->Data(iternode.link->Data());//还要向下删除data
		return GetDt(node_stack,iternode.link);
	}
	else if(node->Right())//找最小的左子树值来
	{
		//ATLTRACE("GetDt Right\n");
		iternode.where = iterator::avl_right;
		iternode.link = node;
		node_stack.push(iternode);
		iternode.link = node->Right();
		iternode.where = iterator::avl_left;
		while(iternode.link->Left())
		{
			node_stack.push(iternode);
			iternode.link = iternode.link->Left();
		}
		node->Data(iternode.link->Data());//还要向下删除data
		return GetDt(node_stack,iternode.link);
	}
	else
	{
		return node;
	}
}
//删除
template<class T,class MEM> inline
bool CAVLTree<T,MEM>::erase(T& data)
{
	if(!_head)
	{
		return false;
	}
	CThisStack node_stack;
	CNode* tmp = _head;
	IterNode iternode;
	while(tmp)
	{
		if(*tmp == data)
		{
			data = tmp->Data();
			break;
		}
		iternode.link = tmp;
		if(*tmp < data)
		{
			tmp = tmp->Right();
			iternode.where = iterator::avl_right;
		}
		else
		{
			tmp = tmp->Left();
			iternode.where = iterator::avl_left;
		}
		node_stack.push(iternode);
	}
	if(!tmp)
		return false;
	tmp = GetDt(node_stack,tmp);
	if(_head == tmp)
	{
		_mem.Free(tmp);
		_size = 0;
		_head = NULL;
		return true;
	}
	iternode = node_stack.top();
	node_stack.pop();


	if(iternode.where == iterator::avl_left)
	{
		ATLASSERT(iternode.link->RightHei()<= 2);
		ATLASSERT(iternode.link->LeftHei() == 1);
		ATLASSERT(iternode.link->Left() == tmp);
		iternode.link->Left(NULL);
		iternode.link->LeftHei(0);
		if(iternode.link->Right())
		{
			iternode.where = iterator::avl_right;
			node_stack.push(iternode);
			iternode.link = iternode.link->Right();
		}
	}
	else
	{
		ATLASSERT(iternode.link->LeftHei()<= 2);
		ATLASSERT(iternode.link->RightHei() == 1);
		ATLASSERT(iternode.link->Right() == tmp);
		iternode.link->Right(NULL);
		iternode.link->RightHei(0);
		if(iternode.link->Left())
		{
			iternode.where = iterator::avl_left;
			node_stack.push(iternode);
			iternode.link = iternode.link->Left();
		}
	}
	node_stack.push(iternode);
	//
	_mem.Free(tmp);
	_size--;
	if(_size)
		BalanceTree(node_stack);
	else
		_head = NULL;
	return true;
}
//删除一区
template<class T,class MEM> inline
long CAVLTree<T,MEM>::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;
}
template<class T,class MEM> inline
long CAVLTree<T,MEM>::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;
}
//改变
template<class T,class MEM> inline
bool CAVLTree<T,MEM>::modify(const T& old,const T& now)
{
	T old2 = old;
	if(erase(old2))
	{
		if(!insert(now))
			ATLASSERT(0);
		return true;
	}
	return false;
}
//////////////////////////////////////////////////////////////////
///////////////////////////测试//////////////////////////
template<class T,class MEM> inline
void CAVLTree<T,MEM>::Iterator() const
{
	if(!_head)
		return;
	T pre;
	bool once(true);
	long sz(0);
	for(iterator iter = begin();iter;iter++)
	{
		if(!once)
		{
			ATLASSERT(pre < *iter);
			once = false;
		}
		ATLASSERT(iter.node()->balance() > -2 && iter.node()->balance() < 2);
		pre = *iter;
		sz++;
	}
	ATLASSERT(sz == _size);
	iter--;
	while(iter)
	{
		sz--;
		iter--;
	}
	ATLASSERT(sz == 0);
}
//////////////////////////////////////////////////////////////////
/////////////////////////////迭代器////////////////////////////

//最头一个
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::begin() const
{
	iterator iter;
	if(_head == NULL)
		return iter;
	if(!iter._nodes.New())
		return iter;
	iter._ptree = this;
	IterNode iternode;
	iternode.link = _head;
	iternode.where = iterator::avl_left;
	while(iternode.link)
	{
		iter._nodes->push(iternode);
		iternode.link = 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;
}
//最后一个
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::last() const
{
	iterator iter;
	if(_head == NULL)
		return iter;
	if(!iter._nodes.New())
		return iter;
	iter._ptree = this;
	IterNode iternode;
	iternode.link = _head;
	iternode.where = iterator::avl_right;
	while(iternode.link)
	{
		iter._nodes->push(iternode);
		iternode.link = 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;
}
//最后
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::end() const
{
	iterator iter;
	if(_head == NULL)
		return iter;
	iter._bof = false;
	iter._eof = true;
	iter._ptree = this;
	return iter;
}
//最前
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::bof() const
{
	iterator iter;
	if(_head == NULL)
		return iter;
	iter._bof = true;
	iter._eof = false;
	iter._ptree = this;
	return iter;
}