Сбалансированное дерево поиска

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node* left;
    node* right;
    int height;
    int level;
};

node* newNode(int key)
{
    node* t = new node();
    t->data = key;
    t->left = NULL;
    t->right = NULL;
    t->height = 1;
    t->level = 0;
    return t;
}

int height(node* t) {
    if (t == NULL) return 0;
    return t->height;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

node* min(node* t) {
    node* cur = t;
    while (cur->left != NULL) cur = cur->left;
    return cur;
}

int balance(node* t) {
    if (t == NULL) return 0;
    return height(t->left) - height(t->right);
}

node* rotateright(node* y)
{
    node* x = y->left;
    node* b = x->right;
    x->right = y;
    y->left = b;
    y->height = max(height(y->left),
        height(y->right)) + 1;
    x->height = max(height(x->left),
        height(x->right)) + 1;
    return x;
}

node* rotateleft(node* t)
{
    node* y = t->right;
    node* b = y->left;
    y->left = t;
    t->right = b;
    t->height = max(height(t->left),
        height(t->right)) + 1;
    y->height = max(height(y->left),
        height(y->right)) + 1;
    return y;
}

node* push(node* t, int in) {
    if (t == NULL) return newNode(in);
    if (in < t->data)
        t->left = push(t->left, in);
    else if (in > t->data)
        t->right = push(t->right, in);
    else
        return t;

    t->height = 1 + max(height(t->left), height(t->right));
    if (balance(t) > 1 && in < t->left->data)
        return rotateright(t);
    if (balance(t) < -1 && in > t->right->data)
        return rotateleft(t);
    if (balance(t) > 1 && in > t->left->data) {
        t->left = rotateleft(t->left);
        return rotateright(t);
    }
    if (balance(t) < -1 && in < t->right->data) {
        t->right = rotateright(t->right);
        return rotateleft(t);
    }
    return t;
}

node* deleteNode(node* t, int in) {
    if (t == NULL) return t;

    if (in < t->data) t->left = deleteNode(t->left, in);
    else if (in > t->data) t->right = deleteNode(t->right, in);
    else {
        if (t->left == NULL || t->right == NULL) {
            node* tmp = t->left ? t->left : t->right;
            if (tmp == NULL) {
                tmp = t;
                t = NULL;
            }
            else {
                *t = *tmp;
            }
            free(tmp);
        }
        else {
            node* tmp = min(t->right);
            t->data = tmp->data;
            t->right = deleteNode(t->right, tmp->data);
        }
    }
    if (t == NULL) return t;
    t->height = 1 + max(height(t->left), height(t->right));
    if (balance(t) > 1 && balance(t->left) >= 0) return rotateright(t);
    if (balance(t) > 1 && balance(t->left) < 0) { t->left = rotateleft(t->left); return rotateright(t); }
    if (balance(t) < -1 && balance(t->right) <= 0) return rotateleft(t);
    if (balance(t) < -1 && balance(t->right) > 0) { t->right = rotateright(t->right); return rotateleft(t); }
    return t;
}

void leveller(node* t, int x) {
    t->level = x;
    if (t->left != NULL)
    {
        leveller(t->left, x + 1);
    }
    if (t->right != NULL)
    {
        leveller(t->right, x + 1);
    }
}

void search(node* root, int key) {
    leveller(root, 0);
    if (!root) return;
    while (root->data != key) {
        if (key < root->data)  root = root->left;
        else root = root->right;
        if (root == NULL) break;
    }
    cout << " Уровень узла " << key << " = " << root->level << endl;
}

void Print(node* Tree, int l) {
    int i;
    if (Tree != NULL) {
        Print((*Tree).right, l + 1);

        for (i = 1; i <= l; i++) cout << "   "; {
            cout << Tree->data << endl;
        }
        Print(((*Tree).left), l + 1);
    }
}

int main() {
    setlocale(0, "");
    node* tree = NULL;
    tree = push(tree, 9);
    tree = push(tree, 5);
    tree = push(tree, 10);
    tree = push(tree, 0);
    tree = push(tree, 6);
    tree = push(tree, 11);
    tree = push(tree, -1);
    tree = push(tree, 1);
    tree = push(tree, 2);
    Print(tree, 0);
    search(tree, -1);
    return 0;
}