卡在从二叉搜索树中删除节点

Question

我一直在尝试按照教科书“算法导论”进行操作，但是从 BST 中删除节点时我卡在了以下步骤 - 当要删除的节点有两个子节点时

我的代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bst.h"


void error()
{
    fprintf(stderr, "%s\n", "Error assigning memory to node");
    exit(1);
}

void insert(node **root, int key)
{
    node *t1, *t2;

    if (*root == NULL) {
        printf("Root is null\n");
        *root = (node *)malloc(sizeof(node));
        if (*root==NULL) {
            fprintf(stderr, "%s\n", "Cannot allocate memory for node in Insert");
            exit(1);
        }
        (*root)->key = key;
        (*root)->left = (*root)->right = NULL;
    }
    else {
        printf("Root contains data. Inserting new node.\n");
        t1 = *root;

        while (t1 != NULL) {
            t2 = t1;

            if (key < t1->key)
                t1 = t1->left;
            else
                t1 = t1->right;
        }

        if(key < t2->key) {
            t2->left = (node *) malloc(sizeof(node));
            t2 = t2->left;
            if (t2==NULL)
                error();
            t2 -> key = key;
        }
        else {
            t2->right = (node *) malloc(sizeof(node));
            t2 = t2->right;
            if (t2==NULL)
                error();
            t2->key = key;
        }
    }

    
}

void inorder(node * root)
{
    if (root!=NULL) {
        inorder(root->left);
        printf("%d ->", root->key);
        inorder(root->right);
    }
}

node * search(node *root, int key)
{
    node * t = root;

    while (t!=NULL)
    {
        if (key == t->key)
            return t;
        else if (key < t->key)
            t = t->left;
        else
            t = t->right;
    }
    return NULL;
}

node * getparent(node * root, int key)
{
    node * t = root, *parent = NULL;

    while (t!=NULL)
    {   
        if (key == t->key)
            return parent;
        else if (key < t->key)
            t = t->left;
        else
            t = t->right;
        parent = t;
    }
    return NULL;
}

node * delete(node *root, int key)
{
    node * todelete = search(root,key), *parent = getparent(root, key), *y;
    if (todelete==NULL) {
        fprintf(stderr, "%s\n", "Key not found");
        exit(2);
    }

    if (todelete->left == NULL && todelete->right==NULL) { //Deleting node with no children
        if (todelete == parent->left)
            parent->left = NULL;
        else
            parent->right = NULL;
        free(todelete);
        return root;
    }
    else if (todelete->left && !todelete->right) {
        if (todelete == parent->left)
            parent->left = todelete->left;
        else
            parent->right = todelete->right;
        free(todelete);
        return root;
    }
    else if (todelete->right & !todelete->left) {
        if (todelete == parent->left)
            parent->left = todelete->left;
        else
            parent->right = todelete->right;
        free(todelete);
        return root;
    }
    else
    {
        node * yparent = NULL;
        y= todelete->right;
        while (y->left!=NULL)
        {
            y = y->left;
            yparent = y;
        }
        if(yparent != todelete) {
            //stuck here
        }
    }


}

bst.h:

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

typedef struct treenode node;

node * getparent(node * root, int key);
void insert(node **root, int key);
node * search(node *root, int key);
node * delete(node *root, int key);
void inorder(node * root);

任何指导将不胜感激。我应该尝试设置 y = y->right 然后设置 todelete->right = y correct?

Answer 1

I'm stuck at the following step when deleting a node from a BST - when the node to be deleted has both children

从 BST 的属性可以看出，如果一个节点 N 有两个 children 那么子树中的每个节点都以左边的根节点 child 小于以右 child 和 为根的子树中的每个节点，反之亦然 。特别地，左子树中的最大节点L_max小于右子树中的所有节点，而最小节点在右子树 R_min 比左子树的所有节点都大。这些是 in-order 遍历中 N 之前和之后的节点。这两个后代都很容易找到，而且都不超过一个child（否则它们在任何子树中都不可能是最大值或最小值）。

接下来，如果你想删除节点 N 那么你可以选择 L_max 或R_min，从树中删除它（这很容易，因为它最多有一个child） , 并用它替换 N 。或者，删除 L_max 或 R_min，以及将节点 N 的密钥替换为该已删除节点的密钥。

Answer 2

将代码更改为以下代码并且它有效（对于删除功能）：

static void transplant(node * root, node * u, node * v)
{
    node *uparent = getparent(root, u->key);
    node * vparent = getparent(root, v->key);

    if (uparent == NULL)
        root = v;
    else if (u == uparent->left)
        uparent->left = v;
    else uparent->right = v;

    if (v!=NULL)
        vparent = uparent;
}

node * delete(node *root, int key)
{
    node * todelete = search(root,key), *parent = getparent(root, key), *y;
    if (todelete==NULL) {
        fprintf(stderr, "%s\n", "Key not found");
        exit(2);
    }

    if (todelete->left == NULL && todelete->right==NULL) { //Deleting node with no children
        if (todelete == parent->left)
            parent->left = NULL;
        else
            parent->right = NULL;
        free(todelete);
        return root;
    }
    else if (todelete->left && !todelete->right) {
        if (todelete == parent->left)
            parent->left = todelete->left;
        else
            parent->right = todelete->left;
        free(todelete);
        return root;
    }
    else if (todelete->right && !todelete->left) {
        if (todelete == parent->left)
            parent->left = todelete->right;
        else
            parent->right = todelete->right;
        free(todelete);
        return root;
    }
    else {
        y = todelete->right;
        while(y->left!=NULL)
        {
            y = y->left;
        }

        node *yparent = getparent(root, y->key);
        if (yparent != todelete)
        {
            transplant(root, y, y->right);
            y->right = todelete->right;
            node * yrightparent = getparent(root, y->right->key);
            yrightparent = y;
        }
        transplant(root, todelete, y);
        y->left = todelete->left;
        node *yleftparent = getparent(root, y->left->key);
        yleftparent = y;
        free(todelete);
        return root;

    }

卡在从二叉搜索树中删除节点

Stuck at deleting node from Binary Search Tree

c

binary-search-tree