Delete function binary search tree BST with parent passing the tree pointer as argument

Question

I am having a very difficult time understanding what my book is wanting me to learn. I am currently re-vising some algorithms and data structure material I studied quite some years ago. One chapter is about Binary Search Tree and their application, etc. The book talks about a BST (binary search tree) as a tree with nodes that has the following qualities: int data, node left, node right, node parent. I understand this and I have implemented a search function.

Now to the issue: How do I create a delete function when the arguments I have are N* delete(Tree* tree, N* delete_node);?

There are lots of recursive functions but they rely on the fact that we recursively pass a pointer of a node and a key value. This is not what the exercise in the book is looking for. An example of a method that I have tried and works is: source code for C Program for Insertion and Deletion in Binary Search Tree. Two other great sources that fails to meet these criteria are codezclub and geeksforgeeks. They solve the "delete" function but their function have other parameters in their function. My book specifies

A modifying operation that, given a pointer delete_node to an element in the BST, tree, deletes delete_node from the BST tree and returns its pointer.

Function declaration: N* delete(Tree* tree, N* delete_node);

Anybody got any ideas? Also minimally reproducible examples are given in the sources above with the caviat that the structs are missing "parent" node. Below are my definitions for the tree and the node:

typedef struct N {
    int data;
    struct N* left;
    struct N* right;
    struct N* parent;
} N;

typedef struct Tree {
    N* root;
} Tree;

Alparslan Alparslan · Accepted Answer · 2021-03-12T21:39:06

You can use CLRS as a reference for understanding Binary search tree data structures and operations on it. Let's implement delete procedure first and then explain necessary parts.
We need 2 procedures, SUCCESSOR and transplant other than delete itself to make it complete. required procedures are implement before delete.

In order to move subtrees around within the binary search tree, we define a subroutine transplant, which replaces one subtree as a child of its parent with another subtree. When transplant replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends up having v as its appropriate child.

void transplant(Tree** root, Tree* u, Tree* v) {
    if(u == NULL)
        return;
    else if(u->parent == NULL)
        *root = v;
    else if(u->parent->left == u)
        u->parent->left = v;
    else
        u->parent->right = v;
    if(v != NULL)
        v->parent = u->parent;
}

We need to implement Tree* SUCCESSOR(Tree* T) procedure which returns the node where node->key is the next larger element greater than T->key, if it exists. otherwise, returns NULL. We need SUCCESSOR when delete_node has 2 children. It'll be replaced with the SUCCESSOR(delete_node).

Tree* SUCCESSOR(Tree* T) {
    if(T == NULL)
        return T; // Since T==NULL, it's equivalent to return NULL
    else if(T->left != NULL) {
        while(T->left != NULL)
            T=T->left;
        return T;
    }
    else {
        while(T->parent != NULL && T->parent->right == T)
            T = T->parent;
        return T->parent;
    }
}

We can all needed to implement delete procedure.

Tree* delete(Tree* root, Tree* delete_node) {
    if(delete_node == NULL)
        return root;
    
    if(delete_node->left== NULL)
        transplant(&root, delete_node, delete_node->right);

    else if(delete_node->right == NULL)
        transplant(&root, delete_node, delete_node->left);

    else {
        Tree* succ = SUCCESSOR(delete_node);
        if(delete_node->right != succ) {
            transplant(&root, succ , succ ->right);
            succ->right = delete_node->right;
            succ->right->parent = succ;
        }
        transplant(&root, delete_node, succ);
        succ->left = delete_node->left;
        succ->left->parent = succ;
    }
    return root;
}

Here's how delete procedure works:

The procedure for deleting a given node delete_node from a binary search tree root takes as arguments pointers to root and delete_node. It organizes its cases a bit differently from the three mentioned above.

If delete_node has no left child (first if statement do this part), then we replace delete_node by its right child, which may or may not be NULL. When delete_node's right child is NULL, this case deals with the situation in which delete_node has no children. When delete_node's right child is non-NULL, this case handles the situation in which delete_node has just one child, which is its right child.

If delete_node has just one child, which is its left child (else if part handles this case), then we replace delete_node by its left child.

Otherwise, delete_node has both a left and a right child. We find delete_node’s successor succ, which lies in delete_node’s right subtree and has no left child (If it has a left, child, then it's not the smallest number greater than delete_node->key. We get contradiction). We want to splice succ out of its current location and have it replace delete_node in the tree.

If succ is delete_node's right child, then we replace delete_node by succ.

Otherwise, succ lies within delete_node’s right subtree but is not delete_node's right child. In this case, we first replace succ by its own right child, and then we replace delete_node by succ.

Since both quotes are taken fromCLRS, I encourage you to review it in case of having problem in understanding why it works.

Delete function binary search tree BST with parent passing the tree pointer as argument

1 Answers