# 这些功能足以保持二进制搜索树的平衡吗？

``````static int maxKey = 1000;
typedef int Key;
class Item {
private:
Key keyval;
public:
Item() {
keyval = maxKey;
}
Key key() const {
return keyval;
}
bool null() { return keyval == maxKey; }
bool scan(istream& is = cin) {
is >> keyval;
return(!cin.fail());
}
//Print values of info and keyval
void show(ostream& os = cout) {
os << keyval << endl;
}
};

template <typename Item, typename Key>
class BST {
private:
//This is the struct to represent nodes of the tree
struct node {
Item item;
node* l; node* r;
node(Item it) { item = it; l = 0; r = 0; }
};
Item nullItem;

if(!tree) return 0;
return 1+tree_size(tree->r)+tree_size(tree->l);
}
//Right rotation
link x = h->l; //Create a temp node equal to left child of root (it will become new root)
h->l = x->r; //Left child of root become right child of temp node
x->r = h; //Right child of temp node become root
h = x; //Root become temp node
}
//Left rotation
link x = h->r; //Create a temp node equal ro right child of root (it will became new root)
h->r = x->l; //Right child of root become left child of temp node
x->l = h; //Left child of temp node become root
h = x; //Root become temp node
}
//Insert keeping the tree balanced
void insert_rootR(link& h, Item it) {
if (!h) {
h = new node(it);
return;
}
if (h->item.key() < it.key()) {
insert_rootR(h->r, it);
rotL(h);
}
else {
insert_rootR(h->l, it);
rotR(h);
}
}
Item selectR(link h, int k) {
if (h == 0) return nullItem;
int t = tree_size(h->l);
if (t > k) return selectR(h->l, k);
if (t < k) return selectR(h->r, k-t-1);
return h->item;
}