参考博客: https://blog.csdn.net/hellochenlu/article/details/53022709
参考博客: https://blog.csdn.net/amoscykl/article/details/81589827

本章问题

1.splay逐层伸展到根和双层伸展有什么区别呢？

假设节点的个数为n，则旋转操作的总次数的为(n-1)+{(n-1)+(n-2)+(n-3)+…+1}=(n²+n-2)/2= Ω \Omega Ω(n²)
逐层伸展，对于规模为任意n的伸展树，只要按照关键码单调的次序，周期性的进行反复的查找，则无论总的访问次数m>>n有多大，就分摊的意义而言，每次访问都需要 Ω \Omega Ω(n)的时间
双层伸展优点
折叠效果：一旦访问坏节点，对应路径的长度将随即减半。
最坏情况不致持续发生！
单趟伸展操作，分摊O(logn)时间！

2.splay为什么要伸展到根，这样做有什么好处

因为数据局部性原理，这样可以加快后续的操作
数据局部性原理:
1.刚刚被访问的节点，即有可能在不久之后再次被访问到
2.将被访问的下一节点，极有可能就处于不久的之前被访问过的某个节点的附近

3.Splay双层伸展的具体描述

参考博客：https://blog.csdn.net/hellochenlu/article/details/53022709

双层伸展
构思精髓：向上追溯两层，而非一层
反复考察祖孙三代：g = parent§，p = parent(v)，v
根据它们的相对位置，经两次旋转使得 v上升两层，成为（子）树根

节点v的位置的四种可能性

zig-zag / zag-zig
与AVL树双旋完全等效
与逐层伸展别无二致。

颠倒次序后，局部的细微差异，将彻底地改变整体…

折叠效果：一旦访问坏节点，对应路径的长度将随即减半。
最坏情况不致持续发生！
单趟伸展操作，分摊O(logn)时间！

要是v只有父亲，没有祖父呢？
此时必有parent(v) == root(T)，且
每轮调整中，这种情况至多（在最后）出现一次
视具体形态，做单词旋转：zig®或者zag®

4.Splay树中查找算法的作用

将最后一个被访问的节点伸展至根，此时仍然还是二叉搜索树，此时仍满足特点
是一棵空树或具有以下几种性质的树:
1.若左子树不空，则左子树上所有结点的值均小于它的根结点的值
2.若右子树不空，则右子树上所有结点的值均大于它的根结点的值
3.左、右子树也分别为二叉排序树
4.没有权值相等的结点。

5.Splay中插入算法怎样完成局部重构

在查找接口Splay::search()已集成了splay()伸展功能,故查找返回后,树根节点要么等于查找目标(查找成功),要么就是_hot,而且恰为拟插入节点的直接前驱或直接后继(查找失败)
如上图所示,为将关键码e插至伸展树T中,首先调用伸展树查找接口Splay::search(e),查找该关键码(图(a))。于是,其中最后被访问的节点t,将通过伸展被提升为树根,其左、右子树分别记作T L 和T R (图(b))。
接下来,根据e与t的大小关系(不妨排除二者相等的情况),以t为界将T分裂为两棵子树。比如,不失一般性地设e大于t。于是,可切断t与其右孩子之间的联系(图©),再将以e为关键码的新节点v作为树根,并以t作为其左孩子,以T R 作为其右子树(图(d))。
v小于t的情况与此完全对称。

6.Splay删除节点时若左右子树都存在，为什么要暂时切断左子树

为从伸展树中删除节点,固然也可以调用二叉搜索树标准的节点删除算法BST::remove(),再通过双层伸展,将该节点此前的父节点提升至树根。然而,同样鉴于Splay::search()已集成了splay()伸展功能,且在成功返回后,树根节点恰好就是待删除节点。因此,亦不妨改用如下方法实现Splay::remove()接口。

如图所示,为从伸展树T中删除关键码为e的节点,首先亦调用接口Splay::search(e),查找该关键码,且不妨设命中节点为v(图(a))。于是,v将随即通过伸展被提升为树根,其左、右子树分别记作T L 和T R (图(b))。接下来,将v摘除(图©)。然后,在T R 中再次查找关键码e。尽管这一查找注定失败,却可以将T R 中的最小节点m,伸展提升为该子树的根。
得益于二叉搜索树的顺序性,此时节点m的左子树必然为空;同时,T L 中所有节点都应小于m(图(d))。于是,只需将T L 作为左子树与m相互联接,即可得到一棵完整的二叉搜索树(图(e))。如此不仅删除了v,而且既然新树根m在原树中是v的直接后继,故数据局部性也得到了利用。

