Функция delete в АА tree

Как можно написать функцию удаления в AA tree? Написал базовые функции, а над удалением сижу уже который день, на хабре или вики не подходят под программу:

    struct node
    {
        int count, level;
        string key; 
        node *right;
        node *left;
        node *parent;
        node *root;
    }*root;
    class AATree
    {
        public:
            int lookup(string &);
            void skew(node *);
            bool split(node *);
            void rebal(node *);
            node *insert(node *,node *);
            void print(node *);
            int countnode(node *);
            AATree()
        {
                root = NULL;
            }
    };
    int AATree::lookup(string &key)
    {
        node *temp = new node;
        temp->key = key;
        temp->level = 1;
        temp->count = 0;
        temp->left = NULL;
        temp->right = NULL;
        temp->parent = NULL;
        temp = insert(root, temp);
        return temp->count;
    }
     
    /*
     * Skew Tree
     */
     
    void AATree::skew(node *temp)
    {
        node *ptr = temp->left;
        if (temp->parent->left == temp)
            temp->parent->left = ptr;
        else
            temp->parent->right = ptr;
        ptr->parent = temp->parent;
        temp->parent = ptr;
        temp->left = ptr->right;
        if (temp->left != NULL)
            temp->left->parent = temp;
        ptr->right = temp;
        temp->level = (temp->left ? temp->left->level + 1 : 1);
    }
    bool AATree::split(node *temp)
    {
        node* ptr = temp->right;
        if (ptr && ptr->right && (ptr->right->level == temp->level))
        {
            if (temp->parent->left == temp)
                temp->parent->left = ptr;
            else
                temp->parent->right = ptr;
            ptr->parent = temp->parent;
            temp->parent = ptr;
            temp->right = ptr->left;
            if (temp->right != NULL)
                temp->right->parent = temp;
            ptr->left = temp;
            ptr->level = temp->level + 1;
            return true;
        }
        return false;
    }
    void AATree::rebal(node* temp)
    {
        temp->left = NULL;
        temp->right = NULL;
        temp->level = 1;
        for (temp = temp->parent; temp != root; temp = temp->parent)
        {
            if (temp->level != (temp->left ? temp->left->level + 1 : 1 ))
            {
                skew(temp);
                if (temp->right == NULL)
                    temp = temp->parent;
                else if (temp->level != temp->right->level)
                    temp = temp->parent;
            }
            if (temp->parent != root)
            {
                if (split(temp->parent) == false)
                    break;
            }
        }
    }
    node* AATree::insert(node* temp, node* ins)
    {
        if (root == NULL)
        {
            ins->count = 1;
            ins->parent = NULL;
            ins->left = NULL;
            ins->right = NULL;
            root = ins;
            return root;
        }
        if (ins->key < temp->key)
        {
            if (temp->left)
                return insert(temp->left, ins);
            temp->left = ins;
            ins->parent = temp;
            ins->count = 1;
            rebal(ins);
            return ins;
        }
        if (ins->key > temp->key)
        {
            if (temp->right)
                return insert(temp->right, ins);
            temp->right = ins;
            ins->parent = temp;
            ins->count = 1;
            rebal(ins);
            return ins;
        }
        temp->count++;
        delete ins;
        return temp;
    }
int AATree::countnode(node* temp)
{
    if (!temp)
        return 0;
    int count = 1;
    count = count + countnode(temp->left);
    count = count + countnode(temp->right);
    return count;
}