| 40 | } |
| 41 | |
| 42 | public static void rotate(int i) { |
| 43 | int f = father[i], g = father[f], soni = lr(i), sonf = lr(f); |
| 44 | if (soni == 1) { |
| 45 | right[f] = left[i]; |
| 46 | if (right[f] != 0) { |
| 47 | father[right[f]] = f; |
| 48 | } |
| 49 | left[i] = f; |
| 50 | } else { |
| 51 | left[f] = right[i]; |
| 52 | if (left[f] != 0) { |
| 53 | father[left[f]] = f; |
| 54 | } |
| 55 | right[i] = f; |
| 56 | } |
| 57 | if (g != 0) { |
| 58 | if (sonf == 1) { |
| 59 | right[g] = i; |
| 60 | } else { |
| 61 | left[g] = i; |
| 62 | } |
| 63 | } |
| 64 | father[f] = i; |
| 65 | father[i] = g; |
| 66 | up(f); |
| 67 | up(i); |
| 68 | } |
| 69 | |
| 70 | public static void splay(int i, int goal) { |
| 71 | int f = father[i], g = father[f]; |