Пишу бинарное дерево поиска, в котором может быть несколько одинаковых ключей(если быть точным, то в данном случае ключ совпадает со значением).
Хочу при удалении любого ключа (например 5) он находил и удалял все найденные ключи.
Для этого думаю написать функцию, которая рекурсивно ищет все ключи и кладет их в лит, после чего, пройдя по списку, удалить их все.
Проблема заключается в следующем:
Когда выбираются элементы со значением, то возвращаются указатели на них, соответственно если в дереве один ключ лежит раньше другого, то при удалении первого ключа рекурсивно удалится всё поддерево, следующее за ним. Соответственно, освободится память, на которую указывает второй элемент, что приведет к двойному освобождению памяти.
Наглядное представление:
/* В дереве есть элемент с ключом 10, функция find_place_to_add()
* возвращает указатель на этот элемент
*/
Tree<int>::Node* n = t1->find_place_to_add(10);
std::cout << n->data << std::endl; // Вывод: 10
t1->clear(); // Полностью очищаем всё дерево
//Память освобождена
std::cout << n->data << std::endl; // Вывод: 10
int* i = new(n) int;
*i = 80;
std::cout << n->data << std::endl; // Вывод: 80
Подскажите пожалуйста, как проверить занята ли память, на которую ссылается указатель.
Коммент заставил меня сомневаться правильно ли я вообще реализовал освобождение памяти:
template <typename DataType>
void Tree<DataType>::clear() noexcept
{
free_resources(root);
delete root;
root = nullptr;
}
template <typename DataType>
void Tree<DataType>::free_resources(Node* node) noexcept
{
if(node->parent != nullptr)
{
if (node->data < node->parent->data)
{
node->parent->left = nullptr;
}
else
{
node->parent->right = nullptr;
}
}
node->data = DataType();
if(node->left != nullptr) free_resources(node->left);
if(node->right != nullptr) free_resources(node->right);
delete node->left;
delete node->right;
}