1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <stdio.h>
using namespace std;
struct node {
    int key, num;
    node* left;
    node* right;
    node(int a, int b) { key = a, num = b, left = NULL, right = NULL; }
};
void right_rotate(node*& t) {
    node* k = t->left;
    t->left = k->right;
    k->right = t;
    k->num = t->num;
    t->num = t->left->num + t->right->num + 1;
    t = k;
}
void left_rotate(node*& t) {
    node* k = t->right;
    t->right = k->left;
    k->left = t;
    k->num = t->num;
    t->num = t->left->num + t->right->num + 1;
    t = k;
}
class SBT {
public:
    node* root;
    SBT() { root = NULL; }
    void insert(int key,node*& t);
    //bool delete(int key);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX