伸展树

伸展树是一种二叉平衡树，普通搜索树在构造序列不是很理想的情况下，访问复杂度会退化。相比于较高级的一点平衡树，伸展树实现上还是比较简单的，只有左旋和右旋两个操作。这种数据结构的优化思路是利用数据访问的局部性，将上次访问的数据节点旋转到根节点，而不破坏平衡树的结构。

我自己实现的时候，核心操作只有左旋和右旋（所谓的Zig/Zag）。这两个操作是对称的，所以一个函数就可以搞定。为了方便操作，每个节点维护一个表示自己是左/右子节点的标记index_。节点表示如下（为方便访问，类中无私有变量）

class SplayNode {
public:
    SplayNode(int data, int index, SplayNode *p): data_(data), index_(index), parent_(p) {
        child_.resize(2, NULL);
    };
    SplayNode *parent_;
    std::vector<SplayNode*> child_;
    int data_;
    int index_;
};

对于一个节点，它的左旋或者右旋涉及他的孩子，父亲和祖父节点，注意，统一考虑的话，实际上孩子节点和祖父节点都是可以不存在的，所以代码里面添加了一些存在性判断。

void ZigOrZag(SplayNode *vis) {

    int index = vis->index_ != 0;
    SplayNode *g = vis->parent_->parent_;
    SplayNode *f = vis->parent_;
    SplayNode *c = vis->child_[1 - index];

    f->child_[index] = c;
    if (c != NULL) {
        c->parent_ = f;
        c->index_ = index;
    }

    f->parent_ = vis;
    vis->child_[1 - index] = f;

    vis->parent_ = g;
    if (g != NULL) {
        g->child_[f->index_] = vis;
        vis->index_ = f->index_;
    }
}

这么写的目的是双旋操作可以用以上单旋操作来表示。

void DualZigOrZag(SplayNode *vis) {
    ZigOrZag(vis->parent_);
    ZigOrZag(vis);
}

void CrossZigOrZag(SplayNode *vis) {
    ZigOrZag(vis);
    ZigOrZag(vis);
}

对于一个访问节点vis而言，伸展树的伸展操作就是要使该节点转到根节点的位置。一次旋转不够就多次旋转，直至成为根节点。旋转方式就是网上双旋加单旋，主要取决于祖父，父亲和该节点的位置关系。代码如下：

void Splay(SplayNode *vis) {
    while (vis->parent_ != NULL) {
        if (vis->parent_->parent_ == NULL)
            ZigOrZag(vis);
        else {
            if (vis->index_ == vis->parent_->index_)
                DualZigOrZag(vis);
            else
                CrossZigOrZag(vis);
        }
    }
}

为了可视化，最终将树BFS成dot语言格式，可以绘制出来。

void BFS(SplayNode *root) {
    std::queue<SplayNode*> Q;
    Q.push(root);
    std::cout << "digraph Splay {" << std::endl;
    std::cout << "\tnode [shape = record, height = .1]" << std::endl;
    while (!Q.empty()) {
        SplayNode *p = Q.front();
        Q.pop();
        std::cout << "\t" << p->data_ << "[label = \"<F0> |<F1> " << p->data_ << "|<F2> \"]\n";
        for (int i = 0; i < 2; i++) {
            std::string node = i == 0 ? "F0": "F2";
            if (p->child_[i]) {
                std::cout << "\t\"" << p->data_ << "\":" << node << " -> "
                          "\"" << p->child_[i]->data_ <<"\":F1;" << std::endl;
                Q.push(p->child_[i]);
            }
        }
    }
    std::cout << "}" << std::endl;
}

以5, 4, 1, 2, 3, 8, 7, 6, 9为例，原二叉搜索树如下：

在这棵树上对节点的伸展结果如下：

节点4

节点1

节点7

节点6