7.3.1 Splay的ADT接口

操作	功能
splay (BinNodePosi(T) v)	将节点伸展到根
search( const T& e )	查找节点
insert ( const T& e )	插入节点
remove( const T& e )	删除节点

7.3.2 Splay的类模板

#include "BST.h"
#include <iostream>
template <typename T> class Splay : public BST<T> {
    protected:
        BinNodePosi(T) splay (BinNodePosi(T) v);//将节点伸展到根
    public:
        BinNodePosi(T) & search( const T& e );//查找
        BinNodePosi(T) insert( const T& e );//插入
        bool remove ( const T& e );//删除
};

7.3.4 Splay的伸展算法

template <typename NodePosi> inline
void attachAsLChild ( NodePosi p, NodePosi lc ) { p->lc = lc; if(lc) lc->parent = p; }
//节点*p与*lc建立父（左）子关系
template <typename NodePosi> inline
void attachAsRChild ( NodePosi p, NodePosi rc ) { p->rc = rc; if(rc) rc->parent = p; }
//节点*p与*rc建立父（右）子关系

//伸展算法的实现
template <typename T>
BinNodePosi(T) Splay<T>::splay ( BinNodePosi(T) v ){
    if( !v ) return nullptr; BinNodePosi(T) p; BinNodePosi(T) g;
    while( ( p = v->parent ) && ( g = p->parent )){//祖父与父亲都安在，双层伸展
        BinNodePosi(T) gg = g->parent;
        if( v->data < p->data)//如果节点v是p的左子树
            if( p->data < g->data){//zig-zig 
                attachAsLChild ( g, p->rc ); attachAsLChild( p, v->rc );
                attachAsRChild ( p, g ); attachAsRChild( v, p );
                std::cout << "here0" << p->data << g->data<< std::endl;
            }else{//zig-zag
                std::cout << "here1" <<std::endl;
                attachAsLChild ( p, v->rc ); attachAsRChild( g, v->lc );
                attachAsLChild ( v, g ); attachAsRChild( v, p );
            }
        else 
            if( p->data >= g->data){//zag-zag
                std::cout << "here2" <<std::endl;
                attachAsRChild ( g, p->lc ); attachAsRChild( p, v->lc );
                attachAsLChild ( p, g ); attachAsLChild( v, p );
            }else{//zag-zig
                std::cout << "here3" <<std::endl;
                attachAsRChild ( p, v->lc ); attachAsLChild( g, v->rc );
                attachAsRChild ( v, g ); attachAsLChild( v, p );
        }
        if ( !gg ) v->parent = NULL;
        else
            ( g == gg->lc ) ? attachAsLChild( gg, v ) : attachAsRChild( gg, v );
        BST<T>::updateHeight ( g ); BST<T>::updateHeight( p ); BST<T>::updateHeight( v );
    }
    if ( p = v->parent ){//只有父亲安在
        if (  v->data < p->data) { attachAsLChild( p, v->rc ) ; attachAsRChild( v, p ); }
        else                     { attachAsRChild( p, v->lc ) ; attachAsLChild( v, p ); }
        BST<T>::updateHeight( p ); BST<T>::updateHeight( v );
    }
    v->parent = NULL; return v;
}

7.3.5 查找

//查找
template <typename T> BinNodePosi(T) & Splay<T>::search( const T& e ){
    BinNodePosi(T) p = searchIn( this->_root, e, this->_hot = nullptr );
    this->_root = splay ( p ? p : this->_hot );
    return this->_root;
}

7.3.6 插入

//插入
template <typename T> BinNodePosi(T) Splay<T>::insert ( const T& e ){
    if ( !this->_root ) { this->_size ++; return this->_root = new BinNode<T> ( e ); }//处理原树为空的退化情况
    if ( e == search( e )->data ) return this->_root;//已经有这个数的情况
    this->_size++; BinNodePosi(T) t = this->_root;
    if ( this->_root->data < e ){
        t -> parent = this->_root = new BinNode<T> ( e, nullptr, t, t->rc );
        if ( HasRChild ( *t )) { t->rc->parent = this->_root; t->rc = nullptr; }
    }else{
        t->parent = this->_root = new BinNode<T> ( e, nullptr, t->lc, t );
        if ( HasLChild ( *t )) { t->lc->parent = this->_root; t->lc = nullptr; }
    }
    BST<T>::updateHeightAbove ( t );
    return this->_root;
}

