AVL Tree

#include <iostream>
#include <vector>

    using namespace std;

struct subset_node {
    int key;
    subset_node* left;
    subset_node* right;
};

bool init(subset_node** sn) { // инициализация пустого дерева (аналогично списку, пустое дерево это указатель на NULL)
    *sn = NULL;
    return true;
}

void printgraph(subset_node* sn) {
    if (sn != NULL) {
        if (sn->left != NULL)
            cout << sn->left->key;
        else
            cout << "NULL";
        cout << " <- " << sn->key << " -> ";
        if (sn->right != NULL)
            cout << sn->right->key;
        else
            cout << "NULL";
        cout << endl;
        printgraph(sn->left);
        printgraph(sn->right);
    }
}


unsigned int size_my(subset_node* sn, unsigned int count) {
    if (sn != NULL) {
        if (sn->left != NULL)
            count += size_my(sn->left, 1);
        if (sn->right != NULL)
            count += size_my(sn->right, 1);
    }
    else
        return 0;
    return count;
}

unsigned int size(subset_node* sn) { // количество элементов в дереве
    return size_my(sn, 1);
}

bool bfs_my(subset_node* sn, vector<subset_node*> data, int* res, int* l) {
    if (data.size() != 0) {
        if (data[0]->right != NULL)
            data.push_back(data[0]->right);
        if (data[0]->left != NULL)
            data.push_back(data[0]->left);
        *(res + (*l)) = data[0]->key;
        (*l)++;
        data.erase(data.begin());
        bfs_my(sn, data, res, l);
    }
    else {
        if (sn == NULL)
            return false;
        else if ((*l) == 0) {
            if (sn->right != NULL)
                data.push_back(sn->right);
            if (sn->left != NULL)
                data.push_back(sn->left);
            *(res + (*l)) = sn->key;
            (*l)++;
            bfs_my(sn, data, res, l);
        }
    }
    return true;
}

int* BFS(subset_node* sn) { //обход в ширину, возвращает указатель на массив
    vector<subset_node*> data;
    unsigned int n = size(sn);
    int* res = new int[n];
    int l = 0;
    bfs_my(sn, data, res, &l);
    return res;
}

bool dfs_my(subset_node* sn, int* res, int* l) {
    if (sn != NULL) {
        if (sn->left != NULL)
            dfs_my(sn->left, res, l);
        *(res + *l) = sn->key;
        (*l)++;
        if (sn->right != NULL)
            dfs_my(sn->right, res, l);
        return true;
    }
    else
        return false;
}

int* DFS(subset_node* sn) { //обход в глубину, возвращает указатель на массив
    unsigned int n = size(sn);
    int* res = new int[n];
    int l = 0;
    dfs_my(sn, res, &l);
    return res;
}

bool height_my(subset_node* sn, unsigned int count, unsigned int* max_count) {
    if (sn != NULL) {
        ++count;
        if (count > * max_count)
            *max_count = count;
        height_my(sn->left, count, max_count);
        height_my(sn->right, count, max_count);
    }
    return true;
}

unsigned int height(subset_node* sn) { // высота дерева
    unsigned int res = 0;
    height_my(sn, 0, &res);
    return res;
}

int bfactor(subset_node* sn) { // проверка на сбалансированность
    return height(sn->right) - height(sn->left);
}


subset_node* rotateleft(subset_node* sn) {
    subset_node* r = sn->right;
    sn->right = r->left;
    r->left = sn;
    return r;
}

subset_node* rotateright(subset_node* sn) {
    subset_node* l = sn->left;
    sn->left = l->right;
    l->right = sn;
    return l;
}

subset_node* balance(subset_node* sn) // балансировка узла p
{
    if (bfactor(sn) == 2) {
        if (bfactor(sn->right) < 0)
            sn->right = rotateright(sn->right);
        return rotateleft(sn);
    }
    if (bfactor(sn) == -2) {
        if (bfactor(sn->left) > 0)
            sn->left = rotateleft(sn->left);
        return rotateright(sn);
    }
    return sn; // балансировка не нужна
}

subset_node* balance_all(subset_node* sn) {
    if (sn != NULL) {
        subset_node* tmp = balance(sn);
        subset_node* l = tmp->left;
        subset_node* r = tmp->right;
        tmp->left = balance_all(l);
        tmp->right = balance_all(r);
        return tmp;
    }
    return NULL;
}

