📄 carrayavltree.h
字号:
#pragma once
#include "ArrayAVLTreeIterator.h"
#define CARRAYAVLTREE_TEMPLATE template<class T> inline
#define CARRAYAVLTREE_TEMPLATE_HEAD template<class T = long>
#define ARRAYSIZE BLOCKDATASIZE
#define CARRAYAVLTREE CArrayAVLTree<T>
CARRAYAVLTREE_TEMPLATE_HEAD
class CArrayAVLTree
{
friend class ArrayAVLTreeIterator<T>;
protected:
typedef MyArrayAlloc<T> CArrayAlloc;
typedef ArrayAVLTreeIterator<T>::CNode CNode;
typedef ArrayAVLTreeIterator<T>::IteratorStatus IteratorStatus;
typedef ArrayAVLTreeIterator<T>::IterNode IterNode;
typedef ArrayAVLTreeIterator<T>::CThisStack CThisStack;
public:
typedef ArrayAVLTreeIterator<T> iterator;
protected:
short _size;//大小
short _head;//头
CArrayAlloc _nodeUsed;//内存使用
CNode _node[ARRAYSIZE];//节点内存
long _reserve;//为特殊用处
public:
CArrayAVLTree(void);
//复制
long copy(const CARRAYAVLTREE& tree);
CArrayAVLTree(const CARRAYAVLTREE& tree);
CArrayAVLTree& operator =(const CARRAYAVLTREE& tree);
//清除
void clear();
~CArrayAVLTree(void);
protected://存储分配
short New();
void Delete(short sb);
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(CARRAYAVLTREE& tree);
//合并
long marge(CARRAYAVLTREE& tree);
//分裂
long onetotwo(CARRAYAVLTREE& tree);
//专用于B树的分裂
T split(CARRAYAVLTREE& tree);
//专用于B树的合并
long marge(CARRAYAVLTREE& tree,T mid);
//专用于B树的平衡
T balance(CARRAYAVLTREE& tree,T mid);
public://作为B树的未连接
long reserve() const;
void reserve(long reserve);
protected:
// 查找替代者
short GetDt(CThisStack& node_stack,short node);
protected://平衡（使用旋转）
void BalanceTree(CThisStack& nodes);
short LLTurn(short& X);
short LRTurn(short& X);
short RRTurn(short& X);
short RLTurn(short& X);
public:
//数据数量
long size() const;
//高度
long height() const;
//平衡因子
long balance() const;
//块大小
static long maxsize();
public:
iterator begin() const;
iterator last() const;
iterator end() const;
iterator bof() const;
void Iterator() const;
};
/////////////////////////////构造与析构///////////////////////////
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::CArrayAVLTree(void)
: _head(ZEROLINK)
, _size(0)
, _reserve(ZEROLINK)
{
}
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::CArrayAVLTree(const CARRAYAVLTREE& tree)
{
copy(tree);
}
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE& CARRAYAVLTREE::operator =(const CARRAYAVLTREE& tree)
{
copy(tree);
return *this;
}
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::copy(const CARRAYAVLTREE& tree)
{
ATLASSERT(&tree != this);
_head = tree._head;
_size = tree._size;
_reserve = tree._reserve;
memcpy(&_nodeUsed,&tree._nodeUsed,sizeof(_nodeUsed));
memcpy(_node,tree._node,sizeof(_node));
return _size;
}
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::~CArrayAVLTree(void)
{
//因为要存盘，所在没有工作
//clear();
}
//清零
CARRAYAVLTREE_TEMPLATE
void CARRAYAVLTREE::clear()
{
//清除分配器就行了
_nodeUsed.clear();
_head = ZEROLINK;
}
/////////////////////////////////////////////////////////////////
////////////////存储分配///////////////////////////
CARRAYAVLTREE_TEMPLATE
short CARRAYAVLTREE::New()
{
return _nodeUsed.alloc();
}
CARRAYAVLTREE_TEMPLATE
void CARRAYAVLTREE::Delete(short sb)
{
if(sb > ZEROLINK && sb < ARRAYSIZE)
{
_nodeUsed.free(sb);
}
}
/////////////////////////////////////////////////////////////////
//////////////////////属性/////////////////////
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::size() const
{
return _size;
}
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::height() const
{
if(_head > ZEROLINK)
return _node[_head].Height();
else
return 0;
}
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::balance() const
{
if(_head > ZEROLINK)
return _node[_head].balance();
else
return 0;
}
//块大小
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::maxsize()
{
long si = ARRAYSIZE;
return ARRAYSIZE;
}
/////////////////////////////////////////////////////////////////
//////////////////查找///////////////////
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::find(T& data) const
{
iterator iter;
if(_head == ZEROLINK)
return iter;
if(!iter._nodes.New())
return iter;
IterNode iternode;
iter._ptree = this;
short sb = _head;
while(sb > ZEROLINK)
{
iternode.link = sb;
if(_node[sb] == data)
{
iternode.where = iterator::avl_now;
iter._bof = iter._eof = false;
iter._nodes->push(iternode);
data = _node[sb].Data();
return iter;
}
if(_node[sb] < data)
{
sb = _node[sb].Right();
iternode.where = iterator::avl_right;
}
else
{
sb = _node[sb].Left();
iternode.where = iterator::avl_left;
}
iter._nodes->push(iternode);
}
iter.clear();
return iter;
}
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::fina_all(const T& data) const
{
iterator iter;
if(_head == ZEROLINK)
return iter;
if(!iter._nodes.New())
return iter;
IterNode iternode;
iter._ptree = this;
short sb = _head;
while(sb > ZEROLINK)
{
iternode.link = sb;
if(_node[sb] == data)
{
iter._bof = false;
iter._eof = false;
iternode.where = iterator::avl_now;
iter._nodes->push(iternode);
break;
}
if(_node[sb] < data)
{
iter._bof = false;
sb = _node[sb].Right();
iternode.where = iterator::avl_right;
}
else
{
iter._eof = false;
sb = _node[sb].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;
}
//查找大于
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::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;
}
//查找大等于
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::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;
}
//查找小于
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::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;
}
//查找小等于
CARRAYAVLTREE_TEMPLATE
CARRAYAVLTREE::iterator CARRAYAVLTREE::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;
}
////////////////////////////////////////////////////////////////
/////////////////////////B-树专用//////////////////////
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::reserve() const
{
return _reserve;
}
CARRAYAVLTREE_TEMPLATE
void CARRAYAVLTREE::reserve(long reserve)
{
_reserve = reserve;
}
//专用于B树的分裂--自己留大的,别人给小的
CARRAYAVLTREE_TEMPLATE
T CARRAYAVLTREE::split(CARRAYAVLTREE& tree)
{
T t = _node[_head].Data();
short head = _head;
tree = *this;
_head = _node[head].Right();
tree._head = _node[head].Left();
tree._reserve = t.link;
tree._nodeUsed.free(head);
_nodeUsed.free(head);
iterator iter;
iter = begin();
long sz = _size;
tree._size = _size = 0;
for(;iter;iter++)
{
tree._nodeUsed.free(iter.nowsb());
_size++;
}
iter = tree.begin();
for(;iter; iter++)
{
_nodeUsed.free(iter.nowsb());
tree._size++;
}
return t;
}
//专用于B树的分裂--自己留大的,别人给小的
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::onetotwo(CARRAYAVLTREE& tree)
{
T head = _node[_head].Data();
long head = _head;
memcpy(tree._node,_node,sizeof(_node));
_head = _node[head].Right();
tree._head = _node[head].Left();
tree._reserve = t.link;
tree._nodeUsed[head] = 0;
_nodeUsed[head] = 0;
iterator iter;
iter = begin();
long sz = _size;
tree._size = _size = 0;
for(;iter;iter++)
{
_nodeUsed[iter] = 1;
tree._nodeUsed[iter] = 0;
_size++;
}
iter = tree.begin();
for(;iter; iter++)
{
tree._nodeUsed[iter] = 1;
_nodeUsed[iter] = 0;
tree._size++;
}
insert(head);
return _size;
}
//专用于B树的合并
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::marge(CARRAYAVLTREE& tree,T mid)
{
if(_node[_head] < mid)
{
mid.link = _reserve;
_reserve = tree._reserve;
}
else
{
mid.link = tree._reserve;
}
insert(mid);
iterator iter = tree.begin();
for(;iter; iter++)
{
insert(*iter);
}
return _size;
}
//专用于B树的合并
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::marge(CARRAYAVLTREE& tree)
{
if(_node[_head] < t)
{
mid.link = _reserve;
_reserve = tree._reserve;
}
else
{
mid.link = tree._reserve;
}
iterator iter = tree.begin();
for(;iter; iter++)
{
insert(*iter);
}
return _size;
}
//专用于B树的平衡
CARRAYAVLTREE_TEMPLATE
T CARRAYAVLTREE::balance(CARRAYAVLTREE& tree,T mid)
{
//一定保证此小tree大
if(_node[_head] > tree._node[tree._head])
return tree.balance(*this,mid);
long ca = abs((_size - tree._size)) / 2;
iterator iter;
long i;
T* era = new T[ca + 1];
era[0] = mid;
era[0].link = _reserve;
T data;
if(_size > tree._size)
{
iter = last();
for(i = 1;i < ca;i++,iter--)
{
era[i] = *iter;
}
data = *iter;
mid = data;
_reserve = iter->link;
erase(data);
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;
}
data = *iter;
mid = data;
_reserve = iter->link;
tree.erase(data);
for(i = 0;i < ca;i++)
{
tree.erase(era[i]);
insert(era[i]);
}
}
//this->iter(true);
//ATLTRACE("%d\n",t.data);
//tree.iter(true);
delete[] era;
return mid;
}
//专用于B树的平衡
CARRAYAVLTREE_TEMPLATE
long CARRAYAVLTREE::balance(CARRAYAVLTREE& 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++)
{
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -