daily pastebin goal
17%
SHARE
TWEET

Untitled

a guest Jul 11th, 2018 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. typedef struct tree_node Tree;
  2. struct tree_node {
  3.     Tree * left, * right;
  4.     int item;
  5. };
  6.  
  7. Tree * splay (int i, Tree * t) {
  8. /* Simple top down splay, not requiring i to be in the tree t.  */
  9. /* What it does is described above.                             */
  10.     Tree N, *l, *r, *y;
  11.     if (t == NULL) return t;
  12.     N.left = N.right = NULL;
  13.     l = r = &N;
  14.  
  15.     for (;;) {
  16.         if (i < t->item) {
  17.             if (t->left == NULL) break;
  18.             if (i < t->left->item) {
  19.                 y = t->left;                           /* rotate right */
  20.                 t->left = y->right;
  21.                 y->right = t;
  22.                 t = y;
  23.                 if (t->left == NULL) break;
  24.             }
  25.             r->left = t;                               /* link right */
  26.             r = t;
  27.             t = t->left;
  28.         } else if (i > t->item) {
  29.             if (t->right == NULL) break;
  30.             if (i > t->right->item) {
  31.                 y = t->right;                          /* rotate left */
  32.                 t->right = y->left;
  33.                 y->left = t;
  34.                 t = y;
  35.                 if (t->right == NULL) break;
  36.             }
  37.             l->right = t;                              /* link left */
  38.             l = t;
  39.             t = t->right;
  40.         } else {
  41.             break;
  42.         }
  43.     }
  44.     l->right = t->left;                                /* assemble */
  45.     r->left = t->right;
  46.     t->left = N.right;
  47.     t->right = N.left;
  48.     return t;
  49. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top