| 39 | void left_rotate(node *n) { rotate(r, l); } |
| 40 | void right_rotate(node *n) { rotate(l, r); } |
| 41 | void fix(node *n) { |
| 42 | while (n) { augment(n); |
| 43 | if (too_heavy(n)) { |
| 44 | if (left_heavy(n) && right_heavy(n->l)) |
| 45 | left_rotate(n->l); |
| 46 | else if (right_heavy(n) && left_heavy(n->r)) |
| 47 | right_rotate(n->r); |
| 48 | if (left_heavy(n)) right_rotate(n); |
| 49 | else left_rotate(n); |
| 50 | n = n->p; } |
| 51 | n = n->p; } } |
| 52 | inline int size() const { return sz(root); } |
| 53 | node* find(const T &item) const { |
| 54 | node *cur = root; |