伸展樹

與AVL樹類似, 伸展樹也是二叉搜索樹的一種形式, 伸展樹無需保證時(shí)刻保持全樹的平衡,也不需要像AVL樹一樣要求記錄平衡因子的附加信息
伸展樹的提出源于信息訪問的局部性(剛被訪問過的信息有可能再次被訪問,要被訪問的元素可能位于剛訪問過的元素的附近), 就伸展樹而言,可采用剛被訪問的元素移至數(shù)據(jù)列表的前端,從而降低后續(xù)的操作時(shí)間

簡易伸展樹的最壞情況
每次使用search,將訪問后的元素移至樹根節(jié)點(diǎn), 如果采用單次zig/zag旋轉(zhuǎn)(先對(duì)該節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn),再對(duì)祖父進(jìn)行旋轉(zhuǎn),每旋轉(zhuǎn)一次,節(jié)點(diǎn)上升一層), 如果總節(jié)點(diǎn)數(shù)為n,那么總的旋轉(zhuǎn)次數(shù)將高達(dá)O(n*n), 平攤到每個(gè)節(jié)點(diǎn),復(fù)雜度(O(n))都高于AVL樹, 簡易伸展并不會(huì)改變當(dāng)前樹的拓?fù)浣Y(jié)構(gòu)
如圖:

雙層旋轉(zhuǎn)
由于單層旋轉(zhuǎn)將會(huì)造成O(n)多,高于AVL樹,就此提出改進(jìn)措施:
進(jìn)行雙層旋轉(zhuǎn), 每次的旋轉(zhuǎn)不再是從當(dāng)前節(jié)點(diǎn)的parent開始,而是從當(dāng)前節(jié)點(diǎn)的grandpa開始;先對(duì)g旋轉(zhuǎn),再對(duì)p旋轉(zhuǎn),這種旋轉(zhuǎn)方式將在zig-zig,zag-zag下展現(xiàn)效果,如圖

對(duì)比簡易伸展與雙層旋轉(zhuǎn),將會(huì)發(fā)現(xiàn)雙層旋轉(zhuǎn)每進(jìn)行一次search操作, 那么樹的高度將會(huì)折半,那么如果訪問最壞的節(jié)點(diǎn)也不會(huì)出現(xiàn)O(n)的復(fù)雜度,單次操作可在O(logn)時(shí)間內(nèi)完成, 但是如果旋轉(zhuǎn)方式為zig-zag/zag-zig, 雙層旋轉(zhuǎn)并不能改變樹高,雙層旋轉(zhuǎn)將導(dǎo)致樹的拓?fù)浣Y(jié)構(gòu)發(fā)生改變
有一種情況為:可能在最后的雙層旋轉(zhuǎn)過程中,v只有parent而沒有g(shù)randpa,但是這種情況只會(huì)在最后出現(xiàn),并且只出現(xiàn)一次,所以并不會(huì)影響樹的整體旋轉(zhuǎn)效果,因此雙層旋轉(zhuǎn)的方式是有效的

伸展樹接口定義
基于二叉平衡搜索樹類,重寫search()(查找過程也會(huì)改變樹的拓?fù)浣Y(jié)構(gòu),所以有必要進(jìn)行重寫), insert(), remove()接口
伸展樹的伸展調(diào)整算法:

