赞
踩
数据项之间,依照各自的关键码彼此区分,关键码之间支持大小比较和相等比对,那么关键码又如何来表示呢?用entry词条
template <class K,class V> struct Entry{
K key;V value;//关键码,数值
Entry (K k=K(),V v=V()):key(k),value(v){};//默认构造函数
Entry (Entry<K,V> const & e):key(e.key),value(e.value){};//克隆
bool operator<(Entry<K,V> const & e){return key<e.key;}
bool operator>(Entry<K,V> const & e){return key>e.key;}
bool operator==(Entry<K,V> const & e){return key==e.key;}
bool operator!=(Entry<K,V> const & e){return key!=e.key;}
};
有序性(微观特征):注意老师说为简洁起见禁止了重复词条,但是应用不自然
单调性(宏观特征)
template <class T> class BST:public BinTree<T>{//
public:
virtual BinNodePosi(T) & search(const T &);//注意这里的语义,返回的是一个引用
virtual BinNodePosi(T) insert(const T &);
virtual bool remove(const T &);
protected:
BinNodePosi(T) _hot;//命中节点的父亲
BinNodePosi(T) connect34(//3+4重构
BinNodePosi(T),BinNodePosi(T),BinNodePosi(T),
BinNodePosi(T),BinNodePosi(T),BinNodePosi(T),BinNodePosi(T));
BinNodePosi(T) rotateAt(BinNodePosi(T));//旋转调整
};
思路:
实现:
接口:static BinNodePosi(T) & searchIn(BinNodePosi(T) & v,const T & e,BinNodePosi(T) & hot);
注意这里的语义!返回值总是等效的指向命中节点,而_hot总是指向命中节点的父亲
template <class T>
BinNodePosi(T)& BST<T>::search(const T & e){
return searchIn(this->_root,e,_hot=0);//从根节点启动查找
}
template <class T>//典型的尾递归
BinNodePosi(T) & BST<T>::searchIn(BinNodePosi(T) & v,const T & e,BinNodePosi(T) & hot){
if(!v||(e==v->data)) return v;//如果v不存在,或者成功找到了直接它,不存在则返回一个空的引用
hot=v;//先记下当前节点
return searchIn(e < v->data? v->lChild : v->rChild,e,hot);
}
思路:
实现:
template <class T>
BinNodePosi(T) BST<T>::insert(const T & e){
BinNodePosi(T) & x=search(e);
if(!x){//由于禁止了重复元素,所以只在查找失败时插入
x=new BinNode<T>(e,_hot);//以_hot为父节点
this->size++;
updateHeightAbove(x);
}
return x;
}
大体框架:
template <class T>
bool BST<T>::remove(const T & e){
BinNodePosi(T) & x=search(e);
removeAt(x,_hot);//分两大类情况
this->_size--;
updateHeightAbove(_hot);
return true;
}
可以看到,算法的主体部分是removeAt(x,_hot),这里分成两种情况讨论
第一种情况:
第二种情况: 这里可以看成中序序列就很好理解了
实现:
接口: static BinNodePosi(T) removeAt(BinNodePosi(T) & x,BinNodePosi(T) & hot);
template <class T> BinNodePosi(T) BST<T>::removeAt(BinNodePosi(T) & x,BinNodePosi(T) & hot){ BinNodePosi(T) w=x;//实际被摘除的节点 BinNodePosi(T) succ=0;//实际被摘除的节点的接替者 if(!HasLChild(*x)) succ=x=x->rChild; //先判断有没有左孩子!,为空 else if(!HasRChild(*x)) succ=x=x->lChild; //右孩子为空 else{ w=w->succ(); swap(x->data,w->data); BinNodePosi(T) u=w->parent; (u==x? u->rChild:u->lchild)=succ=w->rChild; //判等条件,相等时说明w的父亲和要删除的节点是同一个 } hot=w->parent;//记录实际被删除的节点 if(succ) succ->parent=hot;//将被删除的节点的接替者与hot相连 release(w->data);//释放被删除节点 release(w); return succ;//返回接替者 }
BST的查找删除和插入操作在最坏的情况下,均线性正比于高度O(h),若高度不能被有效控制,则性能会大大降低
如何等价转换呢?->旋转调整
如何证明其是适度平衡的?
这里定义宏的时候总是出错,后来把老师的代码后注释换个位置就好了
#define Balanced(x)\
(stature((x).lChild)==stature((x).rChild))//左右子树的高度完全相等,理想平衡
#define BalFac(x)\
(stature((x).lChild)-stature((x).rChild)) //平衡因子
#define AvlBalanced(x)\
((-2<BalFac((x)))&&(BalFac((x))<2))//AVL平衡条件
template <class T> class AVL:public BST<T>{
public:
BinNodePosi(T) insert(const T &);
bool remove(const T &);
};
单旋:
双旋:
实现:
template <class T> BinNodePosi(T) AVL<T>::insert(const T & e){ BinNodePosi(T) & x=search(e); if(x) return x;//目标存在,返回目标,否则 BinNodePosi(T) xx=x=new BinNode<T>(e,this->_hot);//创建新节点 this->_size++; for(BinNodePosi(T) g=this->_hot;g;g=g->parent){ if(!AvlBalanced(*g)){//一旦发现g失衡,则通过调整恢复平衡,该祖先必定是所有失衡祖先的最低者 FromParentTo(*g)=rotateAt(tallerChild(tallerChild(g)));//返回当前节点父亲节点的指针域 break; } else{//在依旧平衡的祖先处,只需要简单的 updateHeght(g);//更新高度即可 } } return xx; }
单旋:
双旋:
实现:
template <class T>
bool AVL<T>::remove(const T & e){
BinNodePosi(T) & x=search(x);
removeAt(x,this->_hot);
this->_size--;
if(!x) return false;
for(BinNodePosi(T) g=this->_hot;g;g=g->parent){
if(!AdlBanced(*g)){//一旦发现失衡
g=FromParentTo(*g)=rotateAt(tallerChild(tallerChild(g)));
}
updateHeight(g);//更新高度
}
return true;
}
(类似于拆除魔方,重新组装,而不是用旋转还原)
实现:
template <class T>
BinNodePosi(T) BST<T>::connect34(//3+4重构
BinNodePosi(T) a,BinNodePosi(T) b,BinNodePosi(T) c,
BinNodePosi(T) T0,BinNodePosi(T) T1,BinNodePosi(T) T2,BinNodePosi(T) T3){
a->lChild=T0;if(T0) T0->parent=a;
a->rChild=T1;if(T1) T1->parent=a;updateHeight(a);
c->lChild=T2;if(T2) T2->parent=c;
c->rChild=T3;if(T3) T3->parent=c;updateHeight(b);
b->lChild=a;a->parent=b;
b->rChild=c;c->parent=b;updateHeight(c);
return b;
}
基于3+4重构实现rotateAt(关于zigzag的命名这里存疑,上面讲的和这里的注释是反的)
template <class T> BinNodePosi(T) BST<T>::rotateAt(BinNodePosi(T) v){ BinNodePosi(T) p=v->parent,g=p->parent;//父亲,祖父 if(IsLChild(*p))//zig if(IsLChild(*v)){//zigzig p->parent=g->parent;//向上联接 return connect34(v,p,g,v->lChild,v->rChild,p->rChild,g->rChild); } else{//zigzag v->parent=g->parent;//向上联接 return connect34(p,v,g,p->lChild,v->lChild,v->rChild,g->rChild); } else{ if(IsLChild(*v)){//zagzig v->parent=g->parent;//向上联接 return connect34(g,v,p,g->lChild,v->lChild,v->rChild,p->rChild); } else{//zagzag p->parent=g->parent;//向上联接 return connect34(g,p,v,g->lChild,p->lChild,v->rChild,v->rChild); } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。