• API
• FAQ
• Tools
• Archive
daily pastebin goal
45%
SHARE
TWEET

# Untitled

a guest Jul 11th, 2018 49 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.

Top