avltree.h

本人自己的作品

#pragma once
#include <stack>
#include <vector>
#include <bitset>
#include "AVLNode.h"
#include "SmartPtr.h"
template<class T,class MEM = CAVLNodeAlloctor<T> > class CAVLTree;
template<class T>
class AVLIterator
{
public:
	typedef CAVLNode<T> CNode;
	enum avltreelink {avl_none = -1,avl_left,avl_now,avl_right};
	struct IterNode
	{
		CNode* link;
		avltreelink where;//0左子树，1当前，2左子树
		bool operator ==(const IterNode& node) const
		{
			return link == node.link && where == node.where;
		}
		IterNode(): link(NULL) , where(avl_none){}
		IterNode(const IterNode& node)
			: link(node.link) , where(node.where){}
	};
	typedef std::stack<IterNode> CThisStack;
	typedef CAVLTree<T> _Tree;
	friend class _Tree;
protected:
	const _Tree* _ptree;
	bool _eof;
	bool _bof;
	CSmartPtr<CThisStack> _nodes;
public:
	AVLIterator()
		: _ptree(NULL)
		, _eof(true)
		, _bof(true)
	{
	}
	AVLIterator(const AVLIterator& iter)
		: _ptree(iter._ptree)
		, _eof(iter._eof)
		, _bof(iter._bof)
		, _nodes(iter._nodes)
	{
	}
	AVLIterator& operator =(const AVLIterator& iter)
	{
		_nodes = iter._nodes;
		_ptree = iter._ptree;
		_eof = iter._eof;
		_bof = iter._bof;
		ATLASSERT(!_nodes || _nodes->top().where == avl_now);
		return *this;
	}
	bool IsNull() const
	{
		return !_ptree || !_nodes || _nodes->empty();
	}
	operator bool() const
	{
		return !IsNull();
	}
	bool bof()  const
	{
		return _bof;
	}
	bool eof() const
	{
		return _eof;
	}
	bool operator !=(const AVLIterator& iter) const
	{
		return !(operator==(iter));
	}
	bool operator ==(const AVLIterator& iter)const
	{
		if(IsNull() && iter.IsNull())
			return true;
		if(IsNull() || iter.IsNull())
			return false;
		if(_nodes->empty() && iter._nodes->empty())
			return true;
		if(_nodes->empty() || iter._nodes->empty())
			return false;
		if(_ptree != iter._ptree)
			return false;
		if(_ptree == iter._ptree && _bof == iter._bof && _eof == iter._eof)
			return true;
		ATLASSERT(!_nodes || _nodes->top().where == avl_now);
		ATLASSERT(!iter._nodes || iter._nodes->top().where == avl_now);
		if(_nodes->top() == iter._nodes->top())
			return true;
		return false;
	}
	AVLIterator& operator ++()
	{
		//栈为空？
		if(IsNull())
		{
			if(_ptree && _bof && !_eof)
			{
				operator=(_ptree->begin());
			}
			else
			{
				//ATLTRACE("已迭代到最后，无法前进！\n"));
				ATLASSERT(0);
			}
			return *this;
		}
		IterNode iternode;
		while(!_nodes->empty())
		{
			iternode = _nodes->top();
			if(iternode.where == avl_left)//还没到过，正好使用
			{
				break;
			}
			_nodes->pop();
			if(iternode.where == avl_now)//用过，应到右子树的最左叶
			{
				iternode.where = avl_right;
				if(iternode.link->Right())//有最左叶
				{
					_nodes->push(iternode);
					iternode.link  = iternode.link->Right();
					iternode.where = avl_left;
					_nodes->push(iternode);
					while(iternode.link->Left())
					{
						iternode.where = avl_left;
						iternode.link = iternode.link->Left();
						_nodes->push(iternode);
					}
					break;
				}
			}//没有，等于看过右子树
		}
		if(!_nodes->empty())
		{//还有东西
			iternode = _nodes->top();
			_nodes->pop();
			iternode.where = avl_now;
			_nodes->push(iternode);
		}
		else
		{
			_nodes.Destory();
			_eof = true;
			_bof = false;
		}
		return *this;
	}
	AVLIterator& operator ++(int i)
	{
		return operator ++();
	}
	//反回来
	AVLIterator& operator --()
	{
		if(IsNull())
		{
			if(_ptree && !_bof && _eof)
			{
				operator=(_ptree->last());
			}
			else
			{
				ATLASSERT(0);
				//ATLTRACE("已迭代到最前，无法后退！\n"));
			}
			return *this;
		}
		IterNode iternode;
		while(!_nodes->empty())
		{
			iternode = _nodes->top();
			if(iternode.where == avl_right)//还没到过，正好使用
			{
				break;
			}
			_nodes->pop();
			if(iternode.where == avl_now)//用过，应到左子树的最右叶
			{
				iternode.where = avl_left;
				if(iternode.link->Left())//有最左叶
				{
					_nodes->push(iternode);
					iternode.where = avl_right;
					iternode.link = iternode.link->Left();
					_nodes->push(iternode);
					while(iternode.link->Right())
					{
						iternode.where = avl_right;
						iternode.link = iternode.link->Right();
						_nodes->push(iternode);
					}
					break;
				}
			}//没有，等于看过右子树
		}
		if(!_nodes->empty())
		{//还有东西
			iternode = _nodes->top();
			_nodes->pop();
			iternode.where = avl_now;
			_nodes->push(iternode);
		}
		else
		{
			_nodes.Destory();
			_eof = false;
			_bof = true;
		}
		return *this;
	}
	AVLIterator& operator --(int i)
	{
		return operator --();
	}
protected:
	CNode* node() const
	{
		return _nodes->top().link;
	}
public:
	T& Data()
	{
		return _nodes->top().link->GetData();
	}
	const T& operator *() const
	{
		return _nodes->top().link->Data();
	}
	const T* operator ->() const
	{
		return &_nodes->top().link->Data();
	}
	AVLIterator& clear()
	{
		_ptree = NULL;
		_eof = true;
		_bof = true;
		_nodes.Destory();
		return *this;
	}
};
template<class T,class MEM = CAVLNodeAlloctor<T> >
class CAVLTree
{
public:
	typedef AVLIterator<T> iterator;
	typedef AVLIterator<T>::CThisStack CThisStack;
	typedef AVLIterator<T>::CNode CNode;
	typedef AVLIterator<T>::IterNode IterNode;
	typedef AVLIterator<T>::avltreelink avltreelink;
	typedef MEM CAlloc;

protected:
	long	_size;//大小
	CNode*	_head;//头
	CAlloc	_mem;//内存使用
public:
	CAVLTree(void);
	//复制
	long copy(const CAVLTree<T,MEM>& tree);
	long copy2(CAVLTree<T,MEM>& tree);
	CAVLTree(const CAVLTree<T,MEM>& tree);
	CAVLTree& operator =(const CAVLTree<T,MEM>& tree);
	//清除
	void clear();
	~CAVLTree(void);
public:
	//查找
	iterator find(T& data) const;
	//查找大等于
	iterator find_lower(const T& data) const;
	//查找大于
	iterator find_upper(const T& data) const;
	//查找小等于
	iterator find_front_lower(const T& data) const;
	//查找小于
	iterator find_front_upper(const T& data) const;
protected:
	//查找近似区域
	iterator fina_all(const T& data) const;
public://插入
	bool insert(const T& data);
	long insertrange(T* first,long size);
	//修改已存在数据的非索引的值
	bool modify(const T& data);
	//删除
	bool erase(T& data);
	long eraserange(T& first,T& last);
	long eraserange(T* first,long size);
	//替换
	bool modify(const T& old,const T& now);
public:
	//平衡
	long balance(CAVLTree& tree);
	//合并
	long marge(CAVLTree& tree);
	//分裂
	long onetotwo(CAVLTree& tree);
protected:
	// 查找替代者
	CNode* GetDt(CThisStack& node_stack,CNode* node);
protected://平衡（使用旋转）
	void BalanceTree(CThisStack& nodes);
	CNode* LLTurn(CNode*& X);
	CNode* LRTurn(CNode*& X);
	CNode* RRTurn(CNode*& X);
	CNode* RLTurn(CNode*& X);
public:
	//数据数量
	long size() const;
	//高度
	long height() const;
	//平衡因子
	long balance() const;
public:
	iterator begin() const;
	iterator last() const;
	iterator end() const;
	iterator bof() const;
	void Iterator() const;
public://取得内存分配器
	CAlloc&	GetAlloc()
	{
		return _mem;	
	}
};
/////////////////////////////构造与析构///////////////////////////
template<class T,class MEM> inline
CAVLTree<T,MEM>::CAVLTree(void)
: _head(NULL)
, _size(0)
{
}