7.3.7 删除

template <typename T> bool Splay<T>::remove( const T& e ){
    if (!this->_root || e != search(e)->data)  return false; 
    auto t = this->_root;
    if (!HasLChild( *(this->_root))) { // 若无左子树，直接删除
        this->_root = this->_root->rc; // 以右子树为树根
        if (this->_root) { this->_root->parent = nullptr; } // 更新右子树父节点为null
    } else if (!HasRChild( *(this->_root))) { // 若无右子树，直接删除
        this->_root = this->_root->lc; // 以左子树为树根
        if (this->_root) { this->_root->parent = nullptr; } // 更新左子树父节点为null
    } else { // 左、右子树同时存在
        // 暂时切除左子树
        auto ltree = this->_root->lc;
        ltree->parent = nullptr;
        this->_root->lc = nullptr;

        // 只保留右子树
        this->_root = this->_root->rc;
        this->_root->parent = nullptr;
        
        // 以原树根为目标，做一次（必定失败的）查找
        search(t->data);

        // 至此，右子树中最小节点必伸展至根，且（因无雷同节点）其左子树必空，于是只需将原左子树接回原位即可
        this->_root->lc = ltree;
        ltree->parent = this->_root;
    }

    // 释放节点，更新规模
    dtl::release(t->data); dtl::release(t); 
    this->_size--;

    // 此后，若树非空，则树根的高度需要更新
    if (this->_root) {
        this->updateHeight(this->_root);
    }

    return true;
}

7.3.8 Splay.h

#include "BST.h"
#include <iostream>
template <typename T> class Splay : public BST<T> {
    protected:
        BinNodePosi(T) splay (BinNodePosi(T) v);//将节点伸展到根
    public:
        BinNodePosi(T) & search( const T& e );//查找
        BinNodePosi(T) insert( const T& e );//插入
        bool remove ( const T& e );//删除
};
//查找
template <typename T> BinNodePosi(T) & Splay<T>::search( const T& e ){
    BinNodePosi(T) p = searchIn( this->_root, e, this->_hot = nullptr );
    this->_root = splay ( p ? p : this->_hot );
    return this->_root;
}
//插入
template <typename T> BinNodePosi(T) Splay<T>::insert ( const T& e ){
    if ( !this->_root ) { this->_size ++; return this->_root = new BinNode<T> ( e ); }//处理原树为空的退化情况
    if ( e == search( e )->data ) return this->_root;//已经有这个数的情况
    this->_size++; BinNodePosi(T) t = this->_root;
    if ( this->_root->data < e ){
        t -> parent = this->_root = new BinNode<T> ( e, nullptr, t, t->rc );
        if ( HasRChild ( *t )) { t->rc->parent = this->_root; t->rc = nullptr; }
    }else{
        t->parent = this->_root = new BinNode<T> ( e, nullptr, t->lc, t );
        if ( HasLChild ( *t )) { t->lc->parent = this->_root; t->lc = nullptr; }
    }
    BST<T>::updateHeightAbove ( t );
    return this->_root;
}
//删除
template <typename T> bool Splay<T>::remove( const T& e ){
    if (!this->_root || e != search(e)->data)  return false; 
    auto t = this->_root;
    if (!HasLChild( *(this->_root))) { // 若无左子树，直接删除
        this->_root = this->_root->rc; // 以右子树为树根
        if (this->_root) { this->_root->parent = nullptr; } // 更新右子树父节点为null
    } else if (!HasRChild( *(this->_root))) { // 若无右子树，直接删除
        this->_root = this->_root->lc; // 以左子树为树根
        if (this->_root) { this->_root->parent = nullptr; } // 更新左子树父节点为null
    } else { // 左、右子树同时存在
        // 暂时切除左子树
        auto ltree = this->_root->lc;
        ltree->parent = nullptr;
        this->_root->lc = nullptr;

        // 只保留右子树
        this->_root = this->_root->rc;
        this->_root->parent = nullptr;
        
        // 以原树根为目标，做一次（必定失败的）查找
        search(t->data);

        // 至此，右子树中最小节点必伸展至根，且（因无雷同节点）其左子树必空，于是只需将原左子树接回原位即可
        this->_root->lc = ltree;
        ltree->parent = this->_root;
    }

    // 释放节点，更新规模
    dtl::release(t->data); dtl::release(t); 
    this->_size--;

    // 此后，若树非空，则树根的高度需要更新
    if (this->_root) {
        this->updateHeight(this->_root);
    }

    return true;
}

