使用父指针从二进制搜索树中删除节点 [英] Delete node from binary search tree with parent pointer

问题描述

我正在研究一种从二进制搜索树中删除具有给定键的节点的算法.到目前为止，我已经能够提出以下代码:

I am working on an algorithm to delete a node with a given key from a binary search tree. So far, I have been able to come up with the following code:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

typedef int ElType;

typedef struct Tree {
    ElType key;
    struct Tree *left;
    struct Tree *right;
    struct Tree *parent;
} Tree;

Tree* InsertBST(Tree* t, int k)
{
    if (t == NULL) {
        Tree* w = (Tree*) malloc(sizeof(Tree));
        w->key = k;
        w->left = NULL;
        w->right = NULL;
        w->parent = NULL;
        return w;
    }

    if (k <= t->key) {
        t->left = InsertBST(t->left, k);
        t->left->parent = t;
    }
    else {
        t->right = InsertBST(t->right, k);
        t->right->parent = t;
    }

    return t;
}

Tree* DeleteMaxOfBST(Tree* t, ElType *deleted_value)
{
    if (t == NULL) {
        *deleted_value = -1;
        return NULL;
    }

    if (t->right == NULL) {
        *deleted_value = t->key;
        Tree* w = t->left;
        w->parent = t->parent;
        free(t);
        return w;
    }

    t->right = DeleteMaxOfBST(t->right, deleted_value);
    return t;
}

Tree* DeleteNodeOfBST(Tree* t, int k)
{
    if (t == NULL) return NULL;

    if (k < t->key) {
        t->left = DeleteNodeOfBST(t->left, k);
        return t;
    }
    else if (k > t->key) {
        t->right = DeleteNodeOfBST(t->right, k);
        return t;
    }
    else if (t->left == NULL) {
        Tree* w = t->right;
        w->parent = t->parent;
        free(t);
        return w;
    }
    else {
        ElType max_left;
        t->left = DeleteMaxOfBST(t->left, &max_left);
        t->key = max_left;
        return t;
    }
}

通常的想法是，我想使用带有指向父节点的指针的BST，并能够在保留BST结构的同时使用我指定的任何键删除节点.

The general idea is that I want to work with a BST with pointers to parent nodes and be able to delete a node with whichever key I specify while preserving the structure of a BST.

我的代码对某些树中的某些键有效，但对其他键却崩溃，而没有任何明显的模式.然后，我得到以下错误:

My code works for some keys in some trees but crashes for other keys without any apparent pattern. I then get the following error:

Segmentation fault (core dumped)

我倾向于认为我已经弄乱了指向父节点的指针，但不能完全查明错误的出在哪里.我对C还是比较陌生，因此，对于指针是否确实是这里的问题以及如何解决此问题，我将不胜感激.

I am inclined to think I have messed up the pointers to the parent nodes but cannot quite pinpoint where the fault is. I am relatively new to C, so I would appreciate any comments whether pointers are in fact the problem here and how to possibly fix this.

推荐答案

因此，在没有任何代码运行方式示例的情况下，很难说出程序运行时分段错误发生的确切位置.当您的程序遇到分段错误时，这意味着该程序正试图访问由于某种原因而无法访问的内存.通常，这意味着您的指针试图指向内存中不应该指向的地址.

So, without any examples of how your code runs it's hard to say where exactly the segmentation fault is occurring when your program is running. When your program encounters a segmentation fault that means that the program is attempting to access memory that, for whatever reason, it is unable to. This generally means your pointers are trying to point at an address in memory that they shouldn't be.

我的建议是逐步运行代码，看看问题出在哪里.或者找到一个调试器，该调试器可以向您显示程序遇到的内存问题.我知道Valgrind程序适用于Ubuntu和其他Linux最佳计算机，但是我不确定其他操作系统是否可以使用其他程序.您可以在此处阅读有关Valgrind的更多信息: http://valgrind.org/.每当需要检查程序中潜在的内存处理问题时，我都会使用它.

My suggestion would be to run the code step by step and see where the problem occurs. Or find a debugger that can show you the memory issues your program is having. I know that the program Valgrind exists for Ubuntu and other Linux best machines, but I'm not sure what others are available for other OSes. You can read more about Valgrind here: http://valgrind.org/. I use it whenever I need to check for potential memory handling issues in my programs.

除此之外，只需密切注意使用malloc创建的空间以及指针指向的位置即可.删除给定节点时，请确保正确重新连接树.手动处理内存可能会很麻烦，但您会一劳永逸.

Other than that, just keep a real close eye on the space that you create using malloc, as well as where your pointers are pointing. Make sure to reconnect your tree properly when you delete the given node. Manually handling memory can be a pain, but you'll get the hang of it.

这篇关于使用父指针从二进制搜索树中删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！