《樹》之伸展樹

本文介紹什么？

1. 使用伸展樹有什么樣的效果；
   

2. 伸展樹的定義；

3. 伸展樹ADT具體實(shí)現(xiàn)過(guò)程的描述；

4. 代碼實(shí)現(xiàn)。

一、使用伸展樹(splay tree)的效果：

              使用伸展樹時(shí)，對(duì)伸展樹上任意一次操作的最壞運(yùn)行時(shí)間為 O( N )；但是，它保證了連續(xù)M次操作花費(fèi)的最多時(shí)間為O(M ㏒N)，從而可以推算出對(duì)伸展樹的每一次操作的攤還時(shí)間為O( ㏒N)。

二、伸展樹的定義:

        對(duì)于一顆二查查找樹進(jìn)行操作時(shí)，每訪問(wèn)一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)都通過(guò)旋轉(zhuǎn)操作被放到根上。這樣的一顆二查查找樹稱為伸展樹。

三、伸展樹ADT的描述:

        1.伸展樹的節(jié)點(diǎn)定義與二查查找樹節(jié)點(diǎn)定義的方法一致，此處不再贅述；

        2.比起二查查找樹，伸展樹ADT只是對(duì)了一個(gè)旋轉(zhuǎn)操作。在這里的旋轉(zhuǎn)，我們稱之為展開(kāi)(Splaying)。設(shè)節(jié)點(diǎn)X為訪問(wèn)的節(jié)點(diǎn)，我們通過(guò)對(duì)節(jié)點(diǎn)X進(jìn)行一系列操作，將節(jié)點(diǎn)X移動(dòng)到根節(jié)點(diǎn)。

        3.節(jié)點(diǎn)X旋轉(zhuǎn)的情況:

             ⑴節(jié)點(diǎn)X為根節(jié)點(diǎn)：什么都不做；

             ⑵節(jié)點(diǎn)X的父節(jié)點(diǎn)為根節(jié)點(diǎn):

                     根節(jié)點(diǎn)的左子樹=X的右子樹；

                     X的右子樹=根節(jié)點(diǎn)；

             ⑶節(jié)點(diǎn)X具有父節(jié)點(diǎn)（P）、祖父節(jié)點(diǎn)（G），此時(shí)有（兩類）四種情況需要考慮:

                     ⅰ、( "一" 字形) P是G的左兒子，X是P的左兒子;

                     ⅱ、( "一" 字形)P是G的右兒子，X是P的右兒子;

                     ⅲ、( "之" 字形)P是G的左兒子，X是P的右兒子;

                     ⅳ、( "之" 字形)P是G的右兒子，X是P的左兒子;

        4.節(jié)點(diǎn)的刪除:

              由于對(duì)節(jié)點(diǎn)X的每一次訪問(wèn)都需要將X移向根節(jié)點(diǎn)，所以懶惰刪除在這里顯得不太合適，在這里需要進(jìn)行的直接刪除。當(dāng)進(jìn)行刪除操作時(shí)，首先需要訪問(wèn)節(jié)點(diǎn)X，節(jié)點(diǎn)X被移動(dòng)到根節(jié)點(diǎn)，此時(shí)刪除X花費(fèi)的代價(jià)是比較小的。在刪除節(jié)點(diǎn)X的時(shí)候，①訪問(wèn)X導(dǎo)致節(jié)點(diǎn)X被移向根節(jié)點(diǎn)，刪除節(jié)點(diǎn)X并得到左、右兩棵子樹(TL、TR)；②在右子樹TR上訪問(wèn)最小節(jié)點(diǎn)Y(該節(jié)點(diǎn)一定沒(méi)有左兒子)，將Y移動(dòng)到右子樹的根節(jié)點(diǎn)；③令Y的左兒子為左子樹TL。

四、核心代碼實(shí)現(xiàn)：

    1.伸展樹的伸展實(shí)現(xiàn)

         ⅰ、( "一" 字形) P是G的左兒子，X是P的左兒子;

              操作:

                  G的左兒子=P的右兒子;

                  P的右兒子=G；

                  P的左兒子=X的右兒子；

                  X的右兒子=P；

//一字形（左左）

static Position ZigzigLL(Position g)
{
    Position p,x;
    p=g->left;x=p->left;
    
    g->left=p->right;
    p->right=g;
    p->left=x->right;
    x->right=p;
    
    return x;
}

ⅱ、( "一" 字形)P是G的右兒子，X是P的右兒子;

        操作:

            G的右兒子=P的左兒子；

            P的左兒子=G；

            P的右兒子=X的左兒子；

            X的左兒子=P； 

//一字形（右右）

static Position ZigzigRR(Position g)
{
    Position p,x;
    p=g->right;x=p->right;
    
    g->right=p->left;
    p->left=g;
    p->right=x->left;
    x->left=p;
    
    return x;
}

ⅲ、( "之" 字形)P是G的左兒子，X是P的右兒子;

        操作:

            G的左兒子=X的右兒子；

            X的右兒子=G;

            P的右兒子=X的左兒子；

            X的左兒子=P；

//一字形（左右）

static Position ZigzigLR(Position g)
{
    Position p,x;
    p=g->left;x=p->right;
    
    g->left=x->right;
    x->right=g;
    p->right=x->left;
    x->left=p;
    
    return x;
}

ⅳ、( "之" 字形)P是G的右兒子，X是P的左兒子;           

        操作:

            G的右兒子=X的左兒子；

            X的左兒子=G；

            P的左兒子=X的右兒子；

            X的右兒子=P；

//一字形（右左）

static Position ZigzigRL(Position g)
{
    Position p,x;
    p=g->right;x=p->left;
    
    g->right=x->left;
    x->left=g;
    p->left=x->right;
    x->right=p;
    
    return x;
}

    3.伸展樹的刪除操作實(shí)現(xiàn)

//刪除節(jié)點(diǎn)
void Delete(const ElementType x,const sTree st)
{
    if(NULL==st) printf("該樹為空樹\n");
    else{
        position temp=Find(x,st);
        Position root=FindMin(temp->right);
        root->left=temp->left;
        
        free(temp);
        temp=NULL;
        return ;
    }
}