template<class T,class MEM> inline
CAVLTree<T,MEM>::CAVLTree(const CAVLTree<T,MEM>& tree)
: _head(NULL)
, _size(0)
{
	copy(tree);
}

template<class T,class MEM> inline
CAVLTree<T,MEM>& CAVLTree<T,MEM>::operator =(const CAVLTree<T,MEM>& tree)
{
	copy(tree);
	return *this;
}

template<class T,class MEM> inline
long CAVLTree<T,MEM>::copy2(CAVLTree<T,MEM>& tree)
{
	clear();
	_head = tree._head;
	_size = tree._size;
	tree._head = 0;
	tree._size = 0;
	//ATLTRACE("没有完成自由内存AVL树的复制\n"));
	return _size;
}
template<class T,class MEM> inline
long CAVLTree<T,MEM>::copy(const CAVLTree<T,MEM>& tree)
{
	ATLASSERT(&tree != this);
	clear();
	iterator iter = tree.begin();
	for(;iter;iter++)
		insert(*iter);
	return _size;
}
template<class T,class MEM> inline
CAVLTree<T,MEM>::~CAVLTree(void)
{
	clear();
}
//清零
template<class T,class MEM> inline
void CAVLTree<T,MEM>::clear()
{
	iterator iter = begin();
	//栈为空？
	if(iter.IsNull())
	{
		return;
	}
	IterNode iternode;
	while(!iter._nodes->empty())
	{
		iternode = iter._nodes->top();
		if(iternode.where == iterator::avl_now)//用过，应到右子树的最左叶
		{
			iter._nodes->pop();
			if(iternode.link->Right())//有最左叶
			{
				iternode.where = iterator::avl_right;
				iter._nodes->push(iternode);
				iternode.link  = iternode.link->Right();
				iternode.where = iterator::avl_left;
				iter._nodes->push(iternode);
				while(iternode.link->Left())
				{
					iternode.where = iterator::avl_left;
					iternode.link = iternode.link->Left();
					iter._nodes->push(iternode);
				}
			}
			else
			{
				_mem.Free(iternode.link);
				continue;
			}
		}//没有，等于看过右子树
		else if(iternode.where == iterator::avl_right)
		{
			iter._nodes->pop();
			_mem.Free(iternode.link);
			continue;
		}
		if(!iter._nodes->empty())
		{//还有东西
			iternode = iter._nodes->top();
			iter._nodes->pop();
			iternode.where = iterator::avl_now;
			iter._nodes->push(iternode);
		}
	}
	_head = NULL;
	_size = 0;
}
/////////////////////////////////////////////////////////////////
//////////////////////属性/////////////////////
template<class T,class MEM> inline
long CAVLTree<T,MEM>::size() const
{
	return _size;
}
template<class T,class MEM> inline
long CAVLTree<T,MEM>::height() const
{
	if(_head)
		return _head->Height();
	else 
		return 0;
}
template<class T,class MEM> inline
long CAVLTree<T,MEM>::balance() const
{
	if(_head)
		return _head->balance();
	else 
		return 0;
}
/////////////////////////////////////////////////////////////////
//////////////////查找///////////////////
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::find(T& data) const
{
	iterator iter;
	if(_head == NULL)
		return iter;
	if(!iter._nodes.New())
		return iter;
	IterNode iternode;
	iter._ptree = this;
	CNode* node = _head;
	while(node)
	{
		iternode.link = node;
		if(*node == data)
		{
			iternode.where = iterator::avl_now;
			iter._bof = iter._eof = false;
			iter._nodes->push(iternode);
			data = node->Data();
			return iter;
		}
		if(*node < data)
		{
			node = node->Right();
			iternode.where = iterator::avl_right;
		}
		else
		{
			node = node->Left();
			iternode.where = iterator::avl_left;
		}
		iter._nodes->push(iternode);
	}
	iter.clear();
	return iter;
}
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::fina_all(const T& data) const
{
	iterator iter;
	if(_head == NULL)
		return iter;
	if(!iter._nodes.New())
		return iter;
	IterNode iternode;
	iter._ptree = this;
	CNode* node = _head;
	while(node)
	{
		iternode.link = node;
		if(*node == data)
		{
			iter._bof = iter._eof = false;
			iternode.where = iterator::avl_now;
			iter._bof = iter._eof = false;
			iter._nodes->push(iternode);
			return iter;
		}
		if(*node < data)
		{
			iter._bof = false;
			node = node->Right();
			iternode.where = iterator::avl_right;
		}
		else
		{
			iter._eof = false;
			node = node->Left();
			iternode.where = iterator::avl_left;
		}
		iter._nodes->push(iternode);
	}
	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>::find_upper(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.eof() && !iter.IsNull() && !(data < *iter))
		iter++;
	if(iter.eof())
		iter.clear();
	return iter;
}
//查找大等于
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::find_lower(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.eof() && !iter.IsNull() && *iter < data)
		iter++;
	if(iter.eof())
		iter.clear();
	return iter;
}
//查找小于
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::find_front_upper(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.bof() && !iter.IsNull() && !(*iter < data))
		iter--;
	if(iter.bof())
		iter.clear();
	return iter;
}
//查找小等于
template<class T,class MEM> inline
CAVLTree<T,MEM>::iterator CAVLTree<T,MEM>::find_front_lower(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.bof() && !iter.IsNull() && data < *iter)
		iter--;
	if(iter.bof())
		iter.clear();
	return iter;
}
////////////////////////////////////////////////////////////////