Splay tree --扩展树

扩展树的C语言实现版本，这个是自上而下且节点带大小（size)的扩展树（伸展树）的具体实现。它由Daniel Dominic Sleator 和Robert Endre Tarjan，Tarjan在计算机算法领域，是个大师级别的人物，求强连通图的分量scc算法，很多基础的算法都是他发现的一个扩展树是自适应调整的二叉搜索树。其他常见的二叉搜索树有，AVL tree，red-black tree(红黑树）。但这里有个明显的区别，splay tree 通过节点额外附带属性信息，该信息记录最近访问的节点。它提供基本操作，如插入，查询和删除，平摊情况下都是 O(logN)的渐近复杂度，单次操作，要比，要对于非随机访问操作，splay tree，即使在不知道访问序列的具体模式情况下，也比其他搜索树提供较好性能。二叉搜索树上的所有普通操作（节点的增删改查），如果整合一个基本操作，都成为splaying，按照一定元素顺序Splaying 这个树，即重新排列了节点，并且这个节点被置为根。一种方法是，第一步，基于标准二叉树的执行对该节点原有的操作，然后基于树的旋转，使得这个节点成为根节点。相应的，一个top-down算法可以整合查询和树的重新组织为一个单一的步骤。

 

头文件：

#ifndef _SPLAY_TREE_H_
#define _SPLAY_TREE_H_

typedef struct tree_node {
    struct tree_node * left, * right;
    int key;
    int size;   /* maintained to be the number of nodes rooted here */

    void *data;
} splay_tree;


splay_tree * splaytree_splay (splay_tree *t, int key);
splay_tree * splaytree_insert(splay_tree *t, int key, void *data);
splay_tree * splaytree_delete(splay_tree *t, int key);
splay_tree * splaytree_size(splay_tree *t);

#define splaytree_size(x) (((x)==NULL) ? 0 : ((x)->size))
/* This macro returns the size of a node.  Unlike "x->size",     */
/* it works even if x=NULL.  The test could be avoided by using  */
/* a special version of NULL which was a real node with size 0.  */


#endif

 

实现代码：

/*
           An implementation of top-down splaying with sizes
             D. Sleator <[e-mail]>, January 1994.

  This extends top-down-splay.c to maintain a size field in each node.
  This is the number of nodes in the subtree rooted there.  This makes
  it possible to efficiently compute the rank of a key.  (The rank is
  the number of nodes to the left of the given key.)  It it also
  possible to quickly find the node of a given rank.  Both of these
  operations are illustrated in the code below.  The remainder of this
  introduction is taken from top-down-splay.c.

  "Splay trees", or "self-adjusting search trees" are a simple and
  efficient data structure for storing an ordered set.  The data
  structure consists of a binary tree, with no additional fields.  It
  allows searching, insertion, deletion, deletemin, deletemax,
  splitting, joining, and many other operations, all with amortized
  logarithmic performance.  Since the trees adapt to the sequence of
  requests, their performance on real access patterns is typically even
  better.  Splay trees are described in a number of texts and papers
  [1,2,3,4].

  The code here is adapted from simple top-down splay, at the bottom of
  page 669 of [2].  It can be obtained via anonymous ftp from
  spade.pc.cs.cmu.edu in directory /usr/sleator/public.

  The chief modification here is that the splay operation works even if the
  item being splayed is not in the tree, and even if the tree root of the
  tree is NULL.  So the line:

                              t = splay(i, t);

  causes it to search for item with key i in the tree rooted at t.  If it's
  there, it is splayed to the root.  If it isn't there, then the node put
  at the root is the last one before NULL that would have been reached in a
  normal binary search for i.  (It's a neighbor of i in the tree.)  This
  allows many other operations to be easily implemented, as shown below.

  [1] "Data Structures and Their Algorithms", Lewis and Denenberg,
       Harper Collins, 1991, pp 243-251.
  [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
       JACM Volume 32, No 3, July 1985, pp 652-686.
  [3] "Data Structure and Algorithm Analysis", Mark Weiss,
       Benjamin Cummins, 1992, pp 119-130.
  [4] "Data Structures, Algorithms, and Performance", Derick Wood,
       Addison-Wesley, 1993, pp 367-375
*/

#include "splaytree.h"
#include <stdlib.h>
#include <assert.h>

#define compare(i,j) ((i)-(j))
/* This is the comparison.                                       */
/* Returns <0 if i<j, =0 if i=j, and >0 if i>j                   */

#define node_size splaytree_size

/* Splay using the key i (which may or may not be in the tree.)
 * The starting root is t, and the tree used is defined by rat
 * size fields are maintained */
splay_tree * splaytree_splay (splay_tree *t, int i) {
    splay_tree N, *l, *r, *y;
    int comp, l_size, r_size;

    if (t == NULL) return t;
    N.left = N.right = NULL;
    l = r = &N;
    l_size = r_size = 0;
/*查找key，一边查找一边进行旋转操作，通过compare函数，这个在c++中需要重载-号*/
    for (;;) {
        comp = compare(i, t->key);
        if (comp < 0) {
            if (t->left == NULL) break;
            if (compare(i, t->left->key) < 0) {/*如果要查询的值比节点值小，且比左子节点小，LL类型*/
                y = t->left;                           /* rotate right ，LL类型，右旋*/
                t->left = y->right;
                y->right = t;
                t->size = node_size(t->left) + node_size(t->right) + 1;
                t = y;
                if (t->left == NULL) break;
            }
            r->left = t;                               /* link right */
            r = t;
            t = t->left;
            r_size += 1+node_size(r->right);
        } else if (comp > 0) {
            if (t->right == NULL) break;
            if (compare(i, t->right->key) > 0) {
                y = t->right;                          /* rotate left */
                t->right = y->left;
                y->left = t;
		t->size = node_size(t->left) + node_size(t->right) + 1;
                t = y;
                if (t->right == NULL) break;
            }
            l->right = t;                              /* link left */
            l = t;
            t = t->right;
            l_size += 1+node_size(l->left);
        } else {
            break;
        }
    }
    l_size += node_size(t->left);  /* Now l_size and r_size are the sizes of */
    r_size += node_size(t->right); /* the left and right trees we just built.*/
    t->size = l_size + r_size + 1;

    l->right = r->left = NULL;

    /* The following two loops correct the size fields of the right path  */
    /* from the left child of the root and the right path from the left   */
    /* child of the root.                                                 */
    for (y = N.right; y != NULL; y = y->right) {
        y->size = l_size;
        l_size -= 1+node_size(y->left);
    }
    for (y = N.left; y != NULL; y = y->left) {
        y->size = r_size;
        r_size -= 1+node_size(y->right);
    }

    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;

    return t;
}

splay_tree * splaytree_insert(splay_tree * t, int i, void *data) {
/* Insert key i into the tree t, if it is not already there. */
/* Return a pointer to the resulting tree.                   */
    splay_tree * new;

    if (t != NULL) {
	t = splaytree_splay(t, i);
	if (compare(i, t->key)==0) {
	    return t;  /* it's already there */
	}
    }
    new = (splay_tree *) malloc (sizeof (splay_tree));
    assert(new);
    if (t == NULL) {
	new->left = new->right = NULL;
    } else if (compare(i, t->key) < 0) {
	new->left = t->left;
	new->right = t;
	t->left = NULL;
	t->size = 1+node_size(t->right);
    } else {
	new->right = t->right;
	new->left = t;
	t->right = NULL;
	t->size = 1+node_size(t->left);
    }
    new->key = i;
    new->data = data;
    new->size = 1 + node_size(new->left) + node_size(new->right);
    return new;
}

splay_tree * splaytree_delete(splay_tree *t, int i) {
/* Deletes i from the tree if it's there.               */
/* Return a pointer to the resulting tree.              */
    splay_tree * x;
    int tsize;

    if (t==NULL) return NULL;
    tsize = t->size;
    t = splaytree_splay(t, i);
    if (compare(i, t->key) == 0) {               /* found it */
	if (t->left == NULL) {
	    x = t->right;
	} else {
	    x = splaytree_splay(t->left, i);
	    x->right = t->right;
	}
	free(t);
	if (x != NULL) {
	    x->size = tsize-1;
	}
	return x;
    } else {
	return t;                         /* It wasn't there */
    }
}

#if 0
static splay_tree *find_rank(int r, splay_tree *t) {
/* Returns a pointer to the node in the tree with the given rank.  */
/* Returns NULL if there is no such node.                          */
/* Does not change the tree.  To guarantee logarithmic behavior,   */
/* the node found here should be splayed to the root.              */
    int lsize;
    if ((r < 0) || (r >= node_size(t))) return NULL;
    for (;;) {
	lsize = node_size(t->left);
	if (r < lsize) {
	    t = t->left;
	} else if (r > lsize) {
	    r = r - lsize -1;
	    t = t->right;
	} else {
	    return t;
	}
    }
}
#endif

 

 

splaytree算法复杂度：http://en.wikipedia.org/wiki/Splay_tree

平摊分析情况下：

 

Splay tree Type Invented Invented by Time complexity
in big O notation Space Search Insert Delete

Tree
1985
Daniel Dominic Sleator and Robert Endre Tarjan
	Average	Worst case
O(n)	O(n)
O(log n)	amortized O(log n)
O(log n)	amortized O(log n)
O(log n)	amortized O(log n)