bool insert_my(subset_node** sn, subset_node* new_elem) { // добавление элемента в дерево,
    if (*sn == NULL) {
        *sn = new_elem;
    }
    else if (new_elem == NULL)
        return true;
    else {
        subset_node* iter_first = *sn;
        subset_node* iter_second = NULL;
        while (iter_first != NULL) {
            iter_second = iter_first;
            if (new_elem->key < iter_first->key) {
                iter_first = iter_first->left;
            }
            else if (new_elem->key > iter_first->key)
                iter_first = iter_first->right;
            else {
                delete new_elem; //элемент не добавляем, удаляем его
                return false;
            }
        }
        if (new_elem->key < iter_second->key)
            iter_second->left = new_elem;
        else
            iter_second->right = new_elem;
    }
    *sn = balance_all(*sn);
    return true;
}

bool insert(subset_node** sn, int k) { // добавление элемента в дерево,
// дубли игнорировать (ничего не добавлять в дерево, если там уже есть элемент с таким же key) и возвращать false
    subset_node* tmp = new subset_node;
    tmp->key = k;
    tmp->left = NULL;
    tmp->right = NULL;
    return insert_my(sn, tmp);
}

subset_node* find(subset_node* sn, int k) { // поиск элемента в дереве, нужно вернуть
// указатель на элемент с тем же key или, если такого элемента не нашлось, то NULL
    subset_node* iter_first = sn;
    while (iter_first != NULL) {
        if (k < iter_first->key)
            iter_first = iter_first->left;
        else if (k > iter_first->key)
            iter_first = iter_first->right;
        else
            return iter_first;
    }
    return NULL;
}

void find_elem_and_pred(subset_node* sn, subset_node** elem, subset_node** pred_elem,
    int k) { // поиск элемента в дереве, нужно вернуть
// указатель на элемент с тем же key или, если такого элемента не нашлось, то NULL
    subset_node* iter_first = sn;
    subset_node* iter_second = NULL;
    while (iter_first != NULL) {
        if (k < iter_first->key) {
            iter_second = iter_first;
            iter_first = iter_first->left;
        }
        else if (k > iter_first->key) {
            iter_second = iter_first;
            iter_first = iter_first->right;
        }
        else {
            *elem = iter_first;
            *pred_elem = iter_second;
            break;
        }
    }
}

bool remove_old(subset_node** sn, int k) { // удаление элемента из дерева (если элемента не нашлось,
// то ничего не удалять и вернуть false)
    if (*sn == NULL)
        return false;
    else {
        subset_node* elem = NULL, * pred_elem = NULL;
        find_elem_and_pred(*sn, &elem, &pred_elem, k);
        if (elem != NULL) {
            if (pred_elem != NULL) {
                if (elem == pred_elem->left) {
                    pred_elem->left = NULL;
                }
                else {
                    pred_elem->right = NULL;
                }
                insert_my(sn, elem->left);
                insert_my(sn, elem->right);
            }
            else { // удаляем корень
                *sn = NULL;
                insert_my(sn, elem->left);
                insert_my(sn, elem->right);
            }
            delete elem;
            return true;
        }
        return false;
    }
}

bool remove(subset_node** sn, int k) { // удаление элемента из дерева (если элемента не нашлось,
// то ничего не удалять и вернуть false)
    if (*sn == NULL)
        return false;
    else {
        subset_node* elem = NULL, * pred_elem = NULL;
        find_elem_and_pred(*sn, &elem, &pred_elem, k);
        if (elem != NULL) {
            subset_node* iter_first = elem->left;
            if (iter_first == NULL) {
                if (pred_elem->left == elem)
                    pred_elem->left = elem->right;
                else
                    pred_elem->right = elem->right;
            }
            else {
                subset_node* iter_second = NULL;
                while (iter_first != NULL) {
                    iter_second = iter_first;
                    iter_first = iter_first->right;
                }
                subset_node* elem1 = NULL, * pred_elem1 = NULL;
                find_elem_and_pred(*sn, &elem1, &pred_elem1, iter_second->key);
                elem->key = iter_second->key;
                if (pred_elem1->left == elem1)
                    pred_elem1->left = elem1->left;
                else
                    pred_elem1->right = elem1->left;
            }
        }
        *sn = balance_all(*sn);
        return true;
    }
}

void destructor(subset_node* sn) { // очистить всю используемую память
    subset_node* iter_first = sn;
    if (sn != NULL) {
        destructor(sn->left);
        destructor(sn->right);
        delete sn;
    }
}