template<typename T>
void RBT<T>::del(T key) {
    node<T> *x = this->root;
    while (x) {
        if (x->key == key) {
            break;
        } else if (x->key > key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    if (!x->left && !x->right) {// Если нет детей, то просто обнуляем
        if (!x->parent) {// Если нет родителя - то найденный элемент - корень
            this->root = nullptr;
            delete x;
            return;
        } else if (x->parent->left == x) {
            x->parent->left = nullptr;
        } else {
            x->parent->right = nullptr;
        }
        delete x;
        return;
    } else if (!x->left && x->right) {// Если есть только правый ребёнок, то вставляем на место x - правого ребёнка
        if (!x->parent) {
            this->root = x->right;
        } else if (x->parent->left == x) {
            x->parent->left = x->right;
        } else {
            x->parent->right = x->right;
        }
        insert_case1(x->right);
    } else if (x->left && !x->right) {
        // Аналогично с левым
        if (!x->parent) {
            this->root = x->left;
        } else if (x->parent->left == x) {
            x->parent->left = x->left;
        } else {
            x->parent->right = x->left;
        }
        insert_case1(x->left);
    } else {// Если есть оба сына
        node<T> *y = x->right;
        node<T> *z = x;
        while (y) {
            z = y;
            y = y->left;
        }
        x->key = z->key;
        x->data = z->data;
        if (z->right) {// Если у найденного минимума был правый сын, перекидываем с его родителя указатель на правого сына и балансируем
            if (z->parent->left == z) {
                z->parent->left = z->right;
            } else {
                z->parent->right = z->right;
            }
            insert_case1(z->right);
        } else {
            if (z->parent->left == z) {
                z->parent->left = nullptr;
            } else {
                z->parent->right = nullptr;
            }
        }
    }
}