template <typename NodePosi> inline
void attachAsLChild ( NodePosi p, NodePosi lc ) { p->lc = lc; if(lc) lc->parent = p; }//节点*p与*lc建立父（左）子关系
template <typename NodePosi> inline
void attachAsRChild ( NodePosi p, NodePosi rc ) { p->rc = rc; if(rc) rc->parent = p; }//节点*p与*rc建立父（右）子关系

//伸展算法的实现
template <typename T>
BinNodePosi(T) Splay<T>::splay ( BinNodePosi(T) v ){
    if( !v ) return nullptr; BinNodePosi(T) p; BinNodePosi(T) g;
    while( ( p = v->parent ) && ( g = p->parent )){//祖父与父亲都安在，双层伸展
        BinNodePosi(T) gg = g->parent;
        if( v->data < p->data)
            if( p->data < g->data){//zig-zig 
                attachAsLChild ( g, p->rc ); attachAsLChild( p, v->rc );
                attachAsRChild ( p, g ); attachAsRChild( v, p );
                std::cout << "here0" << p->data << g->data<< std::endl;
            }else{//zig-zag
                std::cout << "here1" <<std::endl;
                attachAsLChild ( p, v->rc ); attachAsRChild( g, v->lc );
                attachAsLChild ( v, g ); attachAsRChild( v, p );
            }
        else 
            if( p->data >= g->data){//zag-zag
                std::cout << "here2" <<std::endl;
                attachAsRChild ( g, p->lc ); attachAsRChild( p, v->lc );
                attachAsLChild ( p, g ); attachAsLChild( v, p );
            }else{//zag-zig
                std::cout << "here3" <<std::endl;
                attachAsRChild ( p, v->lc ); attachAsLChild( g, v->rc );
                attachAsRChild ( v, g ); attachAsLChild( v, p );
        }
        if ( !gg ) v->parent = NULL;
        else
            ( g == gg->lc ) ? attachAsLChild( gg, v ) : attachAsRChild( gg, v );
        BST<T>::updateHeight ( g ); BST<T>::updateHeight( p ); BST<T>::updateHeight( v );
    }
    if ( p = v->parent ){//只有父亲安在
        if (  v->data < p->data) { attachAsLChild( p, v->rc ) ; attachAsRChild( v, p ); }
        else                     { attachAsRChild( p, v->lc ) ; attachAsLChild( v, p ); }
        BST<T>::updateHeight( p ); BST<T>::updateHeight( v );
    }
    v->parent = NULL; return v;
}

7.3.9 Splay测试

#include "splay.h"
#include <iostream>
using namespace std;

template<typename T> void returnValue(T& a)
{
    cout << "return_value: " << a << endl;
}
int main(){
    Splay<int> bt_test;

	bt_test.insertAsRoot(7);
	BinNodePosi(int) root = bt_test.root();
	int i;
	const int a[7] = { 0, 6, 5, 4, 3, 2, 1};
	for( i = 1; i < 7; ++i ){
		bt_test.insertAsLC( root, 7-i );
		root = root->lc;
	}

	//测试用例
	/* 								7
							6
						5
					4
				3
			2
		1
	*/
	bt_test.search(1);//先序遍历的搜索结果为1642357,与推算结果符合
	/* 	
			1						
							6			
						4		7
				2			5
			 		3
	*/
	bt_test.insert(0);//先序遍历的搜索结果为01642357,与推算结果符合
	/* 	
	0
			1						
							6			
						4		7
				2			5
			 		3
	*/
	//bt_test.remove(59);//删除
	bt_test.remove(1);//先序遍历的搜索结果为2043657,与推算结果符合
	/* 	
		2
	0				4						
				3			6			
						5		7
							
			 		
	*/
	void (* visit)(int& ) = &returnValue;
	bt_test.traverse(bt_test.root(),visit);
	return 0;
    
}