纸上谈兵: 伸展树 (splay tree)

我们讨论过，树的搜索效率与树的深度有关。二叉搜索树的深度可能为n，这种情况下，每次搜索的复杂度为n的量级。AVL树通过动态平衡树的深度，单次搜索的复杂度为log(n) (以上参考纸上谈兵 AVL树)。我们下面看伸展树(splay tree)，它对于m次连续搜索操作有很好的效率。

伸展树会在一次搜索后，对树进行一些特殊的操作。这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度。但伸展树并没有AVL的平衡要求，任意节点的左右子树可以相差任意深度。与二叉搜索树类似，伸展树的单次搜索也可能需要n次操作。但伸展树可以保证，m次的连续搜索操作的复杂度为mlog(n)的量级，而不是mn量级。

具体来说，在查询到目标节点后，伸展树会不断进行下面三种操作中的一个，直到目标节点成为根节点 （注意，祖父节点是指父节点的父节点）

1. zig: 当目标节点是根节点的左子节点或右子节点时，进行一次单旋转，将目标节点调整到根节点的位置。

zig

2. zig-zag: 当目标节点、父节点和祖父节点成"zig-zag"构型时，进行一次双旋转，将目标节点调整到祖父节点的位置。

zig-zag

3. zig-zig：当目标节点、父节点和祖父节点成"zig-zig"构型时，进行一次zig-zig操作，将目标节点调整到祖父节点的位置。

zig-zig

单旋转操作和双旋转操作见AVL树。下面是zig-zig操作的示意图:

zig-zig operation

在伸展树中，zig-zig操作(基本上)取代了AVL树中的单旋转。通常来说，如果上面的树是失衡的，那么A、B子树很可能深度比较大。相对于单旋转(想一下单旋转的效果)，zig-zig可以将A、B子树放在比较高的位置，从而减小树总的深度。

下面我们用一个具体的例子示范。我们将从树中搜索节点2：

Original

zig-zag (double rotation)

zig-zig

zig (single rotation at root)

上面的第一次查询需要n次操作。然而经过一次查询后，2节点成为了根节点，树的深度大减小。整体上看，树的大部分节点深度都减小。此后对各个节点的查询将更有效率。

伸展树的另一个好处是将最近搜索的节点放在最容易搜索的根节点的位置。在许多应用环境中，比如网络应用中，某些固定内容会被大量重复访问(比如江南style的MV)。伸展树可以让这种重复搜索以很高的效率完成。

伸展树的C实现

/* By Vamei */
/* Splay Tree */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

struct node {
    position parent;
    ElementTP element;
    position lchild;
    position rchild;
};

/* pointer => root node of the tree */
typedef struct node *TREE;

TREE find_value(TREE, ElementTP);
position insert_value(TREE, ElementTP);

static void splay_tree(TREE, position);
static position search_value(TREE, ElementTP);
static void with_grandpa(TREE, position);

static void insert_node_to_nonempty_tree(TREE, position);
static TREE left_single_rotate(TREE);
static TREE left_double_rotate(TREE);
static TREE right_single_rotate(TREE);
static TREE right_double_rotate(TREE);
static TREE left_zig_zig(TREE);
static TREE right_zig_zig(TREE);

void main(void) 
{
    TREE tr;
    tr = NULL;
    tr = insert_value(tr, 6);
    tr = insert_value(tr, 5);
    tr = insert_value(tr, 4);
    tr = insert_value(tr, 3);
    tr = insert_value(tr, 1); 
    tr = insert_value(tr, 2); 

    tr = find_value(tr, 2);
    printf("%d\n", tr->rchild->lchild->element);
}

/* 
 * insert a value into the tree
 * return root address of the tree
 */
position insert_value(TREE tr, ElementTP value) 
{
    position np;
    /* prepare the node */
    np = (position) malloc(sizeof(struct node));
    np->element = value;
    np->parent  = NULL;
    np->lchild  = NULL;
    np->rchild  = NULL;
 
    if (tr == NULL) tr = np;
    else {
        insert_node_to_nonempty_tree(tr, np);
    }
    return tr;
}


/*
 *
 * return NUll if not found 
 */
TREE find_value(TREE tr, ElementTP value)
{
    position np;

    np = search_value(tr, value);
    if (np != NULL && np != tr) {
        splay_tree(tr, np);
    }
    return np;
}

/*
 * splaying the tree after search
 */
static void splay_tree(TREE tr, position np)
{
    while (tr->lchild != np && tr->rchild != np) {
        with_grandpa(tr, np);
    }
    if (tr->lchild == np) {
        right_single_rotate(tr);
    }
    else if (tr->rchild == np) {
        left_single_rotate(tr);
    }
}

/*
 * dealing cases with grandparent node
 */
