| 1 | #define AVL_MULTISET 0 |
| 2 | template <class T> |
| 3 | struct avl_tree { |
| 4 | struct node { |
| 5 | T item; node *p, *l, *r; |
| 6 | int size, height; |
| 7 | node(const T &_item, node *_p = NULL) : item(_item), p(_p), |
| 8 | l(NULL), r(NULL), size(1), height(0) { } }; |
| 9 | avl_tree() : root(NULL) { } |
| 10 | node *root; |
| 11 | inline int sz(node *n) const { return n ? n->size : 0; } |
| 12 | inline int height(node *n) const { |
| 13 | return n ? n->height : -1; } |
| 14 | inline bool left_heavy(node *n) const { |
| 15 | return n && height(n->l) > height(n->r); } |
| 16 | inline bool right_heavy(node *n) const { |
| 17 | return n && height(n->r) > height(n->l); } |
| 18 | inline bool too_heavy(node *n) const { |
| 19 | return n && abs(height(n->l) - height(n->r)) > 1; } |
| 20 | void delete_tree(node *n) { if (n) { |
| 21 | delete_tree(n->l), delete_tree(n->r); delete n; } } |
| 22 | node*& parent_leg(node *n) { |
| 23 | if (!n->p) return root; |
| 24 | if (n->p->l == n) return n->p->l; |
| 25 | if (n->p->r == n) return n->p->r; |
| 26 | assert(false); } |
| 27 | void augment(node *n) { |
| 28 | if (!n) return; |
| 29 | n->size = 1 + sz(n->l) + sz(n->r); |
| 30 | n->height = 1 + max(height(n->l), height(n->r)); } |
| 31 | #define rotate(l, r) \ |
| 32 | node *l = n->l; \ |
| 33 | l->p = n->p; \ |
| 34 | parent_leg(n) = l; \ |
| 35 | n->l = l->r; \ |
| 36 | if (l->r) l->r->p = n; \ |
| 37 | l->r = n, n->p = l; \ |
| 38 | augment(n), augment(l) |
| 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; |
| 55 | while (cur) { |
| 56 | if (cur->item < item) cur = cur->r; |
| 57 | else if (item < cur->item) cur = cur->l; |
| 58 | else break; } |
| 59 | return cur; } |
| 60 | node* insert(const T &item) { |
nothing calls this directly
no outgoing calls
no test coverage detected