Удалить один элемент в бинарном дереве поиска (C ++) - PullRequest
Новая
       7

Удалить один элемент в бинарном дереве поиска (C ++)

0 голосов
/ 10 сентября 2018

Я создал класс двоичного дерева поиска (узла): 

class BstNode {
public:
    BstNode(int value);
    ~BstNode();
    BstNode* Delete(int value);

    // more methods

private:
    int value_;
    BstNode* left_;
    BstNode* right_;
};

С деструктором, который выглядит следующим образом: 

BstNode::~BstNode() {
    delete left_;
    delete right_;
}

А Delete функция: 

BstNode* BstNode::Delete(int value) {
    // If the value to be deleted is smaller than the root's key,
    // then it lies in the left subtree.
    if (value < value_) {
        if (left_ == nullptr) return nullptr;
        else left_ = left_->Delete(value);
    }

    // If the value to be deleted is larger than the root's key,
    // then it lies in the right subtree.
    else if (value > value_) {
        if (right_ == nullptr) return nullptr;
        else right_ = right_->Delete(value);
    }

    // If the key to be deleted is the same as root's key, then *this*
    // is the node to be deleted.
    else {
        // If this node has no children, then we can just delete it.
        if (left_ == nullptr && right_ == nullptr) {
            delete this;
            return nullptr;
        }

        // If this node has one child, then we can just set this node to
        // that child and delete this node afterwards.
        else if (left_ == nullptr) {
            BstNode* temp = right_;
            delete this;
            return temp;
        }
        else if (right_ == nullptr) {
            BstNode* temp = left_;
            delete this;
            return temp;
        }

        // If this node has two children, then we have to get the "in-order successor"
        // (the smallest node in the right subtree).
        else {
            BstNode *temp = right_->Smallest();

            // Copy that node's value to this node
            value_ = temp->value_;

            // Then delete that value from the right subtree
            right_ = right_->Delete(value_);
        }
    }
    return this;
}

Что меня смущает, так это фрагмент: 

else if (left_ == nullptr) {
    BstNode* temp = right_;
    delete this;
    return temp;
}
else if (right_ == nullptr) {
    BstNode* temp = left_;
    delete this;
    return temp;
}

Если вызов delete вызывает деструктор класса, разве я не удалил бы все поддерево (правое или левое)? Однако при тестировании создается впечатление, что дерево делает именно то, что мне нужно: удалить узел и «переместить» дочернее поддерево туда, где находится «это», при этом поддеревья все еще не повреждены.

Выполнение BstNode* temp = this;, насколько мне известно, просто скопирует указатели на left_ и right_, а затем вызов delete this должен уничтожить данные, стоящие за ними.

Я что-то упускаю из delete this?

Ответы [ 2 ]

0 голосов
/ 10 сентября 2018

BstNode* temp=left_ и BstNode* temp=right_ сохранят значение left_ или right_ во временной переменной. Вы используете delete this; после того, как сохраните это значение в темп. Теперь, после использования delete this;, left_ и right_ будут удалены, но temp все равно останется без изменений. delete this; не будет влиять на значение temp (которое имеет ваше левое / правое поддерево), и теперь вы можете вернуть соответствующее левое / правое поддерево после того, как соответствующее правое / левое поддерево будет удалено (В этом случае либо left_ или вправо_ указать NULL). Надеюсь, это поможет! Кроме того, использование delete для указателя на объект, не выделенный с новым, приводит к непредсказуемым результатам, поэтому будьте осторожны с этим!

0 голосов
/ 10 сентября 2018

Поскольку ваш деструктор BstNode удаляет оба узла left_ и right_, вы можете столкнуться с неопределенным поведением в результате этой последовательности: 

BstNode* temp = right_;
delete this;
return temp;

После оператора delete this, temp станет висящим указателем, поскольку объект, на который он указывает, был удален. Вы возвращаете этот указатель и сохраняете его в другом узле, и, в конце концов, когда вы разыменовываете этот узел, может произойти все что угодно - в том числе и программа, которая работает нормально.

Вы должны либо установить right_ в nullptr перед вызовом удаления, либо изменить деструктор (и общую последовательность уничтожения), чтобы не удалять дочерние узлы.

...