static void with_grandpa(TREE tr, position np)
{
    position parent, grandPa;
    int i,j; 

    parent  = np->parent;
    grandPa = parent->parent;
 
    i = (grandPa->lchild == parent) ? -1 : 1;
    j = (parent->lchild == np) ? -1 : 1;
    if (i == -1 && j == 1) {
        right_double_rotate(grandPa);
    }
    else if (i == 1 && j == -1) {
        left_double_rotate(grandPa);
    }
    else if (i == -1 && j == -1) {
        right_zig_zig(grandPa);
    }
    else {
        left_zig_zig(grandPa);
    }
}

/*
 * search for value
 */
static position search_value(TREE tr, ElementTP value) 
{
    if (tr == NULL) return NULL; 

    if (tr->element == value) {
        return tr;
    }
    else if (value < tr->element) {
        return search_value(tr->lchild, value);
    }
    else {
        return search_value(tr->rchild, value);
    }
}

/* 
 * left single rotation 
 * return the new root
 */
static TREE left_single_rotate(TREE tr) 
{
    TREE newRoot, parent;
    parent  = tr->parent;
    newRoot = tr->rchild;
    /* detach & attach */ 
    if (newRoot->lchild != NULL) newRoot->lchild->parent = tr;
    tr->rchild = newRoot->lchild;
   
    /* raise new root node */
    newRoot->lchild = tr;
    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->lchild == tr) {
        parent->lchild = newRoot;
    }
    else {
        parent->rchild = newRoot;
    }
    }
    tr->parent = newRoot;
    return newRoot;
}

/* 
 * right single rotation 
 * return the new root
 */
static TREE right_single_rotate(TREE tr) 
{
    TREE newRoot, parent;
    parent  = tr->parent;
    newRoot = tr->lchild;

    /* detach & attach */
    if (newRoot->rchild != NULL) newRoot->rchild->parent = tr;
    tr->lchild = newRoot->rchild;
  
    /* raise new root node */
    newRoot->rchild = tr;
    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->lchild == tr) {
        parent->lchild = newRoot;
    }
    else {
        parent->rchild = newRoot;
    }
    }
    tr->parent = newRoot;
    return newRoot;
}

/*
 * left double rotation
 * return
 */
static TREE left_double_rotate(TREE tr) 
{
    right_single_rotate(tr->rchild);
    return left_single_rotate(tr);
}

/*
 * right double rotation
 * return
 */
static TREE right_double_rotate(TREE tr) 
{
    left_single_rotate(tr->lchild);
    return right_single_rotate(tr);
}

/*
 * insert a node to a non-empty tree
 * called by insert_value()
 */
static void insert_node_to_nonempty_tree(TREE tr, position np)
{
    /* insert the node */
    if(np->element <= tr->element) {
        if (tr->lchild == NULL) {
            /* then tr->lchild is the proper place */
            tr->lchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->lchild, np);
        }
    }
    else if(np->element > tr->element) {
        if (tr->rchild == NULL) {
            tr->rchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->rchild, np);
        }
    }
}

/*
 * right zig-zig operation
 */
static TREE right_zig_zig(TREE tr)
{
    position parent,middle,newRoot;
    parent  = tr->parent;
    middle  = tr->lchild;
    newRoot = tr->lchild->lchild;

    tr->lchild = middle->rchild;
    if (middle->rchild != NULL) middle->rchild->parent = tr;

    middle->rchild = tr;
    tr->parent     = middle;

    middle->lchild = newRoot->rchild;
    if (newRoot->rchild != NULL) newRoot->rchild->parent = middle;

    newRoot->rchild = middle;
    middle->parent  = newRoot;

    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->lchild == tr) {
        parent->lchild = newRoot;
    }
    else {
        parent->rchild = newRoot;
    }
    }
    return newRoot;  
}

/*
 * left zig-zig operation
 */
static TREE left_zig_zig(TREE tr)
{
    position parent,middle,newRoot;
    parent  = tr->parent;
    middle  = tr->rchild;
    newRoot = tr->rchild->rchild;

    tr->rchild = middle->lchild;
    if (middle->lchild != NULL) middle->lchild->parent = tr;

    middle->lchild = tr;
    tr->parent     = middle;

    middle->rchild = newRoot->lchild;
    if (newRoot->lchild != NULL) newRoot->lchild->parent = middle;

    newRoot->lchild = middle;
    middle->parent  = newRoot;

    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->rchild == tr) {
        parent->rchild = newRoot;
    }
    else {
        parent->lchild = newRoot;
    }
    }
    return newRoot;  
}

运行结果:

4

总结

splay tree, m operations: mlog(n)

zig-zig

欢迎继续阅读“纸上谈兵: 算法与数据结构”系列。