template<typename T>inline void attachAsLChild(NodePosi p, NodePosi lc){p->lChild=lc;if(lc)lc->parent=p;//為p,lc建立父(左)子的關(guān)系,可能lc為null } template<typename T>inline void attachAsRChild(NodePosi p, NodePosi rc){p->rChild=rc;if(rc)rc->parent=p;//為p,lc建立父(左)子的關(guān)系,可能lc為null }template<typename T>BinNodePosi* Splay<T>::splay(BinNodePosi* v){//從v的位置開始進(jìn)行伸展操作if(!v) return null;BinNodePosi* p,g;//v的父親與祖父while((p=v->parent)&&(g=p->parent)){//自下而上進(jìn)行雙層伸展BinNodePosi* gg=g->parent;if(p->lChild==v)if(g->lChild==p){//zig-zig//忽略具體旋轉(zhuǎn)過程,直接拼接操作attachAsLChild(g,p->rChild);//將g拼接到p上attachAsLChild(p,v->rChild);//將p拼接到v上attachAsRChild(p,g);attachAsRChild(v,p);//操作同上}else{//zig-zagattachAsLChild(p,v->rChild);attachAsRChild(g,v->lChild);attachAsLChild(v,g);attachAsRChild(v,p);}else if(g->RChild==p){//zag-zagattachAsRChild(g,p->lChild);attachAsRChild(p,v->lChild);attachAsLChild(p,g);attachAsLChild(v,p);} else{//zag-zigattachAsRChild(p,v-lChild);attachAsLChild(g,v->rChild);attachAsRChild(v,g);attachAsLChild(v,p);}if(!gg) v->parent=null;//v伸展至最頂端,變?yōu)閞ootelse//曾祖父存在,直接將v作為曾祖父的左孩子或右孩子(g==gg->lChild)?attachAsLChild(gg,v):attachAsRChild(gg,v);updateHeight(g);updateHeight(p);updateHeight(v);}if(p=v->parent){//v旋轉(zhuǎn)到最后還有一個(gè)p,需要完成一次單旋if(p-lChild==v){attachAsLChild(p,v->rChild);attachAsRChild(v,p);}else {attachAsRChild(p,v->lChild);attachAsLChild(v,p);}updateHeight(p);updateHeight(v);}v->parent=null; returnv;//v已移至root位置 }

search實(shí)現(xiàn)

//在search過程中,將節(jié)點(diǎn)移動(dòng) template<typename T>BinNodePosi* Splay<T>::search(const T& e){BinNodePosi* p=searchIn(_root,e,_hot=null);//從根節(jié)點(diǎn)位置開始查找_root=splay((p?p:root));//無論查找是否成功都將返回與之對(duì)應(yīng)的那個(gè)節(jié)點(diǎn)或者相似的節(jié)點(diǎn)至_root位置return _root; }

insert實(shí)現(xiàn)

//由于查找的過程中就實(shí)現(xiàn)了將要找的相似元素移動(dòng)至_root位置,再將要插入的元素與root位置的節(jié)點(diǎn)作比較,節(jié)點(diǎn)重連實(shí)現(xiàn)插入操作 template<typename T>BinNodePosi* Splay<T>::insert(const T& e){if(!_root) {++_size; return _root= new BinNode<T>(e);}//為空樹的情況if(e==search(e)->data) return _root;//元素已存在無需插入++_size; BinNodePosi* t=_root;//創(chuàng)建新節(jié)點(diǎn)if(_root->data<e){//插入e時(shí),以roo為分界線包含root,左邊部分t變?yōu)閑的左孩子,右邊部分變?yōu)閑的右孩子t->parent=_root=BinNode<T>(e,null,t,t->rChild);//構(gòu)造e節(jié)點(diǎn),左右孩子為t,t->rChildif(t->rChild) {t->rChild->parent=_root;t->rChild=null;}//將t的rChild的parent由t改為_root,自身連接位置改為null,防止野指針}else{t->parent=_root=new BinNode<T>(e,null,t->lChild,t);if(t->lChild) {t->lChild->parent=_root;t->lChild=null;}//原理同上}updateHeight(t);//更新祖先高度return _root;//無論e是否在原樹中,返回值_root->data總是等于e }

刪除實(shí)現(xiàn)

原理與insert一致,當(dāng)進(jìn)行完search操作后,位于root位置的則是要?jiǎng)h除的元素或者是相似的元素,在root的左子樹內(nèi)查找要?jiǎng)h除元素的直接后繼succ()(表示二叉樹中序遍歷序列列表)將其替代即可完成刪除(這步操作與平衡搜索樹的remove一致),保證樹的局部性

template<typename T>bool Splay<T>::remove(const T& e){if(!_root||(e!=search(e)->data)) return false;//查找的節(jié)點(diǎn)信息未在樹中BinNodePosi* w=_root;//要?jiǎng)h除的節(jié)點(diǎn)已經(jīng)伸展至樹根位置if(!_root->lChild) {//若無左子樹_root=_root->rChild; if(_root) _root->parent=null;}else if(!_root->rChild){//無右子樹_root=_root->lChild; if(_root) _root->parent=null;}else{//左右子樹都存在BinNodePosi* lTREE=_root->lChild;lTREE->parent=null;_root->lChild=null;//將左子樹暫時(shí)切除_root=_root->rChild;_root->parent=null;search(w->data);//該查找必定失敗,但是也將右子樹中的最小節(jié)點(diǎn)伸展至root的位置//該過程也可調(diào)用直接后繼,根據(jù)中序遍歷在右子樹中查找最小節(jié)點(diǎn)_root->lChild=lTREE;lTREE->parent=_root;//將左子樹重新歸位}delete w;_size--;//釋放要?jiǎng)h除的節(jié)點(diǎn)if(_root) updateHeight(_root);//樹非空時(shí),更新高度return true; }

總結(jié):伸展樹復(fù)雜度與AVL樹一致O(logn),局部性較強(qiáng),平均效率較高, 但是針對(duì)最壞情況下的單次操作時(shí)任需要O(n), 不適用于對(duì)效率敏感的場所

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的伸展树学习总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。