Удаление первого вхождения числа в Декартовом дереве

Question

Удаление первого вхождения числа в Декартовом дереве

Рейтинг: 0Ответов: 1Опубликовано: 10.01.2023

Нужно, чтобы удалялось только первое вхождение. В моём случае, при использовании функции удаления удаляются все вхождения. Метод удаления:

bool NonOptimizedRemove(TreapNode*& treapNode, int data)
{
    if (treapNode == nullptr)
    {
        return false;
    }
    if (data == treapNode->Data)
    {
        TreapNode* less = nullptr;
        TreapNode* greater = nullptr;
        Split(treapNode, data, less, greater);
        TreapNode* equal = nullptr;
        Split(greater, data + 1, equal, greater);
        delete equal;
        treapNode = Merge(less, greater);

        return true;
    }
    if (data < treapNode->Data)
    {
        return NonOptimizedRemove(treapNode->LeftNode, data);
    }
    else
    {
        return NonOptimizedRemove(treapNode->RightNode, data);
    }
}

Методы Split и Merge:

void Split(TreapNode* treapNode, int data, TreapNode*& left, TreapNode*& right)
{
    if (!treapNode)
    {
        left = right = nullptr;
    }
    else if (treapNode->Data < data)
    {
        Split(treapNode->RightNode, data, treapNode->RightNode, right);
        left = treapNode;
    }
    else
    {
        Split(treapNode->LeftNode, data, left, treapNode->LeftNode);
        right = treapNode;
    }
}


TreapNode* Merge(TreapNode* left, TreapNode* right)
{
    if (!left || !right)
    {
        return left == nullptr ? right : left;
    }
    if (left->Priority > right->Priority)
    {
        left->RightNode = Merge(left->RightNode, right);
        return left;
    }

    right->LeftNode = Merge(left, right->LeftNode);
    return right;
}

Структура Декартового дерева:

/// @brief Узел дерева.
struct TreapNode
{
    /// @brief Значение узла.
    int Data;

    /// @brief Приороитет узла.
    int Priority = rand();

    /// @brief Указатель на левый узел.
    TreapNode* LeftNode = nullptr;

    /// @brief Указатель на правый узел.
    TreapNode* RightNode = nullptr;
};

/// @brief Структура данных Декартово дерево.
struct Treap
{
    /// @brief Корень.
    TreapNode* Root;
};

c# дерево бинарное-дерево

Источник: Stack Overflow на русском

Answer 1

▲ 0Принят

Это не в вашем случае удаляются все элементы, это по алгоритму.
Не нужно просто копировать кем-то написанные алгоритмы.
В вашем случае вы делаете 2 раза Split, получаете 3 дерева, одно из которых - все узлы равные data. И выбрасываете это дерево, т.е. как раз и удаляете все узлы равные data.
А чтобы удалить только первое вхождение нужно один раз применить Merge на потомках узла. Что делает Merge? Принимает на вход два декартовых дерева и сливает их в одно корректное декартово дерево. Вот и примените его для потомков удаляемого узла.

bool NonOptimizedRemove(TreapNode*& treapNode, int data)
{
    if (data == treapNode->Data)
    {
        // запомнить текущий узел
        treapNode = Merge(treapNode->LeftNode, treapNode->RightNode);
        // удалить текущий узел
    }
....
}

Только не забудьте удалить текущий узел.

Удаление первого вхождения числа в Декартовом дереве

Ответы