Source (Plain Text)
#include <iostream>
using namespace std;
class BinarySearchTree {
private:
struct node {
int key;
node *l, *r;
node (int k) : key(k), l(NULL), r(NULL) {}
~node() { delete l; delete r; }
} *root;
node* insert (node *u, int key) {
if (u == NULL) {
node *v=new node (key); return v;
} else {
if (key < u->key) u->l=insert (u->l, key);
else if (key > u->key) u->r=insert (u->r, key);
return u;
}
}
node* remove (node* u, int key) {
if (u == NULL) return NULL;
if (key < u->key) u->l=remove (u->l, key);
else if (key > u->key) u->r=remove (u->r, key);
else {
if (u->l == NULL) { node* v = u->r; u->r=NULL; delete u; return v; }
if (u->r == NULL) { node* v = u->l; u->l=NULL; delete u; return v; }
u->l = removeMax (u->l, u->key); }
return u;
}
node* removeMax (node *u, int& key) {
if (u->r == NULL) {
key=u->key; node* v=u->l;
u->l=NULL; delete u;
return v;
} else {
u->r = removeMax (u->r, key);
return u;
}
}
int height (node *u) {
if (u == NULL) return 0;
return 1 + max (height (u->l), height (u->r));
}
int size (node *u) {
if (u == NULL) return 0;
return 1 + size (u->l) + size (u->r);
}
public:
BinarySearchTree() : root(NULL) {}
~BinarySearchTree() { delete root; } void insert (int key) { root=insert (root, key); }
void remove (int key) { root=remove (root, key); }
int height() { return height (root); }
int size() { return size (root); }
};
void testcase() {
BinarySearchTree T;
int n; cin >> n;
while (n--) {
int x; cin >> x;
if (x > 0) T.insert (x);
else T.remove (-x);
}
printf ("%i %i\n", T.size(), T.height());
}
int main() {
int t; cin >> t;
while (t--) testcase();
return 0;
}