为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
Code:Splay Tree/C
来自NOCOW
(跳转自Splay Tree C)
/* An implementation of top-down splaying D. Sleator <sleator@cs.cmu.edu> March 1992 "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, without parent pointers, and 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,5]. The code here is adapted from simple top-down splay, at the bottom of page 669 of [3]. 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] "Fundamentals of data structures in C", Horowitz, Sahni, and Anderson-Freed, Computer Science Press, pp 542-547. [2] "Data Structures and Their Algorithms", Lewis and Denenberg, Harper Collins, 1991, pp 243-251. [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan, JACM Volume 32, No 3, July 1985, pp 652-686. [4] "Data Structure and Algorithm Analysis", Mark Weiss, Benjamin Cummins, 1992, pp 119-130. [5] "Data Structures, Algorithms, and Performance", Derick Wood, Addison-Wesley, 1993, pp 367-375. The following code was written by Daniel Sleator, and is released in the public domain. */ #include <stdio.h> int size; /* number of nodes in the tree */ /* Not actually needed for any of the operations */ typedef struct tree_node Tree; struct tree_node { Tree * left, * right; int item; }; Tree * splay (int i, Tree * t) { /* Simple top down splay, not requiring i to be in the tree t. */ /* What it does is described above. */ Tree N, *l, *r, *y; if (t == NULL) return t; N.left = N.right = NULL; l = r = &N; for (;;) { if (i < t->item) { if (t->left == NULL) break; if (i < t->left->item) { y = t->left; /* rotate right */ t->left = y->right; y->right = t; t = y; if (t->left == NULL) break; } r->left = t; /* link right */ r = t; t = t->left; } else if (i > t->item) { if (t->right == NULL) break; if (i > t->right->item) { y = t->right; /* rotate left */ t->right = y->left; y->left = t; t = y; if (t->right == NULL) break; } l->right = t; /* link left */ l = t; t = t->right; } else { break; } } l->right = t->left; /* assemble */ r->left = t->right; t->left = N.right; t->right = N.left; return t; } /* Here is how sedgewick would have written this. */ /* It does the same thing. */ Tree * sedgewickized_splay (int i, Tree * t) { Tree N, *l, *r, *y; if (t == NULL) return t; N.left = N.right = NULL; l = r = &N; for (;;) { if (i < t->item) { if (t->left != NULL && i < t->left->item) { y = t->left; t->left = y->right; y->right = t; t = y; } if (t->left == NULL) break; r->left = t; r = t; t = t->left; } else if (i > t->item) { if (t->right != NULL && i > t->right->item) { y = t->right; t->right = y->left; y->left = t; t = y; } if (t->right == NULL) break; l->right = t; l = t; t = t->right; } else break; } l->right=t->left; r->left=t->right; t->left=N.right; t->right=N.left; return t; } Tree * insert(int i, Tree * t) { /* Insert i into the tree t, unless it's already there. */ /* Return a pointer to the resulting tree. */ Tree * new; new = (Tree *) malloc (sizeof (Tree)); if (new == NULL) { printf("Ran out of space\n"); exit(1); } new->item = i; if (t == NULL) { new->left = new->right = NULL; size = 1; return new; } t = splay(i,t); if (i < t->item) { new->left = t->left; new->right = t; t->left = NULL; size ++; return new; } else if (i > t->item) { new->right = t->right; new->left = t; t->right = NULL; size++; return new; } else { /* We get here if it's already in the tree */ /* Don't add it again */ free(new); return t; } } Tree * delete(int i, Tree * t) { /* Deletes i from the tree if it's there. */ /* Return a pointer to the resulting tree. */ Tree * x; if (t==NULL) return NULL; t = splay(i,t); if (i == t->item) { /* found it */ if (t->left == NULL) { x = t->right; } else { x = splay(i, t->left); x->right = t->right; } size--; free(t); return x; } return t; /* It wasn't there */ } void main() { /* A sample use of these functions. Start with the empty tree, */ /* insert some stuff into it, and then delete it */ Tree * root; int i; root = NULL; /* the empty tree */ size = 0; for (i = 0; i < 1024; i++) { root = insert((541*i) & (1023), root); } for (i = 0; i < 1024; i++) { root = delete((541*i) & (1023), root); } printf("size = %d\n", size); }
#include "splay.h" #include <stdlib.h> #include "fatal.h" struct SplayNode { ElementType Element; SplayTree Left; SplayTree Right; }; typedef struct SplayNode *Position; static Position NullNode = NULL; /* Needs initialization */ SplayTree Initialize( void ) { if( NullNode == NULL ) { NullNode = malloc( sizeof( struct SplayNode ) ); if( NullNode == NULL ) FatalError( "Out of space!!!" ); NullNode->Left = NullNode->Right = NullNode; } return NullNode; } static SplayTree Splay( ElementType Item, Position X ); SplayTree MakeEmpty( SplayTree T ) { if( T != NullNode ) { MakeEmpty( T->Left ); MakeEmpty( T->Right ); free( T ); } return NullNode; } void PrintTree( SplayTree T ) { if( T != NullNode ) { PrintTree( T->Left ); printf( "%d ", T->Element ); PrintTree( T->Right ); } } SplayTree Find( ElementType X, SplayTree T ) { return Splay( X, T ); } SplayTree FindMin( SplayTree T ) { return Splay( NegInfinity, T ); } SplayTree FindMax( SplayTree T ) { return Splay( Infinity, T ); } /* This function can be called only if K2 has a left child */ /* Perform a rotate between a node (K2) and its left child */ /* Update heights, then return new root */ static Position SingleRotateWithLeft( Position K2 ) { Position K1; K1 = K2->Left; K2->Left = K1->Right; K1->Right = K2; return K1; /* New root */ } /* This function can be called only if K1 has a right child */ /* Perform a rotate between a node (K1) and its right child */ /* Update heights, then return new root */ static Position SingleRotateWithRight( Position K1 ) { Position K2; K2 = K1->Right; K1->Right = K2->Left; K2->Left = K1; return K2; /* New root */ } /* START: fig12_6.txt */ /* Top-down splay procedure, */ /* not requiring Item to be in tree */ SplayTree Splay( ElementType Item, Position X ) { static struct SplayNode Header; Position LeftTreeMax, RightTreeMin; Header.Left = Header.Right = NullNode; LeftTreeMax = RightTreeMin = &Header; NullNode->Element = Item; while( Item != X->Element ) { if( Item < X->Element ) { if( Item < X->Left->Element ) X = SingleRotateWithLeft( X ); if( X->Left == NullNode ) break; /* Link right */ RightTreeMin->Left = X; RightTreeMin = X; X = X->Left; } else { if( Item > X->Right->Element ) X = SingleRotateWithRight( X ); if( X->Right == NullNode ) break; /* Link left */ LeftTreeMax->Right = X; LeftTreeMax = X; X = X->Right; } } /* while Item != X->Element */ /* Reassemble */ LeftTreeMax->Right = X->Left; RightTreeMin->Left = X->Right; X->Left = Header.Right; X->Right = Header.Left; return X; } /* END */ /* START: fig12_7.txt */ SplayTree Insert( ElementType Item, SplayTree T ) { static Position NewNode = NULL; if( NewNode == NULL ) { NewNode = malloc( sizeof( struct SplayNode ) ); if( NewNode == NULL ) FatalError( "Out of space!!!" ); } NewNode->Element = Item; if( T == NullNode ) { NewNode->Left = NewNode->Right = NullNode; T = NewNode; } else { T = Splay( Item, T ); if( Item < T->Element ) { NewNode->Left = T->Left; NewNode->Right = T; T->Left = NullNode; T = NewNode; } else if( T->Element < Item ) { NewNode->Right = T->Right; NewNode->Left = T; T->Right = NullNode; T = NewNode; } else return T; /* Already in the tree */ } NewNode = NULL; /* So next insert will call malloc */ return T; } /* END */ /* START: fig12_8.txt */ SplayTree Remove( ElementType Item, SplayTree T ) { Position NewTree; if( T != NullNode ) { T = Splay( Item, T ); if( Item == T->Element ) { /* Found it! */ if( T->Left == NullNode ) NewTree = T->Right; else { NewTree = T->Left; NewTree = Splay( Item, NewTree ); NewTree->Right = T->Right; } free( T ); T = NewTree; } } return T; } /* END */ ElementType Retrieve( SplayTree T ) { return T->Element; }
