伸展树的概念及C++实现

伸展树的概念

伸展树是一种二叉树，它能够保证M次操作最多花费O(M log N)的时间，即摊还代价(即平分到每一次操作的代价)为O(log N)。

前面的博客讲过了的AVL树：

浅析AVL树–AVL树的概念及单旋转
浅析AVL树–AVL树的双旋转
浅析AVL树–AVL树的C++实现

AVL树能够保证每一次操作后树都会平衡（即任意结点左右子树最多差1)

在《数据结构与算法分析》一书中有这么一段话：

对于二叉查找树来说，每次操作的最坏情形时间O(N)并不坏，只要它相对不常发生就行。

这也是伸展树为什么存在的原因----伸展树的基本想法是，每次访问一个元素，都要通过一系列的AVL旋转操作将其旋转到根部位置 — 方便下次访问（很有可能下次还是访问的同一个元素）。

我们很容易想到这样一个策略：访问到元素X时，不停地将X与其父节点进行旋转，直至X旋转到根节点的位置，但是这样的策略有问题—如下图，按顺序插入6，5，4，3，2，1，再倒序访问各个元素：

可以发现，在访问结点1的时候会将结点2推向树尾的位置，访问在访问结点2的时候又会将结点3推向树尾的位置。。。。如此按顺序访问1，2，3，4，5，6的时间复杂度会是O(N²)。因此这个策略不够好。

伸展树的展开操作类似于上面的策略，但是会尽量避免上述情况的发生。

伸展树的展开分为以下三种情况(细分之下可以分为6中小情况)：

I . 当前结点X的父节点就是树根，那么只需将X与父节点做一次单旋转即可。根据X是父节点的左儿子还是右儿子可以细分为单左旋转和单右旋转。

II . 当前结点X呈现出“之”字形(ZigZag)，如下图所示，这时候对根据X属于哪一种情况对X进行LR双旋转或者RL双旋转就可以。
III . 当前结点呈现"一"字形(ZigZig)，这种情况下，需要对3个结点进行旋转：
## 伸展树的C++实现：
首先是伸展树的类定义：

//File：SplayTree.h
class SplayTree {
public:
    typedef struct __node{
        struct __node *left,*right,*parent;
        int data;
    } TreeNode;
    typedef TreeNode * Position;
    void insert(int data);
    Position find(int data);
    Position visit(int data);
    SplayTree();

public:
    Position headnode;
    Position doSingleL(Position p);  //以p->left为旋转中心将p右旋
    Position doSingleR(Position p);  //以p->right为旋转中心将p左旋
    Position doRL(Position p);
    Position doLR(Position p);
    Position doZigZigL(Position p);
    Position doZigZigR(Position p);
};

然后是伸展树的具体实现：

//File：SplayTree.cpp
#include "SplayTree.h"

SplayTree::SplayTree():headnode(nullptr) {

}

void SplayTree::insert(int data) {
    Position* curr = &headnode;
    Position lastPatent = nullptr;
    bool lastIsLeft=false;
    while(*curr && (*curr)->data!=data)
    {
        if(data < (*curr)->data)
        {
            lastPatent = *curr;
            curr = &((*curr) -> left);
            lastIsLeft = true;
        }
        else
        {
            lastPatent = *curr;
            curr = &((*curr) -> right);
            lastIsLeft = false;
        }
    }
    if(!*curr)
    {
        *curr = new TreeNode;
        (*curr) -> data = data;
        (*curr) -> left = (*curr) -> right = nullptr;
        if(lastPatent)
        {
            if(lastIsLeft)
                lastPatent -> left = *curr;
            else
                lastPatent -> right = *curr;
        }

        (*curr)->parent = lastPatent;

    }
}

SplayTree::Position SplayTree::find(int data) {
    Position curr = headnode;

    while(curr && curr->data!=data)
    {
        if(data < curr->data)
            curr = curr -> left;
        else
            curr = curr -> right;
    }

    return curr;
}
SplayTree::Position SplayTree::visit(int data) {
    Position curr = find(data);

    while(curr!=headnode)
    {
        if(curr && headnode->left == curr)
            curr = doSingleL(headnode);
        else if (curr && headnode->right == curr)
            curr = doSingleR(headnode);
        else if(curr->parent->left == curr && curr->parent->parent->right == curr->parent)
            curr = doRL(curr->parent->parent);
        else if(curr->parent->right == curr && curr->parent->parent->left == curr->parent)
            curr = doLR(curr->parent->parent);
        else if (curr->parent->left == curr && curr->parent->parent->left == curr->parent)
            curr = doZigZigL(curr->parent->parent);
        else
            curr = doZigZigR(curr->parent->parent);
    }

    return curr;
}
//调用条件：L型子树
//INPUT: 需要进行单右旋的结点子树
//OUTPUT: 旋转完成后的子树根节点
//NEED TO DO:旋转、更新parent的left指针、更新原根节点的parnet指针、更新现根节点的parent指针、
//从q->left挪到p->right结点的parent
SplayTree::Position SplayTree::doSingleL(SplayTree::Position p) {
    Position parent = p -> parent;
    Position q = p -> left;

    p->left = q->right;
    if(p->left)
        p->left->parent=p;
    q->right = p;

    p->parent = q;
    q->parent=parent;
    if(parent && parent->left == p)
        parent->left = q;
    else if (parent && parent->right == p)
        parent->right = q;
    else if(!parent)
        headnode = q;
    return q;
}
//调用条件：R型子树
//INPUT: 需要进行单左旋的结点子树
//OUTPUT: 旋转完成后的子树根节点
//NEED TO DO:旋转、更新parent的left指针、更新原根节点的parnet指针、更新现根节点的parent指针、
//从q->left挪到p->right结点的parent
SplayTree::Position SplayTree::doSingleR(SplayTree::Position p) {
    Position parent = p -> parent;
    Position q = p -> right;

    p->right = q->left;
    if(p->right)
        p->right->parent=p;
    q->left = p;

    p->parent = q;
    q->parent=parent;
    if(parent && parent->left == p)
        parent->left = q;
    else if (parent && parent->right == p)
        parent->right = q;
    else if(!parent)
        headnode = q;
    return q;
}
SplayTree::Position SplayTree::doRL(SplayTree::Position p) {
    p->right = doSingleL(p->right);
    return doSingleR(p);
}
SplayTree::Position SplayTree::doLR(SplayTree::Position p) {
    p->left = doSingleR(p->left);
    return doSingleL(p);
}
SplayTree::Position SplayTree::doZigZigL(SplayTree::Position p) {
    p = doSingleL(p);
    p = doSingleL(p);
    return p;
}
SplayTree::Position SplayTree::doZigZigR(SplayTree::Position p) {
    p = doSingleR(p);
    p = doSingleR(p);
    return p;
}