| 52 | } |
| 53 | |
| 54 | public static void rotate(int i) { |
| 55 | int f = father[i], g = father[f], soni = lr(i), sonf = lr(f); |
| 56 | if (soni == 1) { |
| 57 | right[f] = left[i]; |
| 58 | if (right[f] != 0) { |
| 59 | father[right[f]] = f; |
| 60 | } |
| 61 | left[i] = f; |
| 62 | } else { |
| 63 | left[f] = right[i]; |
| 64 | if (left[f] != 0) { |
| 65 | father[left[f]] = f; |
| 66 | } |
| 67 | right[i] = f; |
| 68 | } |
| 69 | if (g != 0) { |
| 70 | if (sonf == 1) { |
| 71 | right[g] = i; |
| 72 | } else { |
| 73 | left[g] = i; |
| 74 | } |
| 75 | } |
| 76 | father[f] = i; |
| 77 | father[i] = g; |
| 78 | up(f); |
| 79 | up(i); |
| 80 | } |
| 81 | |
| 82 | public static void splay(int i, int goal) { |
| 83 | int f = father[i], g = father[f]; |