Is it possible to optimize this recursive function?

Luca Pedersoli 0
Viewed 59

I am trying to understand if this is the fastest way possible to delete a node in the Tree.

struct node *deleteNode(struct node *root, char *key)
{
    // base case
    if (root == NULL)
        return root;

    // If the key to be deleted
    // is smaller than the root's
    // key, then it lies in left subtree
    if (strcmp(key, root->key) < 0)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted
    // is greater than the root's
    // key, then it lies in right subtree
    else if (strcmp(key, root->key) > 0)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key,
    // then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        // node with two children:
        // Get the inorder successor
        // (smallest in the right subtree)
        struct node *temp = minValueNode(root->right);

        // Copy the inorder
        // successor's content to this node
        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

It takes a tree and a word and deletes the node from the tree. The thing I want to understand is when do I reach a "perfect" optimization level? I have worked a lot on this code and I think it is the best way possible. What can I look for more?

tree c
1 Answers

First the initial parameter to deleteNode is the root, but you should actually name it just node or subtree.

You should free the key, and strdup the key on node creation.

Finding the value at that node you cannot immediately delete that node. Either look at the left's max value (left - rights - rightnull node) or rights min value (right - lefts - leftnull node).

You have three pointers, root, xnull node, and the xnull node's other subtree. One form of deleting is called rotating the pointers.

Notice you do copy the key. In C++ that could be more costly that a pointer copy. In C copying a pointer or at most a struct is similarly costly, though I would favor a pointer copy.

Then you descend the branch again, so there can be optimized a bit; at least more immediate.

struct node *deleteNode(struct node *tree, char *key)
{
    // base case
    if (tree == NULL)
        return tree;

    // If the key to be deleted
    // is smaller than the tree's
    // key, then it lies in left subtree
    int cmp = strcmp(key, tree->key); // Thanks to RachidK
    if (cmp < 0)
        tree->left = deleteNode(tree->left, key);

    // If the key to be deleted
    // is greater than the tree's
    // key, then it lies in right subtree
    else if (cmp > 0)
        tree->right = deleteNode(tree->right, key);

    // if key is same as tree's key,
    // then This is the node
    // to be deleted
    else
    {
        struct node *result;
        // node with only one child or no child
        if (tree->left == NULL)
        {
            result = tree->right;
        }
        else if (tree->right == NULL)
        {
            result = tree->left;
        }
        else
        {
            // node with two children:
            // Get the inorder successor
            // (smallest in the right subtree)
            struct node **successor = &(tree->right);
            while ((*successor)->left != NULL)
            {
                successor = &(*successor)->left;
            }
            // rotate pointers:
            result = *successor;
            result->left = tree->left;
            *successor = result->right;
            result->right = tree->right;
        }
        free(tree->key);
        free(tree);
        return result;
    }
    return tree;
}

I did not test it. Not successor being an alias of first a right and then of left fields.

Joop Eggen0
Related